Цветовое кодирование

Цветовое кодирование — алгоритмическая техника[англ.], полезная для обнаружения структурных мотивов[англ.]. Может быть использована, к примеру, для обнаружения простого пути длины k в заданном графе. Традиционный алгоритм цветового кодирования является вероятностным, но решение может быть дерандомизировано[англ.] без существенного увеличения времени работы.

Цветовое кодирование также применяется для обнаружения циклов заданной длины и в более общем случае, как в задаче поиска изоморфного подграфа (NP-полная задача), где оно даёт алгоритмы полиномиального времени, если искомый подграф имеет ограниченную древесную ширину.

Эта техника широко используется в различных областях, включая науку, инженерию, медицину и информатику, для облегчения восприятия и анализа сложной информации.

Метод цветового кодирования предложили и анализировали в 1994 году. Авторы - Нога Алон, Рафаэль Юстер и Юрий Цвик[1][2].

Результаты

править

Следующие результаты могут быть получены методом цветового кодирования:

  • Для любой константы k, если граф   содержит цикл размера k, такой цикл может быть найден за:
    •   среднее время, или
    •   худшее время, где   является экспонентой умножения матриц[3].
  • Для любой константы k и любого графа   из нетривиального семейства графов, замкнутого по минорам (например, планарные графы), если G содержит простой цикл размера k, то такой цикл может быть найден за:
    • O(V) среднее время, или за
    • O(V log V) время в худшем случае.
  • Если граф   содержит подграф, изоморфный графу ограниченной древесной ширины, который имеет O(log V) вершин, то такой подграф может быть найден за полиномиальное время.

Чтобы решить задачу нахождения подграфа   в данном графе  , где H может быть путём, циклом или любым графом с ограниченной древесной шириной, а  , метод цветового кодирования начинает со случайной раскраски каждой вершины в G с помощью   цветов, а потом пытается найти полноцветную копию H в раскрашенном G. Здесь под полноцветным графом понимается граф, в котором каждая вершина раскрашена в свой цвет. Метод работает путём повторения (1) случайной раскраски графа и (2) нахождения полноцветной копии целевого подграфа. В конечном счёте целевой подграф может быть найден, если процесс повторять достаточное число раз.

Предположим, что копия H в G становится полноцветной с некоторой ненулевой вероятностью p. Отсюда следует, что при повторении случайной раскраски   раз эта копия однажды встретится. Заметим, что даже когда вероятность p мала, известно, что при   вероятность p лишь полиномиально мала. Предположим, что существует алгоритм, который для данного графа G и раскраски, которая отображает каждую вершину G в один из k цветов, находит копию полноцветной копии H, если она существует, за некоторое время O(r). Тогда ожидаемое время поиска копии H в G, если она существует, равно  .

Иногда желательно использовать более жёсткую версию цветной раскраски. Например, в контексте поиска циклов в планарных графах можно разрабатывать алгоритм для поиска хорошо раскрашенных циклов. Здесь под хорошо раскрашенным циклом понимается раскраска последовательными цветами.

Пример

править

В качестве примера возьмём поиск простого цикла длины k в графе  .

При применении метода случайной раскраски каждый простой цикл имеет вероятность   стать полноцветным, поскольку имеется   способов выкрасить k вершин цикла, среди которых встречается   вариантов полноцветной раскраски. Тогда алгоритм (описанный ниже) может быть использован для поиска полноцветных циклов в случайно раскрашенном графе G за время  , где   является константой умножения матриц. Тогда требуется полное время   для нахождения простого цикла длины k в G.

Алгоритм поиска полноцветного цикла сначала находит все пары вершин в V, соединённые простым путём длины k − 1, а потом проверяет, соединены ли две вершины в каждой паре. Если задана функция раскраски   для графа G, перенумеруем все разбиения множества цветов   на два подмножества   размера примерно   в каждом. Для каждого такого разбиения пусть   будет множеством вершинам, выкрашенных цветами из  , а   будет множеством вершин, выкрашенных цветами из  . Пусть   и   обозначают подграфы, порожденные   и   соответственно. Рекурсивно находим полноцветные пути длины   в   и  . Представим, что булевы матрицы   и   представляют связь каждой пары вершин в   и   полноцветным путём соответственно, и пусть B будет матрицей, описывающей смежность вершин   и  , тогда булево произведение   даёт все пары вершин в V, соединённые полноцветным путём длины k − 1. Объединение матриц, полученных на всех разбиениях множества цветов, даёт  , что приводит ко времени работы  . Хотя этот алгоритм находит только конечные точки полноцветного пути, может быть использован другой алгоритм Алона и Наора[4], который и находит, собственно, полноцветный путь.

Дерандомизация

править

Дерандомизация[англ.] цветового кодирования вовлекает перечисление возможных раскрашиваний графа G, так что рандомизация раскраски G больше не нужна. Для обнаружения целевого подграфа H в G, перечисление должно включать, по меньшей мере, один случай, где H полноцветн. Чтобы это получить, достаточно перечислить k-совершенное семейство F хеш-функций из   в {1, ..., k} . По определению, функция F k-совершенна, если для любого подмножества S множества  , где  , существует хеш-функция h из F, такая что   является идеальной функции хеширования[англ.]. Другими словами, должна существовать хеш-функци в F, которая раскрашивает заданные k вершин в k различных цвета.

