Кодирање бојама

У информатици и теорији графова, метод кодирања бојама ефикасно проналази к-чворова простих путева, к-чворова циклуса и друге подграфове задатог графа користећи алгоритме вероватноће. Овај метод показује да се многи изоморфни проблеми подграфова (НП-комплетни проблеми) могу решити у полиномијалном времену.

Теорију и анализу метода кодирања бојама предложили су Нога Алон, Рапхаел Yустер, и Ури Зwицк 1994. године.

Временска сложеност

Следећи резултати могу бити добијени методом кодирања бојама:

• За сваку константу $k$, ако граф $G=(V,E)$ садржи прост циклус $k$, онда се такав циклус може наћи у:
  • О($V^{\omega }$) очекиваном времену, или
  • О($V^{\omega }\log V$) времену најгорег случаја, где је $\omega$ експонент множења матрица.
• За сваку константу $k$, и сваки граф $G=(V,E)$ који је у некој нетривијалној фамилији графова, ако $G$ садржи прост циклус величине $k$, онда се такав циклус може наћи у:
  • О($V$) очекиваном времену, или
  • О($V\log V$) времену најгорег случаја.
• Ако граф $G=(V,E)$ садржи подграф изоморфан ограниченом стаблоширинском графу који има $O(\log V)$ чворова, онда се такав подграф може пронаћи у полиномијалном времену.

Метод

Да би се пронашао подграф $H=(V_{H},E_{H})$ датог графа $G=(V,E)$, где $H$ може бити пут или циклус, метода кодирања бојама почиње насумичним бојањем сваког чвора графа $G$ са $k=|V_{H}|$ различитих боја, а затим налази шарене копије од $H$ у обојеном графу $G$. Граф је шарен ако је сваки чвор у њему обојен различитим бојама. Ова метода функционисе понављањем (1) насумичног бојања графа и (2) проналажењем шарене копије траженог подграфа па ће се тражени подграф пронаћи у процесу понављања.

Претпоставимо да $H$ постаје шарена са неком не-нула вероватноћом $p$. Из тога следи да ако се насумично бојање понавља ${\tfrac {1}{p}}$ пута, онда се очекује да $H$ постане шарен. Иако $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}>{\tfrac {1}{e^{k}}}$ да постане шарен, како постоји $k^{k}$ различитих начина бојања $k$ чворова пута, међу којима су $k!$ шарених појављивања. Онда се алгоритам (доле описан), са временом извршавања $O(V^{\omega })$ може користити да се пронађе шарени циклус у насумично обојаном графу $G$. Због тога је потребно $e^{k}\cdot O(V^{\omega })$ укупног времена да се пронађе једноставан циклус дужине $k$ графа $G$.

Алгоритам за тражење шареног циклуса ради тако што прво проналази све парове чворова у V који су повезани простим путем дужине к − 1, затим проверава да ли су свака два чвора повезана. Позивањем функције за бојање $c:V\rightarrow \{1,\dots ,k\}$ да обоји граф $G$, нумеришу се сви скупови боја $\{1,\dots ,k\}$ у два потскупа $C_{1}$, $C_{2}$ сваки величине $k/2$. Примети се да $V$ може бити подељен на $V_{1}$ и $V_{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)\leq 2^{k}\cdot t(k/2)$, што обезбеђује време извршавања $2^{O(k)}\cdot V^{\omega }\in O(V^{\omega })$.

Како овај алгоритам проналази само крајње тачке шареног пута, постоји и други алгоритам од Алона и Наора који проналази шарене путеве који могу изграђивати сами себе.

Отклањање случајности

Отклањање насумичности код кодирања бојама подразумева набрајања могућих боја графа, таква да случајност код бојања више није потребна. Да би циљни подграф $H$ у графу $G$ био откривен, набрајање мора да садржи бар један пример где је $H$ шарен. Да би се ово постигло, довољно је да се набраја $k$-савршених фамилија $F$ хеш функција од $\{1,2,\dots ,|V|\}$ то $\{1,2,\dots ,k\}$. По дефиницији, $F$ је к-савршен за сваки подскуп $S$ од $\{1,2,\dots ,|V|\}$ где је $|S|=k$, постоји хеш функција $h\in F$ таква да је $h:S\rightarrow \{1,2,\dots ,k\}$ савршена. Другим речима, мора постојати хеш функција у $F$ која боји било којих датих $k$ чворова са $k$ различитих боја.

