skip to content

A signal-to-noise analysis of phylogeny estimation by neighbour-joining

Monday 17th December 2007 - 15:30 to 15:50
INI Seminar Room 1
Session Chair: 
Kathi Huber

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.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons