Motivation

The neighbor-joining (NJ) algorithm is a widely used method to perform iterative clustering and forms the basis for phylogenetic reconstruction in several bioinformatic pipelines. Although NJ is considered to be a computationally efficient algorithm, it does not scale well for datasets exceeding several thousand taxa (>100 000). Optimizations to the canonical NJ algorithm have been proposed; these optimizations are, however, achieved through approximations or extensive memory usage, which is not feasible for large datasets.

Results

In this article, two new algorithms, dynamic neighbor joining (DNJ) and heuristic neighbor joining (HNJ), are presented, which optimize the canonical NJ method to scale to millions of taxa without increasing the memory requirements. Both DNJ and HNJ outperform the current gold standard methods to construct NJ trees, while DNJ is guaranteed to produce exact NJ trees.

Availability and implementation

https://bitbucket.org/genomicepidemiology/ccphylo.git

Supplementary information

Supplementary data are available at Bioinformatics online.

This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted reuse, distribution, and reproduction in any medium, provided the original work is properly cited.