Using Robinson-Foulds supertrees in divide-and-conquer phylogeny estimation

Xilin Yu, Thien Le, Sarah A. Christensen, Erin K. Molloy, Tandy J. WarnowAlgorithms Mol. Biol 2021 · DOI · OpenReview

TL;DR

This paper introduces Exact-RFS-2, the first polynomial-time algorithm for constructing an optimal Robinson-Foulds Supertree (RFS) from two input trees. This is a crucial step towards building statistically consistent and scalable phylogenetic trees using divide-and-conquer methods, a significant challenge in evolutionary biology.

What Problem Does This Paper Address?

Constructing the "Tree of Life," a comprehensive evolutionary tree of all known species, is a monumental task. Current methods struggle with the sheer scale of data, often relying on computationally expensive heuristics for NP-hard problems. A promising approach is "divide-and-conquer," where large datasets are broken into smaller subsets, trees are built for these subsets, and then merged using "supertree methods." However, the efficiency and statistical consistency of these pipelines depend heavily on the performance of the supertree merging step, especially when dealing with just two trees at a time. This paper addresses the need for an efficient and theoretically sound method for merging two phylogenetic trees, specifically focusing on the Robinson-Foulds Supertree (RFS) criterion, which is closely related to maximum likelihood methods.

Methods

The core contribution is the Exact-RFS-2 algorithm, a polynomial-time algorithm that finds an optimal RFS for two input binary trees. This algorithm is novel in its approach to efficiently combine information from two trees by:

  • Decomposing the problem: It focuses on the shared leaves (X) and the "extra subtrees" unique to each input tree.
  • Constructing an initial tree (Tinit): This tree is built to maximize the "split support score" for bipartitions not involving shared leaves.
  • Refining the tree: The algorithm then iteratively refines Tinit by incorporating bipartitions from the shared leaf set. This refinement process uses a weighted incompatibility graph and a maximum weight independent set algorithm to strategically add compatible bipartitions.
  • Theoretical guarantees: The paper proves that Exact-RFS-2 is polynomial in the number of leaves and the size of the shared leaf set. It also establishes that RFS is NP-hard for three or more trees, highlighting the significance of the two-tree solution.

Datasets

Not discussed in the paper. The paper focuses on algorithmic development and theoretical proofs, using example trees for illustration rather than large-scale datasets for evaluation.

Key Insights and Ideas

  • RFS for two trees is tractable: While RFS for multiple trees is NP-hard, the problem becomes solvable in polynomial time when restricted to just two input trees. This is a critical breakthrough for divide-and-conquer strategies.
  • Equivalence of RFS and Split Fit Supertree (SFS): The paper demonstrates that for binary trees, optimizing the Robinson-Foulds distance is equivalent to maximizing the "split support score." This equivalence simplifies the problem and allows for efficient solutions.
  • Divide-and-conquer with Exact-RFS-2 enables statistical consistency: By using the efficient Exact-RFS-2 algorithm within a divide-and-conquer framework (like DACTAL), the authors prove that the resulting phylogeny estimation method is statistically consistent under standard evolutionary models. This means that with enough data, the method is guaranteed to converge to the true evolutionary tree.
  • NP-hardness for three or more trees: The paper formally proves that extending the RFS problem to three or more trees makes it NP-hard, underscoring the computational barrier and the importance of the two-tree solution.

Key Results

  • Exact-RFS-2 algorithm: A polynomial-time algorithm (O(n²|X|)) for finding the optimal Robinson-Foulds Supertree of two binary trees.
  • NP-hardness proof: RFS for three or more trees is proven to be NP-hard.
  • Statistical consistency: The DACTAL-Exact-RFS-2 pipeline is shown to be statistically consistent for phylogeny estimation under various evolutionary models.
  • Equivalence: RFS and Split Fit Supertree (SFS) problems are shown to have the same optimal solutions for binary trees.

Limitations and Future Work

  • Focus on binary trees: The Exact-RFS-2 algorithm is specifically designed for binary input trees. While the paper discusses relaxed versions, the core algorithm assumes binary inputs.
  • Empirical evaluation: While the theoretical underpinnings are strong, the paper does not present extensive empirical evaluations on real biological datasets. Future work could involve comparing Exact-RFS-2-based pipelines with existing methods on large-scale datasets.
  • Extending to non-binary trees: Developing efficient algorithms for RFS on non-binary trees remains an open challenge.
  • Evaluating supertree methods in practice: The authors suggest that further research should focus on evaluating the utility and benefits of these theoretically sound supertree methods in practical phylogenetic inference scenarios.

Summary updated

Abstract

One of the Grand Challenges in Science is the construction of the Tree of Life, an evolutionary tree containing several million species, spanning all life on earth. However, the construction of the Tree of Life is enormously computationally challenging, as all the current most accurate methods are either heuristics for NP-hard optimization problems or Bayesian MCMC methods that sample from tree space. One of the most promising approaches for improving scalability and accuracy for phylogeny estimation uses divide-and-conquer: a set of species is divided into overlapping subsets, trees are constructed on the subsets, and then merged together using a “supertree method”. Here, we present Exact-RFS-2, the first polynomial-time algorithm to find an optimal supertree of two trees, using the Robinson-Foulds Supertree (RFS) criterion (a major approach in supertree estimation that is related to maximum likelihood supertrees), and we prove that finding the RFS of three input trees is NP-hard. Exact-RFS-2 is available in open source form on Github at https://github.com/yuxilin51/GreedyRFS .
BibTeX
@article{yu2021using,
  author = {Xilin Yu and Thien Le and Sarah A. Christensen and Erin K. Molloy and Tandy J. Warnow},
  title = {{Using Robinson-Foulds supertrees in divide-and-conquer phylogeny estimation}},
  journal = {Algorithms Mol. Biol.},
  year = {2021},
  doi = {10.1186/s13015-021-00189-2},
}
Figure