Faster Exact Computation of rSPR Distance via Better Approximation
Faster Exact Computation of rSPR Distance via Better Approximation
复制标题
DOI：
10.1109/tcbb.2018.2878731
复制
发表时间：
2020-05-01
影响因子：
4.5
通讯作者：
Wang，Lusheng
中科院分区：
文献类型：
--
作者：
Chen，Zhi-Zhong;Harada，Youta;Wang，Lusheng
由于进化中的杂交事件，研究一组物种的两个不同基因可能会产生该组物种的两个相关但不同的系统发育树。在这种情况下，我们想要测量两棵树的差异。两棵树的有根子树修剪和重新移植（rSPR）距离已用于此目的。计算两棵给定树的 rSPR 距离的问题有很多应用，但属于 NP 难题。因此，已经开发了许多程序来精确地或近似地解决该问题。在本文中，我们开发了两个新程序，其中一个精确地解决了该问题，并且显着优于先前的最佳程序（即 Whidden 等人的 rSPR-v1.3.0），而另一个程序则近似地解决了该问题，并且在两个给定树的 rSPR 距离上输出明显优于 Schalekamp 等人的先前最佳程序的下限和上限。我们的程序可以从 http://rnc.r.dendai.ac.jp/rspr.html 下载。
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. The problem of computing the rSPR distance of two given trees has many applications but is NP-hard. Accordingly, a number of programs have been developed for solving the problem either exactly or approximately. In this paper, we develop two new programs, one of which solves the problem exactly and outperforms the previous best (namely, Whidden et al.'s rSPR-v1.3.0) significantly, while the other solves the problem approximately and outputs significantly better lower and upper bounds on the rSPR distance of the two given trees than the previous best due to Schalekamp et al. Our programs can be downloaded at http://rnc.r.dendai.ac.jp/rspr.html.