Fast NJ-like algorithms to deal with incomplete distance matrices

Area of Science:

• Computational Biology
• Evolutionary Biology
• Bioinformatics

Background:

• Distance-based phylogeny inference is crucial but struggles with incomplete distance matrices, often arising in multi-gene studies.
• Existing methods for incomplete matrices are computationally expensive (O(n4) or more), limiting their application to large datasets.
• Agglomerative algorithms offer faster O(n3) complexity but typically cannot handle incomplete data.

Purpose of the Study:

• To adapt existing agglomerative phylogenetic algorithms for efficient handling of incomplete distance matrices.
• To develop new algorithms that maintain speed while improving accuracy on phylogenomic datasets with missing data.
• To evaluate the performance of these novel algorithms against existing methods.

Main Methods:

• Adaptation of Neighbor-Joining (NJ), BIONJ, and MVR algorithms to generalize their criteria for incomplete matrices.
• Modification of branch length estimation and distance matrix reduction steps while preserving O(n3) time complexity.
• Large-scale simulations mimicking multi-gene phylogenomic datasets to test algorithm performance.

Main Results:

• Introduced NJ*, BIONJ*, and MVR* algorithms that successfully infer phylogenetic trees from incomplete distance matrices.
• These new algorithms demonstrate comparable or superior accuracy to existing methods with significantly faster run times.
• MVR* exhibited the best overall performance, effectively utilizing variance in distance estimates for phylogenomic studies.

Conclusions:

• NJ*, BIONJ*, and MVR* provide fast and accurate solutions for large-scale phylogenomic studies using distance-based methods.
• Combined with methods like SDM for distance estimation, these algorithms offer a viable alternative to supertree techniques.
• The developed algorithms and simulation data are publicly available.