"On the optimality of the neighbor-joining algorithm"

Ruriko Yoshida
University of Kentucky

Monday, October 8, 2007
4:00 pm, 113 Patterson Office Tower

Abstract:

The popular neighbor-joining (NJ) algorithm used for phylogenetic tree reconstruction is a greedy algorithm for finding the minimum evolution (ME) tree associated to a dissimilarity map. From this point of view, NJ is ``optimal'' when the algorithm outputs the tree which minimizes the balanced minimum evolution criterion. We use the fact that the NJ tree topology and the ME tree topology are determined by polyhedral subdivisions of the spaces of dissimilarity maps ${\R}_{+}^{n \choose 2}$ to study the optimality of the neighbor-joining algorithm. In particular, we investigate and compare the polyhedral subdivisions for n less than or equal to 10. A key requirement is the measurement of volumes of spherical polytopes in high dimension, which we obtain using a combination of traditional Monte Carlo methods and polyhedral algorithms. Our analysis reveals new insights into the performance of the NJ and ME algorithms for phylogenetic reconstruction. In particular we show that highly unrelated trees can be cooptimal in ME reconstruction, and that NJ optimality regions are not convex. We also conjecture that neighbor joining's ability to recover the ME tree depends on the diameter of the ME tree.

This is joint work with K. Eickmeyer, P. Huggins, and L. Pachter.