Sparse Neighbor Joining: rapid phylogenetic inference using a sparse distance matrix

Area of Science:

• Computational Biology
• Bioinformatics
• Phylogenetics

Background:

• Phylogenetic reconstruction is crucial in computational biology.
• The Neighbor Joining (NJ) algorithm is an efficient distance-based method for this.
• Scaling NJ to large datasets is limited by the computation of the distance matrix.

Purpose of the Study:

• To develop a novel algorithm for faster phylogenetic tree reconstruction.
• To overcome the computational bottleneck of the traditional Neighbor Joining algorithm.

Main Methods:

• Propose a new algorithm that avoids computing a dense distance matrix.
• Dynamically determine a sparse set of distance matrix entries to compute.
• Implement a basic version with O(n log n) entries and an enhanced version with O(n log^2 n) entries.

Main Results:

• The new algorithm significantly reduces execution time for large datasets.
• Experimental results demonstrate improved performance compared to standard NJ.
• A trade-off between execution speed and accuracy was observed.

Conclusions:

• Sparse Neighbor Joining offers a scalable alternative for phylogenetic reconstruction.
• The algorithm provides a practical solution for analyzing large biological datasets.
• The Python implementation is publicly available for use and further development.