Poravnavanje višestrukih sekvenci – razlika između verzija
Uklonjeni sadržaj Dodani sadržaj
m Bot: Brisanje šablona: Link GA. |
Rescuing 2 sources and tagging 0 as dead.) #IABot (v2.0.8 |
||
Red 6:
== Dinamičko programiranje i računarska kompleksnost ==
Direktni metod za formiranje poravnavanja višestrukih sekvenci koristi tehnike [[dinamičko programiranje|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.<ref>{{cite web | title=Help with matrices used in sequence comparison tools | publisher=European Bioinformatics Institute | url=http://www.ebi.ac.uk/help/matrix.html | accessdate
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žina<sup>Nsekv</sup>)'' vreme da proizvede rezultat. Nalaženje globalnog optimuma za ''n'' sekvenci na ovaj način je [[NP-kompletni problemi|NP-kompletan]] problem.<ref name="wang">{{cite journal | doi = 10.1089/cmb.1994.1.337 | author = Wang L, Jiang T | year = 1994 | title = On the complexity of multiple sequence alignment | url = | journal = J Comput Biol | volume = 1 | issue = 4| pages=337-348 | pmid = 8790475 }}</ref><ref name="just">{{cite journal | doi = 10.1089/106652701753307511 | author = Just W | year = 2001 | title = Computational complexity of multiple sequence alignment with SP-score | url = | journal = J Comput Biol | volume = 8 | issue = 6| pages=615-23 | pmid = 11747615 }}</ref><ref name=elias>{{cite journal | journal=J Comput Biol | volume=13 | pages=1323-1339 | year=2006 |last=Elias|first=Isaac| title=Settling the intractability of multiple alignment | url=http://www.liebertonline.com/doi/abs/10.1089/cmb.2006.13.1323 | pmid=17037961 | doi =10.1089/cmb.2006.13.1323 | issue=7 }}</ref>
Red 27:
{{portal|Informatika}}
* [http://www.expasy.org/tools/#align ExPASy]
* [http://www.techfak.uni-bielefeld.de/bcd/Curric/MulAli/welcome.html Poravnavanje višestrukih sekvenci] {{Webarchive|url=https://web.archive.org/web/20070630140847/http://www.techfak.uni-bielefeld.de/bcd/Curric/MulAli/welcome.html |date=2007-06-30 }}
[[Kategorija:Bioinformatika]]
| |||