Kodowanie kolorami

Ten artykuł dotyczy techniki projektowania algorytmów grafowych. Aby dowiedzieć się, jak używać kolorów do wyświetlania informacji, zobacz kody kolorów . W przypadku innych zastosowań zobacz Kod koloru (ujednoznacznienie) .

W informatyce i teorii grafów termin kodowanie kolorami odnosi się do techniki algorytmicznej , która jest przydatna w odkrywaniu motywów sieciowych . Na przykład można go użyć do wykrycia prostej ścieżki o długości k w danym grafie . Tradycyjny algorytm kodowania kolorami jest probabilistyczny , ale można go derandomizować bez większego narzutu w czasie wykonywania.

Kodowanie kolorami ma również zastosowanie do wykrywania cykli o określonej długości, a bardziej ogólnie do problemu izomorfizmu podgrafu ( problem NP-zupełny ), gdzie daje algorytmy czasu wielomianowego, gdy wzór podgrafu, który próbuje wykryć, ma ograniczona szerokość drzewa .

Metoda kodowania kolorami została zaproponowana i przeanalizowana w 1994 roku przez Nogę Alona , ​​Raphaela Yustera i Uri Zwicka .

Wyniki

Metodą kodowania kolorami można uzyskać następujące wyniki:

• Dla każdej ustalonej stałej k , jeśli wykres G = ( V , E ) zawiera prosty cykl o rozmiarze k , to taki cykl można znaleźć w:
  • ${\ Displaystyle O (| V | ^ {\ omega})}$ oczekiwany czas lub
  • ${\ Displaystyle O (| V | ^ {\ omega} \ log | V |)}$ czas w najgorszym przypadku, gdzie ω jest wykładnikiem mnożenia macierzy .
• Dla każdej ustalonej stałej k i każdego wykresu G = ( V , E ) należącego do dowolnej nietrywialnej rodziny grafów domkniętych drugorzędnych (np. graf planarny ), jeśli G zawiera prosty cykl o rozmiarze k , to taki cykl można znaleźć W:
  • O ( V ) przewidywany czas, lub
  • O ( V log V ) czas najgorszego przypadku.
• Jeśli graf G = ( V , E ) zawiera podgraf izomorficzny z grafem o ograniczonej szerokości drzewa , który ma wierzchołki O (log V ) , to taki podgraf można znaleźć w czasie wielomianowym .

Metoda

Aby rozwiązać problem znalezienia podwykresu na danym wykresie $H , mi H ) {\ Displaystyle H = (V_ {H},$ , gdzie H może być H = E_ { H } ( V ścieżka, cykl lub dowolny wykres o ograniczonej szerokości drzewa , gdzie ${\ Displaystyle | V_ {H} | = O (\ log | V |)}$ , metoda kodowania kolorami rozpoczyna się od losowego pokolorowania każdego wierzchołka G z $|}$ } kolorów, a następnie próbuje znaleźć kolorową kopię H w kolorowym G. Tutaj graf jest kolorowy, jeśli każdy jego wierzchołek jest pokolorowany odrębnym kolorem. Ta metoda polega na powtarzaniu (1) losowego kolorowania wykresu i (2) znajdowaniu kolorowej kopii podgrafu docelowego, a ostatecznie podgraf docelowy można znaleźć, jeśli proces zostanie powtórzony wystarczającą liczbę razy.

Załóżmy, że kopia H w G staje się kolorowa z pewnym niezerowym prawdopodobieństwem p . Natychmiast wynika z tego, że jeśli losowe kolorowanie powtórzy się 1 / p razy, to oczekuje się, że ta kopia stanie się kolorowa raz. Zauważ, że chociaż p jest małe, pokazano, że jeśli ${\ Displaystyle | V_ {H} | = O (\ log | V |)}$ , p jest tylko wielomianowo małe. Załóżmy ponownie, że istnieje algorytm taki, że mając dany graf G i kolorowanie, które odwzorowuje każdy wierzchołek G na jeden z k kolorów, znajduje kopię kolorowego H , jeśli taki istnieje, w pewnym czasie wykonywania O ( r ) . Wtedy oczekiwany czas na znalezienie kopii H w G , jeśli taka istnieje, to ${\ Displaystyle O ({\ tfrac {r} {p}})}$ .

Czasami pożądane jest również użycie bardziej ograniczonej wersji kolorystyki. Na przykład w kontekście wyszukiwania cykli w grafach planarnych możliwe jest opracowanie algorytmu, który znajduje dobrze pokolorowane cykle. Tutaj cykl jest dobrze pokolorowany, jeśli jego wierzchołki są pokolorowane kolejnymi kolorami.

Przykład

Przykładem może być znalezienie prostego cyklu o długości k w grafie G = ( V , E ) .

Stosując metodę kolorowania losowego, każdy prosty cykl ma prawdopodobieństwo ${\ Displaystyle k!/k ^ {k}> e ^ {-k}},$ aby stać się kolorowym, ponieważ istnieją sposoby kolorowania k wierzchołków k k $Displaystyle k ^ {k}}$ na cyklu, wśród których jest ${\ displaystyle k!}$ kolorowe zdarzenia. Następnie można użyć algorytmu (opisanego $sol$$) do$ losowo pokolorowanym wykresie w czasie , gdzie jest stała mnożenia macierzy. Dlatego potrzeba $,$ cykl k w .

