Faster exact computation of rSPR distance
Faster exact computation of rSPR distance
复制标题
DOI：
10.1007/s10878-013-9695-8
复制
发表时间：
2013-12
影响因子：
1
通讯作者：
Zhi-Zhong Chen;Ying Fan;Lusheng Wang
中科院分区：
文献类型：
--
作者：
Zhi-Zhong Chen;Ying Fan;Lusheng Wang
由于进化中的杂交事件，研究一组物种的两个不同基因可能会产生两个相关但不同的物种系统发育树。在这种情况下，我们要测量两棵树的相异性。有根的子树修剪和嫁接（rSPR）的两棵树的距离已被用于此目的，许多算法和软件工具已被开发用于计算两个给定的系统发育树的rSPR距离。以前最快的精确算法为这个问题运行的时间，其中和是叶数和输入树的rSPR距离，分别。在本文中，我们提出了一个更快的精确算法，运行时间。我们的实验表明，新算法是显着快于最新版本（即v1.1.1）的以前最好的软件（即rSPR）的RSPR距离。
Due to hybridization events in evolution, studying two different genes of a set of species may yield two related but different phylogenetic trees for the set of species. In this case, we want to measure the dissimilarity of the two trees. The rooted subtree prune and regraft (rSPR) distance of the two trees has been used for this purpose, and many algorithms and software tools have been developed for computing the rSPR distance of two given phylogenetic trees. The previously fastest exact algorithm for this problem runs intime, whereandare the number of leaves and the rSPR distance of the input trees, respectively. In this paper, we present a faster exact algorithm which runs intime. Our experiments show that the new algorithm is significantly faster than the newest version (namely, v1.1.1) of the previously best software (namely,rSPR) for RSPR distance.