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
, ako graf
sadrži prost ciklus
, onda se takav ciklus može naći u:
- O(
) očekivanom vremenu, ili
- O(
) vremenu najgoreg slučaja, gde je
eksponent množenja matrica.
- O(
- Za svaku konstantu
, i svaki graf
koji je u nekoj netrivijalnoj familiji grafova, ako
sadrži prost ciklus veličine
, onda se takav ciklus može naći u:
- O(
) očekivanom vremenu, ili
- O(
) vremenu najgoreg slučaja.
- O(
- Ako graf
sadrži podgraf izomorfan ograničenom stabloširinskom grafu koji ima
čvorova, onda se takav podgraf može pronaći u polinomijalnom vremenu.
Metod
Da bi se pronašao podgraf datog grafa
, gde
može biti put ili ciklus, metoda kodiranja bojama počinje nasumičnim bojanjem svakog čvora grafa
sa
različitih boja, a zatim nalazi šarene kopije od
u obojenom grafu
. 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 postaje šarena sa nekom ne-nula verovatnoćom
. Iz toga sledi da ako se nasumično bojanje ponavlja
puta, onda se očekuje da
postane šaren. Iako
ima malu vrednost, pokazano je da ako
,
je samo polinomijalno male vrednosti. Pretpostavimo ponovi da postoji algoritam takav da, dati graf
i bojanja koja označavaju svaki čvor grafa
jednom od
boja, nalazi šarenu kopiju
, ako ona postoji, za neko izvršno vreme
. Onda je očekivano vreme nalaženja kopije
u grafu
, ako ista postoji, iznosi
.
Primer
Primer koji nalazi prost ciklus dužine u grafu
.
Nasumičnim bojanjem, svaki prost ciklus ima verovatnocu da postane šaren, kako postoji
različitih načina bojanja
čvorova puta, među kojima su
šarenih pojavljivanja. Onda se algoritam (dole opisan), sa vremenom izvršavanja
može koristiti da se pronađe šareni ciklus u nasumično obojanom grafu
. Zbog toga je potrebno
ukupnog vremena da se pronađe jednostavan ciklus dužine
grafa
.
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 da oboji graf
, numerišu se svi skupovi boja
u dva potskupa
,
svaki veličine
. Primeti se da
može biti podeljen na
i
shodno tome i
i
označavaju podgraf indukovanih
i
proporcijalno. Zatim se rekurzivno nalazi šareni put dužine
u svakoj od
i
. Pretpostavimo da Bulove matrice
i
predstavljaju povezanost svakog para čvorova
i
šarenim putem, proporcijalno, i neka
bude matrica koja opisuje susedstva između čvorova
i
. Bulov proizvod
daje sve parove čvorova u
koji su povezani šarenim putem dužine
. Dakle, rekurzivni odnos množenja matrica je
, što obezbeđuje vreme izvršavanja
.
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 u grafu
bio otkriven, nabrajanje mora da sadrži bar jedan primer gde je
šaren. Da bi se ovo postiglo, dovoljno je da se nabraja
-savršenih familija
heš funkcija od
to
. Po definiciji,
je k-savršen za svaki podskup
od
gde je
, postoji heš funkcija
takva da je
savršena. Drugim rečima, mora postojati heš funkcija u
koja boji bilo kojih datih
čvorova sa
različitih boja.
Postoji nekoliko različitih pristupa da se izgradi tako savršena heš familija:
- Najbolju eksplicitnu konstrukciju napisali su: Moni Naor, Leonard J. Schulman i Aravind Srinivasan u kojoj se može dobiti familija veličine
. Ovaj način ne zahteva da traženi podgraf postoji u originalnom problemu pronalaženja podgrafa.
- Drugu eksplicitnu konstrukciju napisali su Jeanette P. Schmidt i Alan Siegel. Ovde je porodica veličine
.
- Još jedna konstrukcija se pojavljuje u originalnom dokumentu Noge Alona. Prvo se napravi k-savršena familija, koja mapira
do
, zatim se napravi još jedna k-savršena familija koja mapira
do
. U prvom koraku, moguće je konstruisati familiju sa
slučajnih bitova koji su gotovo
mudro nezavisni i prostor potreban za generisanje tih slučajnih bitova može biti mali
. U drugom koraku, su Jeanette P. Schmidt i Alan Siegel pokazali da veličina takve
-savršene familije može biti
. Shodno tome, komponovanjem
-savršene familije od oba koraka, može se dobiti
-savršena familija veličine
koja mapira od
do
.
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 čvorova u mreži
sa
č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)