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

Area of Science:

• Computational Biology
• Evolutionary Biology
• Bioinformatics

Background:

• The "Tree of Life" project aims to map evolutionary relationships for millions of species.
• Current methods for phylogenetic tree construction are computationally intensive, often involving NP-hard problems or complex sampling techniques.
• Divide-and-conquer strategies, using supertree methods to merge smaller trees, show promise for improving scalability and accuracy.

Purpose of the Study:

• To develop an efficient algorithm for supertree construction.
• To address the computational complexity of inferring evolutionary relationships.
• To provide a method for optimal supertree estimation under the Robinson-Foulds Supertree (RFS) criterion.

Main Methods:

• Development of Exact-RFS-2, a polynomial-time algorithm.
• Application of the Robinson-Foulds Supertree (RFS) criterion for supertree estimation.
• Theoretical analysis to determine the computational complexity of RFS for multiple trees.

Main Results:

• Exact-RFS-2 is the first polynomial-time algorithm to compute an optimal supertree for two input trees based on the RFS criterion.
• The study proves that computing the RFS for three input trees is an NP-hard problem.
• The Exact-RFS-2 algorithm is publicly available on GitHub.

Conclusions:

• The Exact-RFS-2 algorithm offers a significant advancement in efficiently constructing phylogenetic supertrees.
• Understanding the NP-hardness of the three-tree problem highlights the complexity of large-scale evolutionary inference.
• This work contributes to overcoming computational bottlenecks in building the Tree of Life.