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.

Download preprint: not available

Download from publisher: http://dx.doi.org/10.1007/978-3-642-23038-7_15

Related www page: http://compbio.fmph.uniba.sk/pivo/

Bibliography entry: BibTeX

See also: early version

Abstract:

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/

Last update: 10/10/2013