Имеется несколько подходов к построению такого k-идеального семейства хеша:

  1. Лучшее явное построение предложили Мони Наор, Леонард Дж. Шульман и Аравинд Сринивасан[5], в котором можно получить семейство размера  . Это построение не требует, чтобы целевой подграф содержался в исходной задаче нахождения подграфа.
  2. Другое явное построение предложили Джанетта П. Шмидт и Алан Сигель[6] даёт семейство размера  .
  3. Ещё одно построение, которое появилось в исходной статье Нога Алона и др.[2], можно получить сначала путём построения k-совершенного семейства, которое отображает   в  , с построением другого k-совершенного семейства, которое отображает   в  . На первом шаге можно построить такое семейство с 2nlog k случайными битами, которое почти 2log k-независимо[7][8], и пространство, необходимое для генерации этих случайных бит, может быть ограничено величиной  . На втором шаге, как показали Джанетта П. Шмидт и Алан Зигель [6], размер такого k-идеального семейства может быть  . Следовательно, составляя k-идеальные семейства из обоих шагов, можно получить k-совершенное семейство размера  , которое отображает из   в  .

В случае дерандомизации идеального раскрашивания, когда каждая вершина подграфа раскрашивается последовательно, требуется k-идеальное семейство хэш-функций из   в  . Достаточное k-совершенное семейство, отображающее из   в  , может быть построено способом, подобным подходу 3 выше (первый шаг). В частности, это делается использованием   случайных бит, которые почти   независимы, а размер получающегося k-совершенного семейства будет равен  .

Дерандомизация метода цветового кодирования может быть легко распараллелена, что приводит к эффективным алгоритмам в классе NC.

Приложения

править

Недавно цветовое кодирование привлекло внимание ученых из области биоинформатики. Пример — определение сигнальных путей в сетях белок-белкового взаимодействия (ББВ). Другим примером является обнаружение и подсчёт числа мотивов[англ.] в сетях ББВ. При изучении как сигнальных путей, так и мотивов[англ.] позволяет более глубокое понимание похожести разницы многих биологических функций, процессов и структур в организмах.

Вследствие большого числа генетических данных, которые можно собрать, поиск путей или мотивов может занимать продолжительное время. Однако, используя метод цветового кодирования, мотивы и сигнальные пути с   вершинами в сети G с n вершинами могут быть найдены очень эффективно за полиномиальное время. Это позволяет исследовать более сложные или больших размеров структуры в сетях ББВ.

Примечания

править
  1. Alon, Yuster, Zwick, 1994, с. 23—25.
  2. 1 2 Alon, Yuster, Zwick, 1995, с. 844—856.
  3. См. Алгоритм Копперсмита — Винограда. Экспонента   умножения матриц — это степень   размера матрицы   асимптотической сложности алгоритма умножения матриц.
  4. Alon, Naor, 1994.
  5. Naor, Schulman, Srinivasan, 1995, с. 182.
  6. 1 2 Schmidt, Siegel, 1990, с. 775–786.
  7. Naor, Naor, 1990, с. 213—223.
  8. Alon, Goldreich, Hastad, Peralta, 1990, с. 544—553.

Литература

править
  • Naor J., Naor M. Small-bias probability spaces: efficient constructions and applications // Proceedings of the Twenty-Second Annual ACM Symposium on theory of Computing (Baltimore, Maryland, United States, May 13–17, 1990) / H. Ortiz, Ed.. — New York, NY: ACM, 1990. — doi:10.1145/100216.100244.
  • Alon N., Goldreich O., Hastad J., Peralta R. Simple construction of almost k-wise independent random variables // Proceedings of the 31st Annual Symposium on Foundations of Computer Science (October 22–24, 1990). SFCS.. — Washington, DC: IEEE Computer Society, 1990. — doi:10.1109/FSCS.1990.89575.
  • Alon N., Yuster R., Zwick U. Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs // Proceedings of the Twenty-Sixth Annual ACM Symposium on theory of Computing (Montreal, Quebec, Canada, May 23–25, 1994). STOC '94.. — New York, NY: ACM, 1994. — doi:10.1145/195058.195179.
  • Alon N., Yuster R., Zwick U. Color-coding. // J. ACM. — 1995. — Т. 42, вып. 4. — doi:10.1145/210332.210337.
  • Alon N., Naor M. Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions. // Technical Report. UMI Order Number: CS94-11.,. — Weizmann Science Press of Israel, 1994.
  • Naor M., Schulman L. J., Srinivasan A. Splitters and near-optimal derandomization // In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (October 23–25, 1995). FOCS.. — Washington, DC: IEEE Computer Society, 1995. — Т. 182.
  • Schmidt J. P., Siegel A. The spatial complexity of oblivious k-probe Hash functions // SIAM J. Comput.. — 1990. — Т. 19, вып. 5. — doi:10.1137/0219054.

Литература для дальнейшего чтения

править
  • Alon N., Dao P., Hajirasouliha I., Hormozdiari F., Sahinalp S. C. Biomolecular network motif counting and discovery by color coding // Bioinformatics. — 2008. — Т. 24, вып. 13. — С. i241–i249. — doi:10.1093/bioinformatics/btn163. — PMID 18586721. — PMC 2718641.
  • Hüffner F., Wernicke S., Zichner T. Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection // Algorithmica. — 2008. — Т. 52, вып. 2. — С. 114–132. — doi:10.1007/s00453-007-9008-7.