Sorting by reversals, block interchanges, tandem duplications, and deletions
Background: Finding sequences of evolutionary operations that transform one genome into another is a classic problem in comparative genomics. While most of the genome rearrangement algorithms assume that there is exactly one copy of each gene in both genomes, this does not reflect the biological reality very well -most of the studied genomes contain duplicated gene content, which has to be removed before applying those algorithms. However,dealing with unequal gene content is a very challenging task, and only few algorithms allow operations like duplications and deletions. Almost all of these algorithms restrict these operations to have a fixed size.Results: In this paper, we present a heuristic algorithm to sort an ancestral genorne (with unique gene content) into a genome of a descendant (with arbitrary gene content) by reversals, block interchanges, tandem duplications, and deletions, where tandem duplications and deletions are of arbitrary size.Conclusions: Experimental results show that our algorithm finds sorting sequences that are close to an optimal sorting sequence when the ancestor and the descendant are closely related. The quality of the results decreases when the genomes get more diverged or the genome size increases. Nevertheless, the calculated distances give a good approximation of the true evolutionary distances.
Martin Bader
Institute of Theoretical Computer Science, Univerity of Ulm, 89069 Uim, Germany
国际会议
The 7th Asia-Pacific Bioinformatics Conference(第七届亚太生物信息学大会)
北京
英文
83-93
2009-01-01（万方平台首次上网日期，不代表论文的发表时间）