TreeMerge

TreeMerge merges phylogenetic trees from disjoint species subsets to enable scalable multi-locus species tree estimation using a divide-and-conquer strategy and a full-set distance matrix.

Key Features:

• Guaranteed output: Unlike NJMerge, TreeMerge always returns a species tree.
• Computational efficiency: TreeMerge has O(n²) running time for n species, improving on the O(n⁵) complexity reported for NJMerge.
• Divide-and-conquer framework: TreeMerge divides the species set into smaller disjoint subsets, constructs trees on each subset, and merges them using information from the full species set to scale analyses to larger datasets.

Scientific Applications:

• Multi-locus species tree estimation: TreeMerge is applied to multi-locus datasets to produce species trees from large numbers of species and loci.
• Integration with ASTRAL-III and RAxML: TreeMerge was evaluated with ASTRAL-III and RAxML and enables these methods to complete analyses on datasets that would otherwise be computationally prohibitive given constraints such as 64 GB memory and a 48-hour maximum running time.

Methodology:

TreeMerge employs a divide-and-conquer approach: it partitions the species set into disjoint subsets, constructs phylogenetic trees for each subset independently, and combines the subset trees using an associated distance matrix computed on the full species set.