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

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

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

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

Результаты

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

Для каждой фиксированной константы k , если граф G = ( V , E ) содержит простой цикл размера k , то такой цикл можно найти в:
- $O(|V|^{\omega })$ ожидаемое время или
- $O(|V|^{\omega }\log |V|)$ время наихудшего случая, где $ω$ — показатель степени умножения матриц . ^[3]
Для каждой фиксированной константы k и каждого графа 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$ . Отсюда сразу следует, что если случайная раскраска повторяется $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ 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 : V \to {1, ..., k}$ для раскрашивания графа $G$ , перечислите все разделы набора цветов ${1, ..., k}$ на два подмножества $C 1, C 2$ размера $k/2$ каждый. Обратите внимание, что $V$ можно разделить на $V 1$ и $V 2$ соответственно, и пусть $G 1$ и $G 2$ обозначают подграфы, индуцированные $V 1$ и $V 2$ соответственно. Затем рекурсивно найдите красочные пути длиной $k/2-1$ в $G1 каждом$ и $G2 .$ из Предположим, что булева матрица $A 1$ и $A 2$ представляют связность каждой пары вершин в $G 1$ и $G 2$ цветным путем соответственно, и пусть $B$ — матрица, описывающая отношения смежности между вершинами $V 1$ и вершинами $V 2.$ , логическое произведение $A_{1}BA_{2}$ дает все пары вершин в $V$ , соединенные цветным путем длиной $k - 1$ . Таким образом, рекурсивное отношение умножения матриц имеет вид $t(k)\leq 2^{k}\cdot t(k/2)$ , что дает время выполнения $2^{O(k)}\cdot V^{\omega }$ . Хотя этот алгоритм находит только конечные точки цветного пути, другой алгоритм Алона и Наора ^[4] который сам находит красочные дорожки, может быть включен в него.

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

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

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

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

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

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

Приложения

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

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

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

Алон, Н.; Дао, П.; Хаджирасулиха, И.; Хормоздиари, Ф.; Сахинальп, Южная Каролина (2008). «Подсчет и обнаружение мотивов биомолекулярной сети с помощью цветового кодирования» . Биоинформатика . 24 (13): i241–i249. doi : 10.1093/биоинформатика/btn163 . ПМЦ 2718641 . ПМИД 18586721 .
Хюффнер, Ф.; Вернике, С.; Зихнер, Т. (2008). «Разработка алгоритмов цветового кодирования с применением к обнаружению сигнальных путей». Алгоритмика . 52 (2): 114–132. CiteSeerX 10.1.1.68.9469 . дои : 10.1007/s00453-007-9008-7 . S2CID 81069 .

Ссылки

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

[1] Алон Н., Юстер Р. и Цвик У. 1994. Цветовое кодирование: новый метод поиска простых путей, циклов и других небольших подграфов в больших графах. В материалах двадцать шестого ежегодного симпозиума ACM по теории вычислений (Монреаль, Квебек, Канада, 23–25 мая 1994 г.). СТОК '94. ACM, Нью-Йорк, штат Нью-Йорк, 326–335. DOI= http://doi.acm.org/10.1145/195058.195179

[orig-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 г.). ФОКС. Компьютерное общество IEEE, Вашингтон, округ Колумбия, 182.

[SS90-6] Перейти обратно: ^а ^б Шмидт, JP; Сигел, А. (1990). «Пространственная сложность забывчивых хэш-функций k-зонда». СИАМ Дж. Компьютер . 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 г.). СФКС. Компьютерное общество IEEE, Вашингтон, округ Колумбия, 544-553, том 2. дои : 10.1109/FSCS.1990.89575

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]