Poravnavanje višestrukih sekvenci
Poravnavanje višestrukih sekvenci je poravnavanje sekvenci tri ili više bioloških sekvenci, uglavnom proteina, DNK ili RNK. U mnogim slučajevima podrazumijeva se da postoji evolucjskii odnos između sekvenci koje se poravnavaju. Poravnavanja više sekvenci su polazna tačka za proučavanje homologije i dalju filogenetičku analizu. Vizuelni prikaz poravnavanja je ilustracija mutacija, kao što je promjena jedne aminokiseline ili nukleotida, koje sa prikazane kao različita slova u odgovarajućoj koloni poravnavanja. Vidne su i mutacije insercija ili delecija, koje su prikazane kao crtice u jednoj ili više sekvenci. Poravnavanje višestrukih sekvenci koristi se često za procjenu 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 ručno poravnavanje tri ili više sekvenci sa biološki relevantnim dužinama nepraktično, za formiranje i analizu poravnavanja uvijek se koriste računarski algoritmi . Poravnavanje višestrukih sekvenci počiva na sofisticiranijim metodima od poravnavanja para sekvenci, jer je ono računarski kompleksnije. Većina programa za poravnavanje višestrukih sekvenci koristi heurističke metode, umjesto globalne optimizacije, jer je identifikacija optimalnog poravnavanja između više od nekoliko sekvenci umjerene dužine, računarski izuzetno skupa.
Dinamičko programiranje i računarska kompleksnost
urediDirektni metod za poravnavanja višestrukih sekvenci koristi tehnike dinamičkog programiranja za identifikaciju globalno optimalnih poravnavanja. Za proteine, ovaj metod obično koristi dvije grupe parametara: penale praznina i supstitucijske matrice za dodijeljivanje vrednosti ili vjerovatnoće poravnavanja svakog mogućeg para aminokiselina. Ovi parametri su bazirani na sličnosti hemijskih osobina aminokiselina i evolucijskoj vjerovatnoći mutacije. Za nukleotidne sekvence koriste se slični penali praznina, ali su supstitucijske matrice znatno jednostavnije, tipski se posmatraju jedinoidentična preklapanja. Parametri u supstitucijskoj matrici mogu biti bilo svi pozitivni ili mješavina pozitivnih i negativnih, u slučaju globalnog poravnavanja. U slučaju lokalnog poravnavanja, moraju biti pozitivni i negativni.[1]
Za n individualnih sekvenci, uprimjeni naivnog metoda, neophodno je konstruitati n-dimenzijski 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 zavisan od dužine sekvenci. Naivnom algoritmu je potrebno O(dužinaNsekv) vrijeme da proizvede rezultat. Nalaženje globalnog optimuma za n sekvencu na ovaj način je NP-kompletan problem.[2][3][4]
Na bazi Karilo-Lipmanovog algoritma,[5] Altschul uveo je 1989. praktični metod koji koristi poravnavanja parova za ograničavanje n-dimenzijskog prostora pretrage.[6] U ovom pristupu, dinamički programirana poravnavanja parova izvode se za svaki par sekvenci upitnog seta i pretražuje se jedino prostor u blizini n-dimenzijskog presjeka tih poravnavanja. Ovaj program optimizira zbir svih parova slova u svakoj poziciji poravnavanja (takozvani parametar sume parova).[7]
Reference
uredi- ^ "Help with matrices used in sequence comparison tools". European Bioinformatics Institute. Arhivirano s originala, 11. 3. 2010. Pristupljeno 3. 3. 2010.
- ^ Wang L, Jiang T (1994). "On the complexity of multiple sequence alignment". J Comput Biol. 1 (4): 337–348. doi:10.1089/cmb.1994.1.337. PMID 8790475.
- ^ Just W (2001). "Computational complexity of multiple sequence alignment with SP-score". J Comput Biol. 8 (6): 615–23. doi:10.1089/106652701753307511. PMID 11747615.
- ^ Elias, Isaac (2006). "Settling the intractability of multiple alignment". J Comput Biol. 13 (7): 1323–1339. doi:10.1089/cmb.2006.13.1323. PMID 17037961.
- ^ -{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. doi:10.1073/pnas.86.12.4412. PMC 287279. PMID 2734293.
- ^ "Genetic analysis software". National Center for Biotechnology Information. Pristupljeno 3. 3. 2010.
Dopunska literatura
uredi- Duret, L.; S. Abdeddaim (2000). "Multiple alignment for structural functional or phylogenetic analyses of homologous sequences". u D. Higgins and W. Taylor (ured.). Bioinformatics sequence structure and databanks. Oxford: Oxford University Press.CS1 održavanje: ref=harv (link)
- Notredame, C. (2002). "Recent progresses in multiple sequence alignment: a survey". Pharmacogenomics. 31 (1): 131–144. doi:10.1517/14622416.3.1.131. PMID 11966409.
- Thompson, J. D.; F. Plewniak; O. Poch (1999). "A comprehensive comparison of multiple sequence alignment programs". Nucleic Acids Research. 27 (13): 12682–2690. doi:10.1093/nar/27.13.2682. PMC 148477. PMID 10373585.
- Wallace, I.M.; Blackshields G; Higgins DG. (2005). "Multiple sequence alignments". Curr Opin Struct Biol. 15 (3): 261–266. doi:10.1016/j.sbi.2005.04.002. PMID 15963889.
- Notredame, C (2007). "Recent Evolutions of Multiple Sequence Alignment Algorithms". PLOS Computational Biology. 8 (3): e123. doi:10.1371/journal.pcbi.0030123. PMC 1963500. PMID 17784778.
Vanjski linkovi
uredi- -{ExPASy}- Arhivirano 13. 4. 2010. na Wayback Machine
- [1]