Jakub Kovac, Brona Brejova, Tomas Vinar.
A Practical Algorithm for Ancestral Rearrangement Reconstruction.
In Teresa M. Przytycka, Marie-France Sagot, ed.,
Algorithms in Bioinformatics, 11th International Workshop (WABI),
6833 volume of Lecture Notes in Computer Science,
pp. 163-174, Saarbrücken, Germany, September 2011. Springer.
Preprint, 450Kb | Download from publisher | Webpage | BibTeX
Genome rearrangements are a valuable source of information about early evolution, as well as an important factor in speciation processes. Reconstruction of ancestral gene orders on a phylogeny is thus one of the crucial tools contributing to understanding of evolution of genome organization. For most models of evolution, this problem is NP-hard. We have developed a universal method for reconstruction of ancestral gene orders by parsimony (PIVO) using an iterative local optimization procedure. Our method can be applied to different rearrangement models. Combined with a sufficiently rich model, such as the double cut and join (DCJ), it can support a mixture of different chromosomal architectures in the same tree. We show that PIVO can outperform previously used steinerization framework and achieves better results on real data than previously published methods. Datasets, reconstructed histories, and the software can be downloaded at http://compbio.fmph.uniba.sk/pivo/