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: http://ceur-ws.org/Vol-1214/46.pdf
Related web page: http://compbio.fmph.uniba.sk/pivo/
Bibliography entry: 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/.
Last modified: 02.12.2014
Contact: Tomáš Vinař, KAI FMFI UK, Mlynská Dolina, 84248 Bratislava, Slovakia
Broňa Brejová, KI FMFI UK, Mlynská Dolina, 84248 Bratislava, Slovakia
Office: M-163 Phone: +421(2)60295207
E-mail: 