• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computational Biology and Bioinformatics, IEEE/ACM Transactions on >Quartets MaxCut: A Divide and Conquer Quartets Algorithm
【24h】

Quartets MaxCut: A Divide and Conquer Quartets Algorithm

机译：四方MaxCut：分而治之四方算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Accurate phylogenetic reconstruction methods are currently limited to a maximum of few dozens of taxa. Supertree methods construct a large tree over a large set of taxa, from a set of small trees over overlapping subsets of the complete taxa set. Hence, in order to construct the tree of life over a million and a half different species, the use of a supertree method over the product of accurate methods, is inevitable. Perhaps the simplest version of this task that is still widely applicable, yet quite challenging, is quartet-based reconstruction. This problem lies at the root of many tree reconstruction methods and theoretical as well as experimental results have been reported. Nevertheless, dealing with false, conflicting quartet trees remains problematic. In this paper, we describe an algorithm for constructing a tree from a set of input quartet trees even with a significant fraction of errors. We show empirically that conflicts in the inputs are handled satisfactorily and that it significantly outperforms and outraces the Matrix Representation with Parsimony (MRP) methods that have previously been most successful in dealing with supertrees. Our algorithm is based on a divide and conquer algorithm where our divide step uses a semidefinite programming (SDP) formulation of MaxCut. We remark that this builds on previous work of ours [29] for piecing together trees from rooted triplet trees. The recursion for unrooted quartets, however, is more complicated in that even with completely consistent set of quartet trees the problem is NP-hard, as opposed to the problem for triples where there is a linear time algorithm. This complexity leads to several issues and some solutions of possible independent interest.
机译：目前，准确的系统发育重建方法仅限于几十个分类单元。超级树方法从整个分类单元集的重叠子集上的一组小树上，在一大类分类单元上构建一棵大树。因此，为了构建超过一百万个不同物种的生命之树，必然要在精确方法的产物上使用超树方法。仍然可以广泛应用但仍具有挑战性的此任务的最简单版本是基于四重奏的重建。这个问题是许多树木重建方法的根源，并且已经报道了理论和实验结果。然而，处理假的，冲突的四重奏树仍然存在问题。在本文中，我们描述了一种从一组输入四重奏树构造树的算法，即使有很大一部分错误也是如此。我们从经验上证明，输入中的冲突得到了令人满意的处理，并且显着优于并超越了以前在处理超级树方面最为成功的具有简约性的矩阵表示（MRP）方法。我们的算法基于分治法，其中分步使用MaxCut的半定性编程（SDP）公式。我们注意到，这是建立在我们以前的工作中[29]的，该工作是将有根三联体树中的树拼接在一起。但是，无根四重奏的递归更为复杂，因为即使具有完全一致的四重奏树集，该问题也是NP难题，而不是存在线性时间算法的三重奏问题。这种复杂性导致可能产生独立利益的若干问题和解决方案。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号