Algorytm znajdowania kolorowych cykli najpierw znajduje wszystkie pary wierzchołków w V , które są połączone prostą ścieżką o długości k − 1 , a następnie sprawdza, czy dwa wierzchołki w każdej parze są połączone. Biorąc pod uwagę funkcję kolorowania c : V → {1, ..., k } do wykresu kolorów G , wylicz wszystkie partycje zbioru kolorów {1, ..., k } na dwa podzbiory C ₁ , C ₂ o rozmiarze ${\ displaystyle k/2}$ każdy. Zauważ, że V można odpowiednio podzielić na V ₁ i V ₂ i niech G ₁ i G ₂ oznaczają podgrafy indukowane odpowiednio przez V ₁ i V _{2 .} Następnie rekurencyjnie znajdź _kolorowe ścieżki o $sol$ każdym sol ₂ . Załóżmy, że macierze boolowskie A ₁ i A ₂ reprezentują łączność każdej pary wierzchołków w G ₁ i G ₂ odpowiednio kolorową ścieżką i niech B będzie macierzą opisującą relacje sąsiedztwa między wierzchołkami V ₁ i wierzchołkami V _{2 ,} $są$ logiczny daje wszystkie pary wierzchołków w V kolorową ścieżką o długości - 1 . Zatem rekurencyjna relacja mnożenia macierzy to , co daje ${\ Displaystyle t (k) \ równoważnik 2 ^ {k} \ cdot t (k/2)}$${\ Displaystyle 2 ^ {O (k)} \ cdot V ^ {\ omega} = O (V ^ {\ omega})$ } . Chociaż ten algorytm znajduje tylko punkty końcowe kolorowej ścieżki, można do niego włączyć inny algorytm Alona i Naora, który sam znajduje kolorowe ścieżki.

Derandomizacja

Derandomizacja kodowania kolorami polega na wyliczeniu możliwych kolorów grafu G , tak że losowość kolorowania G nie jest już wymagana . Aby docelowy podgraf H w G był wykrywalny, wyliczenie musi zawierać co najmniej jedno wystąpienie, w którym H jest kolorowy. Aby to osiągnąć, wyliczając k -perfekcyjną rodzinę F funkcji mieszających z {1, ..., | V |} do {1, ..., k } jest wystarczające. Z definicji F jest k -idealne, jeśli dla każdego podzbioru S z {1, ..., | V |} gdzie ${\ displaystyle | S | = k}$ , istnieje funkcja mieszająca h w F taka, że ​​h : S → {1, ..., k } jest doskonały . Innymi słowy, w F musi istnieć funkcja mieszająca , która koloruje dowolne k wierzchołków k różnymi kolorami.

Istnieje kilka podejść do skonstruowania takiej k -perfekcyjnej rodziny skrótów:

