Brejová Broňa, Gafurov Askar, Pardubská Dana, Sabo Michal, Vinař Tomáš
Faculty of Mathematics, Physics, and Informatics, Comenius University, Mlynská dolina, 842 48 Bratislava, Slovakia.
Algorithms Mol Biol. 2017 Jun 13;12:17. doi: 10.1186/s13015-017-0108-x. eCollection 2017.
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.
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 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.
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.
等距基因树调和是一种基因树/物种树调和问题，其中基因树和物种树都包含分支长度，并且调和过程必须尊重这些分支长度。该问题由马等人于2008年在无限位点模型下重建基因组进化历史的背景中提出。
在本文中，我们表明马等人的原始算法是不正确的，并提出了一种改进算法来解决我们发现的问题。我们还将运行时间从[公式：见原文]改进到了[公式：见原文]，其中 是两个输入树中的节点总数。最后，我们研究了该问题的两个新变体：两个无根树的调和以及两个有根树调和过程中基因树分支长度的缩放。
我们为树的等距调和提供了几种新算法。该领域的一些问题仍然悬而未决；最重要的是允许分支长度进行不精确估计的问题扩展。
