Statistically consistent divide-and-conquer pipelines for phylogeny estimation using NJMerge.

Area of Science:

• Computational Biology
• Phylogenetics
• Bioinformatics

Background:

• Divide-and-conquer methods enhance phylogeny estimation scalability for large datasets.
• Current supertree methods, often NP-hard, limit the scalability of these approaches.

Purpose of the Study:

• Introduce a novel divide-and-conquer strategy that bypasses supertree estimation.
• Present NJMerge, a polynomial-time method for combining disjoint subset trees.

Main Methods:

• Developed NJMerge, a polynomial-time extension of Neighbor Joining (NJ).
• Applied NJMerge in a divide-and-conquer framework using disjoint subsets and distance matrices.
• Evaluated NJMerge on multi-locus datasets with up to 1000 species.

Main Results:

• NJMerge demonstrated statistical consistency under certain evolutionary models.
• The method improved accuracy over traditional NJ in some cases.
• NJMerge substantially reduced running times for ASTRAL-III, SVDquartets, and RAxML concatenation without accuracy loss.
• NJMerge exhibited a low failure rate (11/2560 test cases).

Conclusions:

• NJMerge is a valuable technique for large-scale phylogeny estimation, particularly when computational resources are constrained.
• The method offers improved scalability and efficiency for phylogenetic analyses.
• NJMerge is publicly available on Github.