Triplet supertree heuristics for the tree of life

Abstract

Background: There is much interest in developing fast and accurate supertree methods to infer the tree of life. Supertree methods combine smaller input trees with overlapping sets of taxa to make a comprehensive phylogenetic tree that contains all of the taxa in the input trees. The intrinsically hard triplet supertree problem takes a collection of input species trees and seeks a species tree (supertree) that maximizes the number of triplet subtrees that it shares with the input trees. However, the utility of this supertree problem has been limited by a lack of efficient and effective heuristics.

Results: We introduce fast hill-climbing heuristics for the triplet supertree problem that perform a step-wise search of the tree space, where each step is guided by an exact solution to an instance of a local search problem. To realize time efficient heuristics we designed the first nontrivial algorithms for two standard search problems, which greatly improve on the time complexity to the best known (naïve) solutions by a factor of n and n2 (the number of taxa in the supertree). These algorithms enable large-scale supertree analyses based on the triplet supertree problem that were previously not possible. We implemented hill-climbing heuristics that are based on our new algorithms, and in analyses of two published supertree data sets, we demonstrate that our new heuristics outperform other standard supertree methods in maximizing the number of triplets shared with the input trees.

Conclusion: With our new heuristics, the triplet supertree problem is now computationally more tractable for large-scale supertree analyses, and it provides a potentially more accurate alternative to existing supertree methods.

Figure 1

Triplet supertree problem. Given an input profile of n species trees (T₁,..., T_n), the triplet supertree problem is to find a supertree that maximizes the triplet-similarity score. The score for a supertree is calculated by first decomposing trees into their corresponding triplet presentations, then counting the number of common triplets between the supertree and each input tree (S₁,..., S_n), and finally aggregating all the counts. The triplet-similarity score for the candidate supertree T with respect to the input profile is therefore ${\displaystyle {\sum }_{i=1}^n{S}_i}$.

Figure 2

Example of an RR operation. Depicted is an example of an RR operation where T' = RR_T(d). The original tree T is shown in (a). In (b), we first suppress the root node, and then introduce the new root node r above d. Finally we rearrange the tree so that r is at root, as in (c).

Figure 3

Example of a TBR operation. Depicted is an example of a TBR operation where T' = TBR_T(e, h, b). The original tree T is shown in (a). In (b), we first remove the edge above e, that is we prune the subtree T_e. Then we introduce a new node above h which will be the new root of the pruned subtree. We also introduce a new node above b – this is where we will reconnect the subtree back to T. Finally we rearrange the tree and obtain the resulting tree T' as in (c).