Institute of Evolution, University of Haifa, Haifa, Israel.
IEEE/ACM Trans Comput Biol Bioinform. 2010 Oct-Dec;7(4):704-18. doi: 10.1109/TCBB.2008.133.
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 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）。我们的算法基于一种分治算法，其中我们的划分步骤使用了最大切割的半定规划（SDP）公式。我们注意到，这是基于我们以前用于从有根三分体树中拼接树的工作。然而，对于无根四分体的递归更加复杂，即使对于完全一致的四分体树集，该问题也是 NP 难的，与用于三重体的问题相反，后者有一个线性时间算法。这种复杂性导致了几个问题和一些可能具有独立兴趣的解决方案。
