Prospects for inferring very large phylogenies by using the neighbor-joining method

TLDR

Reconstructing phylogenies with thousands of sequences is computationally demanding, and although neighbor‑joining is fast and accurate on small data sets, it explores only a negligible fraction of tree space as data size grows. This study evaluates the accuracy of neighbor‑joining trees for very large phylogenies through computer simulations. We developed a likelihood‑based method that simultaneously estimates all pairwise distances using realistic nucleotide substitution models. The method corrects up to 60 % of NJ errors, and NJ accuracy declines only about 5 % when sequence numbers increase from 32 to 4,096, even under rate heterogeneity and compositional bias, supporting the use of complex substitution models for large phylogenies.

Abstract

Current efforts to reconstruct the tree of life and histories of multigene families demand the inference of phylogenies consisting of thousands of gene sequences. However, for such large data sets even a moderate exploration of the tree space needed to identify the optimal tree is virtually impossible. For these cases the neighbor-joining (NJ) method is frequently used because of its demonstrated accuracy for smaller data sets and its computational speed. As data sets grow, however, the fraction of the tree space examined by the NJ algorithm becomes minuscule. Here, we report the results of our computer simulation for examining the accuracy of NJ trees for inferring very large phylogenies. First we present a likelihood method for the simultaneous estimation of all pairwise distances by using biologically realistic models of nucleotide substitution. Use of this method corrects up to 60% of NJ tree errors. Our simulation results show that the accuracy of NJ trees decline only by approximately 5% when the number of sequences used increases from 32 to 4,096 (128 times) even in the presence of extensive variation in the evolutionary rate among lineages or significant biases in the nucleotide composition and transition/transversion ratio. Our results encourage the use of complex models of nucleotide substitution for estimating evolutionary distances and hint at bright prospects for the application of the NJ and related methods in inferring large phylogenies.