Publication details

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

Abstract

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/.

Photo

Contact

Mailing address:
Bronislava Brejova
Katedra informatiky
FMFI UK
Mlynska Dolina
842 48 Bratislava
Slovakia

Office: M163

Phone: +421-2-60295217

E-mail: my_surname at dcs.fmph.uniba.sk