Properties of the TBR metric
Seminar Room 1, Newton Institute
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.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.