1. Najlepsza jawna konstrukcja jest autorstwa Moni Naora , Leonarda J. Schulmana i Aravinda Srinivasana, gdzie rodzina wielkości ${\ displaystyle e ^ {k} k ^ {O (\ log k)} \ log | V |} .$ można uzyskać Ta konstrukcja nie wymaga istnienia podgrafu docelowego w pierwotnym problemie ze znajdowaniem podgrafów.
2. Inna wyraźna konstrukcja autorstwa Jeanette P. Schmidt i Alana Siegela daje rodzinę o rozmiarze ${\ Displaystyle 2 ^ {O (k)} \ log ^ {2} | V |}$ .
3. Kolejna konstrukcja pojawiająca się w oryginalnej pracy Nogi Alon et al. można uzyskać budując najpierw k -perfekcyjną rodzinę, która odwzorowuje {1, ..., | V |} do {1, ..., k ² }, a następnie budujemy kolejną k -doskonałą rodzinę, która odwzorowuje {1, ..., k ² } na {1, ..., k }. W pierwszym kroku możliwe jest zbudowanie takiej rodziny z 2 n log k losowych bitów, które są prawie 2 log k niezależne, a przestrzeń próbki potrzebna do wygenerowania tych losowych bitów może być tak mała jak ${\ Displaystyle k ^ {O (1)} \ log | V |}$ . W drugim kroku Jeanette P. Schmidt i Alan Siegel wykazali, że wielkość takiej k - idealnej rodziny może wynosić ${\ Displaystyle 2 ^ {O (k)}}$ . W konsekwencji, składając k -doskonałe rodziny z obu etapów, k -doskonała rodzina o rozmiarze ${\ Displaystyle 2 ^ {O (k)} \ log | V |}$ odwzorowuje od {1, ..., | V |} Można otrzymać do {1, ..., k } .

W przypadku derandomizacji dobrego kolorowania, gdzie każdy wierzchołek na podgrafie jest kolejno kolorowany, k -doskonała rodzina funkcji mieszających z {1, ..., | V |} Potrzebne jest do {1, ..., k !} . Wystarczająca k - doskonała rodzina, która odwzorowuje od {1, ..., | V |} do {1, ..., k ^k } można skonstruować w sposób podobny do podejścia 3 powyżej (pierwszy krok). W szczególności odbywa się to za pomocą nk log k losowych bitów, które są prawie k log k niezależne, a rozmiar wynikowej k -doskonałej rodziny będzie wynosił ${\ Displaystyle k ^ {O (k)} \ log | V |}$ .

Derandomizację metody kodowania kolorami można łatwo zrównoleglić, uzyskując wydajne algorytmy NC .

Aplikacje

Ostatnio kodowanie kolorami przyciągnęło wiele uwagi w dziedzinie bioinformatyki. Jednym z przykładów jest wykrywanie szlaków sygnałowych w sieciach interakcji białko-białko (PPI). Innym przykładem jest odkrycie i policzenie liczby motywów w sieciach PPI. Badanie zarówno ścieżek sygnałowych , jak i motywów pozwala na głębsze zrozumienie podobieństw i różnic wielu funkcji, procesów i struktur biologicznych między organizmami.

Ze względu na ogromną ilość danych genów, które można zebrać, poszukiwanie ścieżek lub motywów może być bardzo czasochłonne. Jednak wykorzystując metodę kodowania kolorami, motywy lub ścieżki sygnałowe z wierzchołkami w sieci G z n wierzchołkami można znaleźć bardzo wydajnie w ${\ Displaystyle k = O (\ log n)}$ czas wielomianowy. Dzięki temu możemy badać bardziej złożone lub większe struktury w sieciach PPI.

Dalsza lektura

•    Alon, N.; Dao, P.; Hajirasouliha, I.; Hormozdiari, F.; Sahinalp, SC (2008). „Liczenie i odkrywanie motywów sieci biomolekularnej za pomocą kodowania kolorami” . Bioinformatyka . 24 (13): i241-i249. doi : 10.1093/bioinformatyka/btn163 . PMC 2718641 . PMID 18586721 .
•    Hüffner, F.; Wernicke, S.; Zichner, T. (2008). „Inżynieria algorytmiczna do kodowania kolorami z aplikacjami do wykrywania ścieżki sygnalizacyjnej”. Algorytmika . 52 (2): 114–132. CiteSeerX 10.1.1.68.9469 . doi : 10.1007/s00453-007-9008-7 . S2CID 81069 .