skip to content

Properties of the TBR metric

Friday 7th September 2007 - 10:40 to 11:00
INI Seminar Room 1

Tree rearrangement operations are used in computational biology as a measure of the similarity between two binary phylogenetic trees on the same leaf set. For unrooted trees, the three operations of primary interest are nearest-neighbour interchange (NNI), subtree prune-and-regraft (SPR) and tree bisection-and-reconnection (TBR). All three of these have been shown to induce metrics on the set of unrooted binary phylogenetic trees.

The unit-neighbourhood of a tree T is the set of all trees that can be obtained by performing exactly one tree rearrangement on T. For both NNI and SPR, the size of this unit-neighbourhood is independent of the shape of T, and depends only on the size of the leaf set. The same is not true for TBR however, although both upper and lower bounds are known.

We present a recursion for calculating the size of the TBR unit- neighbourhood for any tree in the space of unrooted binary phylogenetic trees with n leaves. We also use this to establish improved upper and lower bounds on this size, and characterise those trees for which the given upper bound is sharp.

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