NJMerge

NJMerge implements a divide-and-conquer extension of the Neighbor Joining algorithm to estimate large-scale phylogenetic trees by merging subset trees using a shared distance matrix.

Key Features:

• Divide-and-conquer framework: Splits the species set into pairwise disjoint subsets to enable scalable analysis.
• Subset tree construction: Constructs individual trees for each subset using a specified base method.
• Distance-matrix merging: Merges subset trees through an associated shared distance matrix.
• Polynomial-time NJ extension: Employs a polynomial-time extension of Neighbor Joining (NJ) for the merger step.
• Supertree avoidance: Circumvents NP-hard supertree estimation by using a shared distance matrix for combination.
• Statistical consistency: Maintains statistical consistency under certain evolutionary models.
• Multi-locus scalability: Validated on multi-locus datasets with up to 1000 species.
• Improves downstream methods: Can improve accuracy of Neighbor Joining and reduce computational time for ASTRAL-III, SVDquartets, and RAxML concatenation.
• Empirical reliability: In simulation studies it failed to return a tree in 11 out of 2560 test cases.

Scientific Applications:

• Large-scale phylogeny estimation: Estimating species trees for very large taxon sets, including datasets up to 1000 species.
• Species tree estimation from multi-locus data: Inferring species trees from multi-locus sequence datasets.
• Alternative to supertree pipelines: Combining subset trees without relying on NP-hard supertree optimization.
• Acceleration of species-tree methods: Reducing computational time for methods such as ASTRAL-III, SVDquartets, and RAxML concatenation while preserving accuracy.

Methodology:

Divide the species set into pairwise disjoint subsets, construct subset trees with a base method, and merge them using a shared distance matrix via a polynomial-time extension of Neighbor Joining (NJ) instead of supertree optimization.