Center for Integrative Bioinformatics Vienna, Max F, Perutz Laboratories, University of Vienna, Medical University of Vienna, University of Veterinary Medicine Vienna, Dr. Bohr-Gasse 9, A-1030 Vienna, Austria.
BMC Evol Biol. 2011 Jul 13;11:205. doi: 10.1186/1471-2148-11-205.
Supertree methods combine overlapping input trees into a larger supertree. Here, I consider split-based supertree methods that first extract the split information of the input trees and subsequently combine this split information into a phylogeny. Well known split-based supertree methods are matrix representation with parsimony and matrix representation with compatibility. Combining input trees on the same taxon set, as in the consensus setting, is a well-studied task and it is thus desirable to generalize consensus methods to supertree methods.
Here, three variants of majority-rule (MR) supertrees that generalize majority-rule consensus trees are investigated. I provide simple formulas for computing the respective score for bifurcating input- and supertrees. These score computations, together with a heuristic tree search minmizing the scores, were implemented in the python program PluMiST (Plus- and Minus SuperTrees) available from http://www.cibiv.at/software/plumist. The different MR methods were tested by simulation and on real data sets. The search heuristic was successful in combining compatible input trees. When combining incompatible input trees, especially one variant, MR(-) supertrees, performed well.
The presented framework allows for an efficient score computation of three majority-rule supertree variants and input trees. I combined the score computation with a heuristic search over the supertree space. The implementation was tested by simulation and on real data sets and showed promising results. Especially the MR(-) variant seems to be a reasonable score for supertree reconstruction. Generalizing these computations to multifurcating trees is an open problem, which may be tackled using this framework.
Supertree 方法将重叠的输入树组合成一个更大的 Supertree。在这里，我考虑基于分裂的 Supertree 方法，该方法首先提取输入树的分裂信息，然后将该分裂信息合并到一个系统发育中。著名的基于分裂的 Supertree 方法是基于矩阵的简约法和基于矩阵的相容性法。在相同的分类单元集上组合输入树，就像共识设置一样，是一个经过充分研究的任务，因此将共识方法推广到 Supertree 方法是可取的。
这里研究了三种基于多数规则 (MR) 的 Supertree 变体，这些变体可以推广到多数规则共识树。我提供了计算分支输入树和 Supertree 各自得分的简单公式。这些得分计算，以及最小化得分的启发式树搜索，都在 python 程序 PluMiST（Plus- 和 Minus SuperTrees）中实现，该程序可从 http://www.cibiv.at/software/plumist 获得。通过模拟和真实数据集对不同的 MR 方法进行了测试。搜索启发式方法在组合相容的输入树时是成功的。当组合不相容的输入树时，特别是一种变体，MR(-) Supertrees，表现良好。
所提出的框架允许对三种基于多数规则的 Supertree 变体和输入树进行高效的得分计算。我将得分计算与 Supertree 空间的启发式搜索相结合。该实现通过模拟和真实数据集进行了测试，结果很有前景。特别是 MR(-) 变体似乎是 Supertree 重建的一个合理得分。将这些计算推广到多叉树是一个开放的问题，可能可以使用这个框架来解决。
