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

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

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

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

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

Результаты

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

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

Метод

Чтобы решить задачу нахождения подграфа $H=(V_{H},E_{H})$ в данном графе $G=(V,E)$ , где H может быть путём, циклом или любым графом с ограниченной древесной шириной, а $|V_{H}|=O(\log V)$ , метод цветового кодирования начинает со случайной раскраски каждой вершины в G с помощью $k=|V_{H}|$ цветов, а потом пытается найти полноцветную копию H в раскрашенном G. Здесь под полноцветным графом понимается граф, в котором каждая вершина раскрашена в свой цвет. Метод работает путём повторения (1) случайной раскраски графа и (2) нахождения полноцветной копии целевого подграфа. В конечном счёте целевой подграф может быть найден, если процесс повторять достаточное число раз.

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

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

Пример

В качестве примера возьмём поиск простого цикла длины k в графе $G=(V,E)$ .

При применении метода случайной раскраски каждый простой цикл имеет вероятность $k!/k^{k}>e^{-k}$ стать полноцветным, поскольку имеется $k^{k}$ способов выкрасить k вершин цикла, среди которых встречается $k!$ вариантов полноцветной раскраски. Тогда алгоритм (описанный ниже) может быть использован для поиска полноцветных циклов в случайно раскрашенном графе G за время $O(V^{\omega })$ , где $\omega$ является константой умножения матриц. Тогда требуется полное время $e^{k}\cdot O(V^{\omega })$ для нахождения простого цикла длины k в G.

Алгоритм поиска полноцветного цикла сначала находит все пары вершин в V, соединённые простым путём длины k − 1, а потом проверяет, соединены ли две вершины в каждой паре. Если задана функция раскраски $c\colon V\to \{1,\dots ,k\}$ для графа G, перенумеруем все разбиения множества цветов $\{1,\dots ,k\}$ на два подмножества $C_{1},C_{2}$ размера примерно $k/2$ в каждом. Для каждого такого разбиения пусть $V_{1}$ будет множеством вершинам, выкрашенных цветами из $C_{1}$ , а $V_{2}$ будет множеством вершин, выкрашенных цветами из $C_{2}$ . Пусть $G_{1}$ и $G_{2}$ обозначают подграфы, порожденные $V_{1}$ и $V_{2}$ соответственно. Рекурсивно находим полноцветные пути длины $k/2-1$ в $G_{1}$ и $G_{2}$ . Представим, что булевы матрицы $A_{1}$ и $A_{2}$ представляют связь каждой пары вершин в $G_{1}$ и $G_{2}$ полноцветным путём соответственно, и пусть B будет матрицей, описывающей смежность вершин $V_{1}$ и $V_{2}$ , тогда булево произведение $A_{1}BA_{2}$ даёт все пары вершин в V, соединённые полноцветным путём длины k − 1. Объединение матриц, полученных на всех разбиениях множества цветов, даёт $t(k)\leqslant 2^{k}\cdot t(k/2)$ , что приводит ко времени работы $2^{O(k)}\cdot V^{\omega }=O(V^{\omega })$ . Хотя этот алгоритм находит только конечные точки полноцветного пути, может быть использован другой алгоритм Алона и Наора^[4], который и находит, собственно, полноцветный путь.

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

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

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

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

В случае дерандомизации идеального раскрашивания, когда каждая вершина подграфа раскрашивается последовательно, требуется k-идеальное семейство хэш-функций из $\{1,\dots ,|V|\}$ в $\{1,\dots ,k!\}$ . Достаточное k-совершенное семейство, отображающее из $\{1,\dots ,|V|\}$ в $\{1,\dots ,k^{k}\}$ , может быть построено способом, подобным подходу 3 выше (первый шаг). В частности, это делается использованием $nk\log k$ случайных бит, которые почти $k\log k$ независимы, а размер получающегося k-совершенного семейства будет равен $k^{O(k)}\log |V|$ .

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

Приложения

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

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

Примечания

↑ Alon, Yuster, Zwick, 1994, с. 23—25.
↑ ¹ ² Alon, Yuster, Zwick, 1995, с. 844—856.
↑ См. Алгоритм Копперсмита — Винограда. Экспонента $\omega$ умножения матриц — это степень $\omega$ размера матрицы $n$ асимптотической сложности алгоритма умножения матриц.
↑ Alon, Naor, 1994.
↑ Naor, Schulman, Srinivasan, 1995, с. 182.
↑ ¹ ² Schmidt, Siegel, 1990, с. 775–786.
↑ Naor, Naor, 1990, с. 213—223.
↑ 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.