Цветовая кодировка - Color-coding

Эта статья посвящена методике разработки алгоритмов на графах. Для использования цвета для отображения информации см. цветовой код. Для использования в других целях см. Цветовой код (значения).

В Информатика и теория графов, период, термин цветовое кодирование относится к алгоритмическая техника что полезно для открытия сетевые мотивы. Например, его можно использовать для обнаружения простой путь длины k в данном график. Традиционный алгоритм цветового кодирования вероятностный, но это может быть дерандомизированный без особых накладных расходов во время работы.

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

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

Полученные результаты

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

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

Метод

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

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

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

Пример

Примером может служить поиск простого цикла длины k в графике грамм = (V, E).

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

Алгоритм красочного поиска циклов работает, сначала находя все пары вершин в V которые связаны простым путем длиной k − 1, а затем проверка, связаны ли две вершины в каждой паре. Учитывая функцию окраски c : V → {1, ..., k} раскрасить график грамм, пронумеровать все разделы набора цветов {1, ..., k} на два подмножества C₁, C₂ размера ${\displaystyle k/2}$ каждый. Обратите внимание, что V можно разделить на V₁ и V₂ соответственно, и пусть грамм₁ и грамм₂ обозначим подграфы, индуцированные V₁ и V₂ соответственно. Затем рекурсивно найдите цветные пути длины ${\displaystyle k/2-1}$ в каждом из грамм₁ и грамм₂. Предположим, что логическая матрица А₁ и А₂ представляют собой связность каждой пары вершин в грамм₁ и грамм₂ красочной дорожкой соответственно, и пусть B - матрица, описывающая отношения смежности между вершинами V₁ и те из V₂, логическое произведение ${\displaystyle A_{1}BA_{2}}$ дает все пары вершин в V которые соединены красочной дорожкой длиной k − 1. Таким образом, рекурсивное отношение матричных умножений есть ${\displaystyle t(k)\leq 2^{k}\cdot t(k/2)}$, что дает время выполнения ${\displaystyle 2^{O(k)}\cdot V^{\omega }=O(V^{\omega })}$. Хотя этот алгоритм находит только конечные точки красочного пути, другой алгоритм Алона и Наора^[4] который сам находит красочные дорожки, может быть включен в него.

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

В дерандомизация цветового кодирования включает в себя перечисление возможных раскрасок графа грамм, такая, что случайность раскраски грамм больше не требуется. Для целевого подграфа ЧАС в грамм чтобы его можно было обнаружить, перечисление должно включать как минимум один экземпляр, где ЧАС красочный. Чтобы добиться этого, перечислив k-идеальная семья F хэш-функций из {1, ..., |V|} к {1, ..., k} достаточно. По определению, F является k-совершенно, если для каждого подмножества S из {1, ..., |V|} куда ${\displaystyle |S|=k}$, существует хеш-функция час в F такой, что час : S → {1, ..., k} является идеально. Другими словами, должна существовать хеш-функция в 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- идеальная семья, которая отображает {1, ..., |V|} к {1, ..., k²}, с последующим построением еще одного k- идеальная семья, которая отображает {1, ..., k²} к {1, ..., k}. На первом этапе можно построить такое семейство с 2пбревно 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|}$ что карты из {1, ..., |V|} к {1, ..., k} может быть получен.

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

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

Приложения

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

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

дальнейшее чтение

• Alon, N .; Dao, P .; Hajirasouliha, I .; Хормоздиари, Ф .; Сахиналп, С. С. (2008). «Подсчет и обнаружение мотивов биомолекулярной сети с помощью цветового кодирования». Биоинформатика. 24 (13): i241 – i249. Дои:10.1093 / биоинформатика / btn163. ЧВК  2718641. PMID  18586721.
• Hüffner, F .; Wernicke, S .; Зихнер, Т. (2008). «Разработка алгоритмов для цветового кодирования с приложениями для обнаружения сигнального пути». Алгоритмика. 52 (2): 114–132. CiteSeerX  10.1.1.68.9469. Дои:10.1007 / s00453-007-9008-7.

Рекомендации

1. Алон Н., Юстер Р. и Цвик У. 1994. Цветовое кодирование: новый метод поиска простых путей, циклов и других небольших подграфов в больших графах. В материалах двадцать шестого ежегодного симпозиума ACM по теории вычислений (Монреаль, Квебек, Канада, 23–25 мая 1994 г.). STOC '94. ACM, Нью-Йорк, штат Нью-Йорк, 326–335. DOI = http://doi.acm.org/10.1145/195058.195179
2. Алон Н., Юстер Р. и Цвик У. 1995. Цветовое кодирование. J. ACM 42, 4 (июль 1995 г.), 844–856. DOI = http://doi.acm.org/10.1145/210332.210337
3. Алгоритм Копперсмита – Винограда
4. Алон, Н. и Наор, М. 1994 Дерандомизация, свидетельства умножения булевых матриц и построения совершенных хеш-функций. Технический отчет. Номер заказа UMI: CS94-11., Weizmann Science Press, Израиль.
5. Наор, М., Шульман, Л. Дж., И Сринивасан, А. 1995. Сплиттеры и почти оптимальная дерандомизация. В материалах 36-го ежегодного симпозиума по основам компьютерных наук (23–25 октября 1995 г.). FOCS. Компьютерное общество IEEE, Вашингтон, округ Колумбия, 182.
6. Schmidt, J. P .; Сигель, А. (1990). «Пространственная сложность не обращающих внимания на хеш-функции k-зонда». SIAM J. Comput. 19 (5): 775–786. Дои:10.1137/0219054.
7. Наор, Дж. И Наор, М. 1990. Вероятностные пространства с малым смещением: эффективные конструкции и приложения. В материалах двадцать второго ежегодного симпозиума ACM по теории вычислений (Балтимор, Мэриленд, США, 13–17 мая 1990 г.). Х. Ортис, Под ред. СТОК '90. ACM, Нью-Йорк, штат Нью-Йорк, 213-223. DOI = http://doi.acm.org/10.1145/100216.100244
8. Алон, Н., Голдрейх, О., Хастад, Дж., И Перальта, Р. 1990. Простое построение почти k-образных независимых случайных величин. В материалах 31-го ежегодного симпозиума по основам информатики (22–24 октября 1990 г.). SFCS. IEEE Computer Society, Вашингтон, округ Колумбия, 544-553, том 2. Дои:10.1109 / FSCS.1990.89575