# PLG

## Seminar

### Partitioning the sample space on five taxa for the neighbour joining algorithm

Yoshida, R (Kentucky)
Tuesday 04 September 2007, 16:10-16:30

Seminar Room 1, Newton Institute

#### Abstract

In this talk, we will analyze the behavior of the Neighbor Joining algorithm on five taxa and we will show that the partition of the sample (data) space for estimation of a tree topology with five taxa into subspaces, within each of which the Neighbor Joining algorithm returns the same tree topology. A key of our method to partition the sample space is the action of the symmetric group $S_5$ on the set of distance matrices by changing the labels of leaves. The method described in this paper can be generalized to trees with more than five taxa.

This is joint work with Kord Eickmeyer and a preprint is available at http://arxiv.org/abs/math.CO/0703081.