GreedyRFS

GreedyRFS constructs a binary Robinson-Foulds supertree by greedily merging binary source trees with overlapping leaf sets to produce a single binary supertree for large-scale phylogenetic estimation.

Key Features:

• Input and Output: Accepts a set of binary source trees with overlapping leaf sets and outputs a single binary supertree on the union of leaves.
• Heuristic Approach: Implements a greedy heuristic that iteratively selects and merges pairs of source trees guided by the Robinson-Foulds Supertree (RFS) criterion.
• Algorithmic Foundation: Uses Exact-RFS-2, a polynomial-time exact algorithm that computes an optimal RFS supertree for two input trees.
• Iterative Merging Process: Repeatedly merges selected tree pairs using Exact-RFS-2 until all input trees are consolidated into one supertree.
• Computational Efficiency: Leverages the polynomial-time pairwise optimality of Exact-RFS-2 to improve scalability relative to methods that solve NP-hard optimizations or rely on Bayesian MCMC sampling.

Scientific Applications:

• Large-scale phylogeny reconstruction: Applies to studies aiming to assemble comprehensive evolutionary trees such as the Tree of Life by merging overlapping subsets of species.
• Divide-and-conquer phylogeny pipelines: Serves to combine subset trees into a single global phylogeny to improve scalability and accuracy of phylogeny estimation.

Methodology:

Accepts binary source trees with overlapping leaf sets; repeatedly selects pairs of source trees according to a greedy criterion and merges each pair using Exact-RFS-2 (a polynomial-time exact solver for two-tree RFS), iterating until a single binary supertree on the union of leaves is produced.