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 from publisher | Webpage | 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 http://compbio.fmph.uniba.sk/pivo/.