skip to content
 

On the optimality of the neighbour-joining algorithm

Date: 
Tuesday 18th December 2007 - 14:00 to 14:20
Venue: 
INI Seminar Room 1
Session Chair: 
Magnus Bordewich
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 \leq 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.

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