Split-based computation of majority-rule supertrees

Abstract

Background: 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.

Results: 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.

Conclusions: 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.

Figure 1

Example input- and supertree. Example supertree (a) and input tree (b) for distance computations. Both trees are identified by its split sets: = {AB|CDEFGH, ABC|DEFGH, ABCD|EFGH, FGH|ABCDE, GH|ABCDEF} and = {DF|CGH, GH|CDF} The supertree pruned to the taxa in is shown in (c). Thus d^- = 2. (d) shows a tree that results in an optimal distance of d⁺ = 4 and (e) shows a tree that results in an optimal distance of .

Figure 2

Distribution of inner splits with compatible input trees and 50% of the taxa deleted.

Figure 3

Results for incompatible input trees and n = 32. The distances are normalized by dividing by the maximal distances, that is, 2n - 6 for the RF distance and n - 3 for the other two distances. "Missing splits" is the proportion of splits that are in the model tree but not in the supertree and "Incorrect splits" are in the supertree but not in the model tree. The mean of the data is displayed by "+". Note the different scaling of the y-axes.

Figure 4

Results with sequence simulation. The mean of the data is displayed by "+".

Figure 5

Prokaryote trees. Reference tree for the bacteria is taken from Wu et al. [41]. Chlorobium tepidum is not present in [41] but is displayed at the position of the other Chlorobi. The Archaea are marked in turquoise. Full taxon names can be found in [40].

Figure 6

Modification of the supertree. The taxon set {A, B} is replaced by A'.