Kodiranje bojama

Из Википедије, слободне енциклопедије

U informatici i teoriji grafova, metod kodiranja bojama efikasno pronalazi k-čvorova prostih puteva, k-čvorova ciklusa i druge podgrafove zadatog grafa koristeći algoritme verovatnoće. Ovaj metod pokazuje da se mnogi izomorfni problemi podgrafova (NP-kompletni problemi) mogu rešiti u polinomijalnom vremenu.

Teoriju i analizu metoda kodiranja bojama predložili su Noga Alon, Raphael Yuster, i Uri Zwick 1994. godine.

Vremenska složenost[уреди]

Sledeći rezultati mogu biti dobijeni metodom kodiranja bojama:

  • Za svaku konstantu k, ako graf G = (V, E) sadrži prost ciklus k, onda se takav ciklus može naći u:
    • O(V^\omega) očekivanom vremenu, ili
    • O(V^\omega \log V) vremenu najgoreg slučaja, gde je \omega eksponent množenja matrica.
  • Za svaku konstantu k, i svaki graf G = (V, E) koji je u nekoj netrivijalnoj familiji grafova, ako G sadrži prost ciklus veličine k, onda se takav ciklus može naći u:
    • O(V) očekivanom vremenu, ili
    • O(V \log V) vremenu najgoreg slučaja.
  • Ako graf G = (V, E) sadrži podgraf izomorfan ograničenom stabloširinskom grafu koji ima O(\log V) čvorova, onda se takav podgraf može pronaći u polinomijalnom vremenu.

Metod[уреди]

Da bi se pronašao podgraf H = (V_H, E_H) datog grafa G = (V, E), gde H može biti put ili ciklus, metoda kodiranja bojama počinje nasumičnim bojanjem svakog čvora grafa G sa k = |V_H| različitih boja, a zatim nalazi šarene kopije od H u obojenom grafu G. Graf je šaren ako je svaki čvor u njemu obojen različitim bojama. Ova metoda funkcionise ponavljanjem (1) nasumičnog bojanja grafa i (2) pronalaženjem šarene kopije traženog podgrafa pa će se traženi podgraf pronaći u procesu ponavljanja.

Pretpostavimo da H postaje šarena sa nekom ne-nula verovatnoćom p. Iz toga sledi da ako se nasumično bojanje ponavlja \tfrac{1}{p} puta, onda se očekuje da H postane šaren. Iako p ima malu vrednost, pokazano je da ako |V_H| = O(\log V), p je samo polinomijalno male vrednosti. Pretpostavimo ponovi da postoji algoritam takav da, dati graf G i bojanja koja označavaju svaki čvor grafa G jednom od k boja, nalazi šarenu kopiju H, ako ona postoji, za neko izvršno vreme O(r). Onda je očekivano vreme nalaženja kopije H u grafu G, ako ista postoji, iznosi O(\tfrac{r}{p}).

Primer[уреди]

Primer koji nalazi prost ciklus dužine k u grafu G = (V, E).

Nasumičnim bojanjem, svaki prost ciklus ima verovatnocu k!/k^k > \tfrac{1}{e^k} da postane šaren, kako postoji k^k različitih načina bojanja k čvorova puta, među kojima su k! šarenih pojavljivanja. Onda se algoritam (dole opisan), sa vremenom izvršavanja O(V^\omega) može koristiti da se pronađe šareni ciklus u nasumično obojanom grafu G. Zbog toga je potrebno e^k\cdot O(V^\omega) ukupnog vremena da se pronađe jednostavan ciklus dužine k grafa G.

Algoritam za traženje šarenog ciklusa radi tako što prvo pronalazi sve parove čvorova u V koji su povezani prostim putem dužine k − 1, zatim proverava da li su svaka dva čvora povezana. Pozivanjem funkcije za bojanje c: V\rightarrow \{1, \dots, k\} da oboji graf G, numerišu se svi skupovi boja \{1, \dots, k\} u dva potskupa C_1, C_2 svaki veličine k/2. Primeti se da V može biti podeljen na V_1 i V_2 shodno tome i G_1 i G_2 označavaju podgraf indukovanih V_1 i V_2 proporcijalno. Zatim se rekurzivno nalazi šareni put dužine k/2 - 1 u svakoj od G_1i G_2. Pretpostavimo da Bulove matrice A_1 i A_2 predstavljaju povezanost svakog para čvorova G_1 i G_2 šarenim putem, proporcijalno, i neka B bude matrica koja opisuje susedstva između čvorova V_1 i V_2. Bulov proizvod A_1BA_2 daje sve parove čvorova u V koji su povezani šarenim putem dužine k-1. Dakle, rekurzivni odnos množenja matrica je t(k) \le 2^k\cdot t(k/2), što obezbeđuje vreme izvršavanja 2^{O(k)}\cdot V^\omega \in O(V^\omega).

