The property of fast-convergence describes phylogeny reconstruction methods that, with high probability, recover the true tree from sequences that grow polynomially in the number of taxa. While provably fast-converging methods have been developed, the neighbor-joining (NJ) algorithm of Saitou and Nei remains one of the most popular methods used in practice. This algorithm is known to converge for sequences that are exponential in n, but no lower bound for its convergence rate has been established. To address this theoretical question, we analyze the performance of the NJ algorithm on a type of phylogeny known as a "caterpillar tree." We find that, for sequences of polynomial length in the number of taxa, the variability of the NJ criterion is sufficiently high that the algorithm is likely to fail even in the first step of the phylogeny reconstruction process, regardless of the degree of polynomial considered. This result demonstrates that, for general trees, the exponential bound cannot be improved.
view more