Fast Local Search for Unrooted Robinson-Foulds Supertrees
Fast Local Search for Unrooted Robinson-Foulds Supertrees
复制标题
DOI：
10.1109/tcbb.2012.47
复制
发表时间：
2012-07-01
影响因子：
4.5
通讯作者：
Fernandez-Baca, David
中科院分区：
文献类型：
--
作者：
Chaudhary, Ruchi;Burleigh, J. Gordon;Fernandez-Baca, David
输入树的集合的Robinson-Foulds（RF）超树是包含输入树中的所有物种的树，其与输入树的总RF距离最小。因此，RF超树与输入树中的最大分裂数一致。为有根和无根数据构造RF超树是NP难的。然而，有效的本地搜索算法已经被开发的限制的情况下，输入树和超树的根。我们描述了新的算法，基于边缘合同和细化（ECR）操作，消除了这一限制，从而扩大了RF超树的效用。我们的模拟和经验数据集上的实验结果表明，我们的无根局部搜索算法产生更好的超树比从MRP和根的RF算法获得的总RF输入树的距离方面，对于模拟数据，在RF距离到真正的树。
A Robinson-Foulds (RF) supertree for a collection of input trees is a tree containing all the species in the input trees that is at minimum total RF distance to the input trees. Thus, an RF supertree is consistent with the maximum number of splits in the input trees. Constructing RF supertrees for rooted and unrooted data is NP-hard. Nevertheless, effective local search heuristics have been developed for the restricted case where the input trees and the supertree are rooted. We describe new heuristics, based on the Edge Contract and Refine (ECR) operation, that remove this restriction, thereby expanding the utility of RF supertrees. Our experimental results on simulated and empirical data sets show that our unrooted local search algorithms yield better supertrees than those obtained from MRP and rooted RF heuristics in terms of total RF distance to the input trees and, for simulated data, in terms of RF distance to the true tree.