MULTIPLE ALIGNMENT OF NUCLEOTIDE OR PROTEIN SEQUENCES

Hkratna poravnava več DNK ali proteinskih zaporedij je eno najpogostejših opravil na področju bioinformatike. Uporabna je za filogenetsko analizo, detekcijo homologije med sekvenciranim genom in obstoječo družino genov ter za napovedovanje strukture proteinov. Uporaba eksaktnega algoritma je zaradi eksponentne zahtevnosti problema v praksi nemogoča. Namen tega dela je preučitev računalniških hevrističnih algoritmov, ki so se razširili kot alternativa ročni poravnavi več zaporedij. V okviru tega sta bila implementirana in ocenjena dva algoritma, ki sta se že v osnovni različici izkazala za dovolj natančna in učinkovita za uporabo na realnih zaporedjih. V delu so predstavljeni rezultati testiranja algoritmov ter nadaljnje možnosti raziskovanja.The simultaneous alignment of a number of DNA or protein sequences is one of the most common tasks in bioinformatics. It is useful for phylogenetic analysis, detection of homology between a newly sequenced gene and an existing gene family and for prediction of protein structure. The use of an exact algorithm is practically impossible due to the exponential nature of the problem. The goal of this work is to study several heuristic computer algorithms that have emerged as an alternative to manual alignment construction. Two algorithms have been implemented and evaluated. They have been considered effective enough for construction of real-life multiple sequence alignments. Test results are shown and suggestions for further studies are given