Albert Herencsár, Broňa Brejová . An Improved Algorithm for Ancestral Gene Order Reconstruction. In V. Kurkova, L. Bajer, V. Svatek, ed., Information Technologies - Applications and Theory (ITAT), number 1003 in CEUR-WS, pp. 46-53, Jasna, Slovakia, 2014.

Download preprint: not available

Download from publisher:

Related web page:

Bibliography entry: BibTeX


Genome rearrangements are large-scale mutations that change the
order and orientation of genes in genomes. In the small phylogeny
problem, we are given gene orders in several current species and
a phylogenetic tree representing their evolutionary history. Our
goal is to reconstruct gene orders in the ancestral species,
while minimizing the overall number of rearrangement operations
that had to occur during the evolution.

The small phylogeny problem is NP-hard for most genome
rearrangement models. We have designed a heuristic method for
solving this problem, building on ideas from an earlier tool PIVO
by Kováč et al 2011. Our tool, PIVO2, contains several
improvements, including randomization to select among potentially
many equally good candidates in a hill-climbing search and a more
efficient calculation of distances between gene orders. Using
PIVO2, we were able to discover better histories for two
biological data sets previously discussed in research literature.
The software can be found at