Broňa Brejová, Askar Gafurov, Dana Pardubska, Michal Sabo and Tomas Vinar. Isometric Gene Tree Reconciliation Revisited. In Algorithms in Bioinformatics (WABI), 2016. Accepted.

Download preprint: not available

Download from publisher: not available

Related www page: not available

Bibliography entry: BibTeX

Abstract:

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. 2008 in the
context of reconstructing evolutionary histories of genomes in
infinite sites model. 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. Moreover, by
adapting a data structure by Amir et al. 2007, we were able to improve
running time from \$O(mn)\$ to \$O(n+mlog m)\$, where \$n\$ is the size of
the species tree, and \$m\$ is the size of the gene tree.

Last update: 06/02/2016