Kako ovaj algoritam pronalazi samo krajnje tačke šarenog puta, postoji i drugi algoritam od Alona i Naora koji pronalazi šarene puteve koji mogu izgrađivati sami sebe.

Otklanjanje slučajnosti[уреди]

Otklanjanje nasumičnosti kod kodiranja bojama podrazumeva nabrajanja mogućih boja grafa, takva da slučajnost kod bojanja više nije potrebna. Da bi ciljni podgraf H u grafu G bio otkriven, nabrajanje mora da sadrži bar jedan primer gde je H šaren. Da bi se ovo postiglo, dovoljno je da se nabraja k-savršenih familija F heš funkcija od \{1, 2, \dots, |V|\} to \{1, 2, \dots, k\}. Po definiciji, F je k-savršen za svaki podskup S od \{1, 2, \dots, |V|\} gde je |S| = k, postoji heš funkcija h\in F takva da je h: S \rightarrow \{1, 2, \dots, k\} savršena. Drugim rečima, mora postojati heš funkcija u F koja boji bilo kojih datih k čvorova sa k različitih boja.

Postoji nekoliko različitih pristupa da se izgradi tako savršena heš familija:

  1. Najbolju eksplicitnu konstrukciju napisali su: Moni Naor, Leonard J. Schulman i Aravind Srinivasan u kojoj se može dobiti familija veličine e^k k^{O(\log k)} \log |V|. Ovaj način ne zahteva da traženi podgraf postoji u originalnom problemu pronalaženja podgrafa.
  2. Drugu eksplicitnu konstrukciju napisali su Jeanette P. Schmidt i Alan Siegel. Ovde je porodica veličine 2^{O(k)}\log^2 |V|.
  3. Još jedna konstrukcija se pojavljuje u originalnom dokumentu Noge Alona. Prvo se napravi k-savršena familija, koja mapira \{1, 2, \dots, |V|\} do \{1, 2,\dots, k^2\}, zatim se napravi još jedna k-savršena familija koja mapira \{1, 2, \dots, k^2\} do \{1, 2, \dots, k\}. U prvom koraku, moguće je konstruisati familiju sa 2n\log k slučajnih bitova koji su gotovo 2\log k mudro nezavisni i prostor potreban za generisanje tih slučajnih bitova može biti mali k^{O(1)}\log |V|. U drugom koraku, su Jeanette P. Schmidt i Alan Siegel pokazali da veličina takve k-savršene familije može biti 2^{O(k)}. Shodno tome, komponovanjem k-savršene familije od oba koraka, može se dobiti k-savršena familija veličine 2^{O(k)}\log |V| koja mapira od \{1, 2, \dots, |V|\} do \{1, 2, \dots, k\}.

Upotreba[уреди]

Od skoro, kodiranje bojama privlači mnogo pažnje u polju bioinformatike. Jedan od primera je otkrivanje signalnih puteva u protein-protein interakciji. Drugi primer je da se otkrije i prebroji broj motiva u PPI. Proučavanjem oba omogućava dublje razumevanje sličnosti i razlika mnogih bioloških funkcija, procesa i struktura među organizmima.

Zbog velike količine prikupljenih podataka (o genima), potraga puteva i motiva može veoma dugo trajati. Međutim, korišćenjem kodiranja bojama, motivi ili signalni putevi sa k=O(\log n) čvorova u mreži G sa n čvorova vertices mogu se naći veoma efikasno, u polinomijalnom vremenu. To omogućava istraživanja složenijih i većih struktura u protein-protein interakcijama. Više detalja se može pronaći.

Literatura[уреди]

  • 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)