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

редактировать

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

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

Метод цветового кодирования был предложен и проанализирован в 1994 году Нога Алон и Ури Цвик.

Содержание

1 Результаты
2 Метод
- 2.1 Пример
3 Дерандомизация
4 Приложения
5 Далее чтение
6 Ссылки

Результаты

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

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

метод

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

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

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

Пример

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

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

Алгоритм красочного поиска циклов работает, сначала находя все пары вершин в V, которые соединены простым путем длины k - 1, а затем проверка того, что две вершины в каждой па ir подключены. Дана функция раскраски c: V → {1,..., k} для раскрашивания графа G, перечислим все разбиения цветового набора {1,..., k} на два подмножества C 1, C 2 размера $k / 2 {\ displaystyle k / 2}$ $k / 2$ каждый. Обратите внимание, что V можно разделить на V 1 и V 2 соответственно, и пусть G 1 и G 2 обозначают подграфы, индуцированные V 1 и V 2 соответственно. Затем рекурсивно найдите цветные пути длиной $k / 2-1 {\ displaystyle k / 2-1}$ $k / 2-1$ в каждом из G 1 и G 2 <115.>. Предположим, что логическая матрица A 1 и A 2 представляет связность каждой пары вершин в G 1 и G 2 красочным путь, соответственно, и пусть B будет матрицей, описывающей отношения смежности между вершинами V 1 и V 2, логическое произведение $A 1 BA 2 {\ displaystyle A_ {1} BA_ {2}}$ $A_ {1} BA_ {2}$ дает все пары вершин в V, которые соединены красочным путем длины k - 1. Таким образом, рекурсивное соотношение умножений матриц равно $t (k) ≤ 2 k ⋅ t (k / 2) {\ displaystyle t (k) \ leq 2 ^ {k} \ cdot t (k / 2)}$ $t (k) \ leq 2 ^ {k} \ cdot t (k / 2)$ , что дает время выполнения $2 О (К) ⋅ В ω знак равно О (В ω) {\ Displaystyle 2 ^ {О (к)} \ cdot V ^ {\ omega} = O (V ^ {\ omega})}$ ${\ displaystyle 2 ^ {O (k)} \ cdot V ^ {\ omega} = O (V ^ {\ omega})}$ . Хотя этот алгоритм находит только конечные точки цветного пути, в него можно включить другой алгоритм Алона и Наора, который находит сами красочные пути.

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

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

Существует несколько подходов к созданию такого k-совершенного семейства хешей:

Лучшее явное построение - от Мони Наор, и, где семейство размера $ekk O (журнал ⁡ k) журнал ⁡ | V | Можно получить {\ displaystyle e ^ {k} k ^ {O (\ log k)} \ log | V |}$ $e ^ {k} k ^ {{O (\ log k)}} \ log | V |$ . Эта конструкция не требует, чтобы целевой подграф существовал в исходной задаче поиска подграфа.
Другая явная конструкция Алана Сигеля и дает семейство размера $2 O (k) log 2 ⁡ | V | {\ displaystyle 2 ^ {O (k)} \ log ^ {2} | V |}$ $2 ^ {{O (k)}} \ log ^ {2} | V |$ .
Другая конструкция, которая появляется в исходной статье Noga Alon et al. можно получить, сначала построив k-совершенное семейство, отображающее {1,..., | V |} в {1,..., k}, а затем построив другое k-совершенное семейство, отображающее {1,..., k} на {1,..., k}. На первом этапе можно построить такое семейство из 2nlog k случайных битов, которые почти не зависят от 2log k по k, а пространство выборок, необходимое для генерации этих случайных битов, может быть всего лишь $k O (1) журнал ⁡ | V | {\ displaystyle k ^ {O (1)} \ log | V |}$ $k ^ {{O (1)}} \ log | V |$ . На втором этапе Жанетт П. Шмидт и Алан Сигель показали, что размер такого k-совершенного семейства может быть $2 O (k) {\ displaystyle 2 ^ {O (k)}}$ $2 ^ {O (k)}$ . Следовательно, составляя k-совершенные семейства из обоих шагов, k-совершенное семейство размера $2 O (k) log ⁡ | V | Можно получить {\ displaystyle 2 ^ {O (k)} \ log | V |}$ $2 ^ {{O (k)}} \ log | V |$ , который отображает {1,..., | V |} в {1,..., k}.

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

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

Приложения

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

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

Дополнительная литература

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