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

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

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

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

Результаты

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

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

Метод

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

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

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

Пример

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

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

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

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

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

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

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

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

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

Приложения

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

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

Примечания

Литература

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

• 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.

Эта страница в последний раз была отредактирована 24 февраля 2024 в 18:59.