Publication details

Broňa Brejová, Askar Gafurov, Dana Pardubská, Michal Sabo, Tomáš Vinař. Isometric gene tree reconciliation revisited. Algorithms for Molecular Biology, 12:17. 2017. Early version appeared at WABI 2016.
Download from publisher | Early version | BibTeX | PubMed

Abstract

BACKGROUND: Isometric gene tree reconciliation is a gene tree/species tree
reconciliation problem where both the gene tree and the species tree include
branch lengths, and these branch lengths must be respected by the reconciliation.
The problem was introduced by Ma et al. in 2008 in the context of reconstructing 
evolutionary histories of genomes in the infinite sites model. RESULTS: In this
paper, we show that the original algorithm by Ma et al. is incorrect, and we
propose a modified algorithm that addresses the problems that we discovered. We
have also improved the running time from [Formula: see text] to [Formula: see
text], where N is the total number of nodes in the two input trees. Finally, we
examine two new variants of the problem: reconciliation of two unrooted trees and
scaling of branch lengths of the gene tree during reconciliation of two rooted
trees. CONCLUSIONS: We provide several new algorithms for isometric
reconciliation of trees. Some questions in this area remain open; most
importantly extensions of the problem allowing for imprecise estimates of branch 
lengths.



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