Advancing Divide-And-Conquer Phylogeny Estimation Using Robinson-Foulds Supertrees

Xilin Yu, Thien Le, Sarah A. Christensen, Erin K. Molloy, Tandy J. Warnow

TL;DR

This paper introduces Exact-RFS-2, a novel polynomial-time algorithm for constructing optimal phylogenetic supertrees from two input trees using the Robinson-Foulds Supertree (RFS) criterion. This advancement is crucial for enabling statistically consistent and scalable divide-and-conquer approaches to building the Tree of Life, a grand challenge in biology.

What Problem Does This Paper Address?

Constructing the Tree of Life, which represents the evolutionary history of all species, is an immense computational challenge. Current accurate methods are either slow heuristics for NP-hard problems or computationally intensive Bayesian approaches. A promising strategy is "divide-and-conquer," where large datasets are broken into smaller, overlapping subsets, trees are built for these subsets, and then merged into a final supertree. However, the efficiency and statistical consistency of this approach heavily depend on the supertree method used for merging. Specifically, accurately and efficiently merging just two trees is a critical bottleneck. This paper addresses this by developing a fast and optimal method for merging two trees under the RFS criterion, a widely used metric related to maximum likelihood supertrees.

Methods

The core contribution is the Exact-RFS-2 algorithm, which efficiently computes the optimal Robinson-Foulds Supertree (RFS) for two input binary trees. This algorithm leverages a clever strategy of separating the problem into two independent optimization tasks: one related to "trivial" bipartitions (splits involving a single leaf) and another for "non-trivial" bipartitions. It constructs an initial "star tree" that maximizes the score for trivial bipartitions and then refines it to optimize the score for non-trivial bipartitions by constructing and solving a weighted incompatibility graph.

The paper also introduces GreedyRFS, a heuristic that extends Exact-RFS-2 to multiple trees by repeatedly merging pairs of trees using Exact-RFS-2 until a single supertree is formed.

The authors also prove that while finding the RFS of two trees is solvable in polynomial time, the problem becomes NP-hard for three or more trees.

Datasets

The paper does not introduce new benchmark datasets. Instead, it evaluates its methods using:

  • Simulated datasets: Used for testing the performance of Exact-RFS-2 in phylogenomic species tree estimation.
  • SMIDgen datasets: A subset of these datasets, with 500 species and varying numbers of source trees, were used to evaluate the GreedyRFS heuristic for supertree estimation. These datasets have been previously used in supertree method evaluations.

Key Insights and Ideas

  • RFS for two trees is tractable: The paper proves that finding an optimal RFS supertree for two input trees can be done efficiently in polynomial time, a significant theoretical breakthrough.
  • NP-hardness for three or more trees: Conversely, the problem becomes NP-hard when dealing with three or more input trees, highlighting the inherent complexity of supertree construction beyond pairs.
  • Divide-and-conquer can be statistically consistent: By providing an optimal and efficient method for merging two trees, Exact-RFS-2 enables divide-and-conquer pipelines to be provably statistically consistent under standard evolutionary models. This is a major step towards building the Tree of Life reliably.
  • Greedy approach shows promise: The GreedyRFS heuristic, which iteratively uses Exact-RFS-2, demonstrates better accuracy than existing methods like FastRFS, especially when the number of input trees is not excessively large.

Key Results

  • Exact-RFS-2: Achieves better RFS criterion scores than the leading heuristic (FastRFS) for two-tree merging in phylogenomic species tree estimation.
  • GreedyRFS: Outperforms FastRFS in terms of RFS criterion score when the number of source trees is small to moderate, suggesting its utility for larger supertree problems.
  • Theoretical guarantees: The DACTAL-DACTAL-Exact-RFS-2 pipeline is proven to be statistically consistent for unrooted tree topology estimation.

Limitations and Future Work

  • NP-hardness for >2 trees: The NP-hardness of RFS for three or more trees means that exact solutions for larger problems will remain computationally challenging. Heuristics like GreedyRFS are necessary but may not always find the absolute optimum.
  • Computational aspects: While the paper focuses on accuracy, a more thorough comparison of running times between methods would be beneficial, especially for large datasets.
  • Further heuristic development: The authors suggest exploring other heuristics that utilize Exact-RFS-2 beyond GreedyRFS.
  • Broader dataset evaluation: Additional studies with more simulated and biological datasets are recommended to further explore the performance of Exact-RFS-2 and GreedyRFS against other leading supertree methods.

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. We also present GreedyRFS (a greedy heuristic that operates by repeatedly using Exact-RFS-2 on pairs of trees, until all the trees are merged into a single supertree). We evaluate Exact-RFS-2 and GreedyRFS, and show that they have better accuracy than the current leading heuristic for RFS.
BibTeX
@inproceedings{yu2020advancing,
  author = {Xilin Yu and Thien Le and Sarah A. Christensen and Erin K. Molloy and Tandy J. Warnow},
  title = {{Advancing Divide-And-Conquer Phylogeny Estimation Using Robinson-Foulds Supertrees}},
  booktitle = {WABI},
  year = {2020},
  url = {https://openreview.net/forum?id=GxOwZo0Y3t},
}
Figure