# PLG

## Seminar

### On the optimality of the neighbour-joining algorithm

Seminar Room 1, Newton Institute

#### 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.

## Comments

Start the discussion!