Постоји неколико различитих приступа да се изгради тако савршена хеш фамилија:

1. Најбољу експлицитну конструкцију написали су: Мони Наор, Леонард Ј. Сцхулман и Аравинд Сринивасан у којој се може добити фамилија величине $e^{k}k^{O(\log k)}\log |V|$. Овај начин не захтева да тражени подграф постоји у оригиналном проблему проналажења подграфа.
2. Другу експлицитну конструкцију написали су Јеанетте П. Сцхмидт и Алан Сиегел. Овде је породица величине $2^{O(k)}\log ^{2}|V|$.
3. Још једна конструкција се појављује у оригиналном документу Ноге Алона. Прво се направи к-савршена фамилија, која мапира $\{1,2,\dots ,|V|\}$ до $\{1,2,\dots ,k^{2}\}$, затим се направи још једна к-савршена фамилија која мапира $\{1,2,\dots ,k^{2}\}$ до $\{1,2,\dots ,k\}$. У првом кораку, могуће је конструисати фамилију са $2n\log k$ случајних битова који су готово $2\log k$ мудро независни и простор потребан за генерисање тих случајних битова може бити мали $k^{O(1)}\log |V|$. У другом кораку, су Јеанетте П. Сцхмидт и Алан Сиегел показали да величина такве $k$-савршене фамилије може бити $2^{O(k)}$. Сходно томе, компоновањем $k$-савршене фамилије од оба корака, може се добити $k$-савршена фамилија величине $2^{O(k)}\log |V|$ која мапира од $\{1,2,\dots ,|V|\}$ до $\{1,2,\dots ,k\}$.

Употреба

Од скоро, кодирање бојама привлачи много пажње у пољу биоинформатике. Један од примера је откривање сигналних путева у протеин-протеин интеракцији. Други пример је да се открије и преброји број мотива у ППИ. Проучавањем оба омогућава дубље разумевање сличности и разлика многих биолошких функција, процеса и структура међу организмима.

Због велике количине прикупљених података (о генима), потрага путева и мотива може веома дуго трајати. Међутим, коришћењем кодирања бојама, мотиви или сигнални путеви са Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/sr.wikipedia.org/v1/":): {\displaystyle k=O(\log n)} чворова у мрежи $G$ са $n$ чворова вертицес могу се наћи веома ефикасно, у полиномијалном времену. То омогућава истраживања сложенијих и већих структура у протеин-протеин интеракцијама. Више детаља се може пронаћи.

Литература

• Alon, N., Yuster, R., and Zwick, U. 1994. Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. In Proceedings of the Twenty-Sixth Annual ACM Symposium on theory of Computing (Montreal, Quebec, Canada, May 23–25, 1994)
• Alon, N., Yuster, R., and Zwick, U. 1995. Color-coding. J. ACM 42, 4 (Jul. 1995)
• Coppersmith–Winograd Algorithm
• Naor, M., Schulman, L. J., and Srinivasan, A. 1995. Splitters and near-optimal derandomization. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (October 23–25, 1995)
• Schmidt, J. P. and Siegel, A. 1990. The spatial complexity of oblivious k-probe Hash functions. SIAM J. Comput. 19, 5 (Sep. 1990)
• Naor, J. and Naor, M. 1990. Small-bias probability spaces: efficient constructions and applications. In Proceedings of the Twenty-Second Annual ACM Symposium on theory of Computing (Baltimore, Maryland, United States, May 13–17, 1990)
• Alon, N., Dao, P., Hajirasouliha, I., Hormozdiari, F., and Sahinalp, S. C. 2008. Biomolecular network motif counting and discovery by color coding. Bioinformatics 24, 13 (Jul. 2008)
• Hüffner, F., Wernicke, S., and Zichner, T. 2008. Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection. Algorithmica 52, 2 (Aug. 2008)