Poravnavanje višestrukih sekvenci
Poravnavanje višestrukih sekvenci je poravnavanje sekvenci tri ili više bioloških sekvenci, generalno proteina, DNK, ili RNK. U mnogim slučajevima se podrazumeva da postoji evolucioni odnos između sekvenci koje se poravnavaju. Poravnavanja više sekvenci su polazna tačka za izučavanje homologije i dalju filogenetičku analizu. Vizuelni prikaz poravnavanja je ilustracija mutacija, poput promena jedne aminokiseline ili nukleotida, koje sa prikazane kao različita slova u datoj koloni poravnavanja. Vidne su i mutacije umetanja ili brisanja koje su prikazane kao crtice u jednoj ili više sekvenci. Poravnavanje višestrukih sekvenci se često koristi za procenjivanje konzervacije proteinskih domena, tercijarne i sekundarne strukture, i individualnih aminokiselina ili nukleotida.
Poravnavanje višestrukih sekvenci se isto tako odnosi na sam proces poravnavanja. Pošto je manuelno poravnavanje tri ili više sekvenci se biološki relevantnim dužinama nepraktično, računarski algoritmi se uvek koriste za formiranje i analizu poravnavanja. Poravnavanje višestrukih sekvenci zahteva sofisticiranije metodologije od poravnavanja para sekvenci, jer je ono računski kompleksnije. Većina programa za poravnavanje višestrukih sekvenci koristi heurističke metode umesto globalne optimizacije, jer je identifikacija optimalnog poravnavanja između više od nekolicine sekvenci umerene dužine izuzetno računski skupa.
Dinamičko programiranje i računarska kompleksnost
[уреди | уреди извор]Direktni metod za formiranje poravnavanja višestrukih sekvenci koristi tehnike dinamičkog programiranja za identifikaciju globalno optimalnih poravnavanja. Za proteine, ovaj metod obično koristi dve grupe parametara: penale praznina i supstitucione matrice za dodeljivanje vrednosti ili verovatniće poravnavanja svakog mogućeg para aminokiselina. Ovi parametri su bazirani na sličnosti hemijskih osobina aminokiselina i evolucionoj verovatnoći mutacije. Za nukleotidne sekvence se koriste slični penali praznina, ali su supstitucione matrice znatno jednostavnije, tipično se jedino identična preklapanja uzimaju u obzir. Parametri u supstitucionoj matrici mogu da budu bilo svi pozitivni, ili mešavina pozitivnih i negativnih u slučaju globalnog poravnavanja. U slučaju lokalnog poravnavanja oni moraju da budu pozitivni i negativni.[1]
Za n individualnih sekvenci, za primenu naivnog metoda je neophodno konstruisati n-dimenzioni ekvivalent matrice koja se formira u standardnom poravnavanju para sekvenci. Prostor pretrage se stoga eksponencijalno povećava sa povećanjem broja sekvenci i veoma je zavistan od dužine sekvenci. Naivnom algoritmu je potrebno O(DužinaNsekv) vreme da proizvede rezultat. Nalaženje globalnog optimuma za n sekvenci na ovaj način je NP-kompletan problem.[2][3][4]
Na bazi Karilo-Lipmanovog algoritma,[5] Alčal je uveo 1989. praktični metod koji koristi poravnavanja parova za ograničavanje n-dimenzionog prostora pretrage.[6] U ovom pristupu dinamički programirana poravnavanja parova se izvode za svaki par sekvenci upitnog seta, i pretražuje se jedino prostor u blizini n-dimenzionog preseka tih poravnavanja. Ovaj program optimizuje sumu svih parova slova u svakoj poziciji poravnavanja (takozvani parametar sume parova).[7]
Reference
[уреди | уреди извор]- ^ „Help with matrices used in sequence comparison tools”. European Bioinformatics Institute. Архивирано из оригинала 11. 03. 2010. г. Приступљено 3. 3. 2010.
- ^ Wang L, Jiang T (1994). „On the complexity of multiple sequence alignment”. J Comput Biol. 1 (4): 337—348. PMID 8790475. doi:10.1089/cmb.1994.1.337.
- ^ Just W (2001). „Computational complexity of multiple sequence alignment with SP-score”. J Comput Biol. 8 (6): 615—23. PMID 11747615. doi:10.1089/106652701753307511.
- ^ Elias, Isaac (2006). „Settling the intractability of multiple alignment”. J Comput Biol. 13 (7): 1323—1339. PMID 17037961. doi:10.1089/cmb.2006.13.1323.
- ^ Carrillo H, Lipman DJ,(1988) The Multiple Sequence Alignment Problem in Biology. SIAM Journal of Applied Mathematics, Vol.48, No. 5, 1073-1082
- ^ Lipman DJ, Altschul SF, Kececioglu JD (1989). „A tool for multiple sequence alignment”. Proc Natl Acad Sci U S A. 86 (12): 4412—4415. PMC 287279
. PMID 2734293. doi:10.1073/pnas.86.12.4412.
- ^ „Genetic analysis software”. National Center for Biotechnology Information. Приступљено 3. 3. 2010.
Literatura
[уреди | уреди извор]- Duret, L.; S. Abdeddaim (2000). „Multiple alignment for structural functional or phylogenetic analyses of homologous sequences”. Ур.: D. Higgins and W. Taylor. Bioinformatics sequence structure and databanks. Oxford: Oxford University Press.
- Notredame, C. (2002). „Recent progresses in multiple sequence alignment: a survey”. Pharmacogenomics. 31 (1): 131—144. PMID 11966409. doi:10.1517/14622416.3.1.131.
- Thompson, J. D.; F. Plewniak; O. Poch (1999). „A comprehensive comparison of multiple sequence alignment programs”. Nucleic Acids Research. 27 (13): 12682—2690. PMC 148477 . PMID 10373585. doi:10.1093/nar/27.13.2682.
- Wallace, I.M.; Blackshields G; Higgins DG. (2005). „Multiple sequence alignments”. Curr Opin Struct Biol. 15 (3): 261—266. PMID 15963889. doi:10.1016/j.sbi.2005.04.002.
- Notredame, C (2007). „Recent Evolutions of Multiple Sequence Alignment Algorithms”. PLOS Computational Biology. 8 (3): e123. PMC 1963500 . PMID 17784778. doi:10.1371/journal.pcbi.0030123.
Spoljašnje veze
[уреди | уреди извор]
- ExPASy Архивирано на сајту Wayback Machine (13. април 2010)
- Poravnavanje višestrukih sekvenci