<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue3" %>
On the Combinatorics of Rooted Binary Phylogenetic Trees
Yun S. Song
Department of Statistics, University of Oxford, 1 South Parks Road, Oxford, OX1 3TG, UK
Annals of Combinatorics 7 (3) p.365-379 September, 2003
AMS Subject Classification: 05C05, 92D15
We study subtree-prune-and-regraft (SPR) operations on leaf-labelled rooted binary trees, also known as rooted binary phylogenetic trees. This study is motivated by the problem of graphically representing evolutionary histories of biological sequences subject to recombination. We investigate some basic properties of the induced SPR-metric on the space of leaf-labelled rooted binary trees with n leaves. In contrast to the case of unrooted trees, the number |U(T )| of trees in which are one SPR operation away from a given tree T depends on the topology of T. In this paper, we construct recursion relations which allow one to determine the unit-neighbourhood size |U(T )| efficiently for any tree topology. In fact, using the recursion relations we are able to derive a simple closed-form formula for the unit-neighbourhood size. As a corollary, we construct sharp upper and lower bounds on the size of unit-neighbourhoods and investigate the diameter of . Lastly, we consider an enumeration problem relevant to population genetics.
Keywords: rooted trees, ordered trees, subtree prune regraft, neighbourhood


1. B.L. Allen and M. Steel, Subtree transfer operations and their induced metrics on evolutionary trees, Ann. Combin. 5 (2001) 1ĘC13.

2. J. Hein, A heuristic method to reconstruct the history of sequences subject to recombination, J. Mol. Evol. 36 (1993) 396ĘC405.

3. E. Schröder, Vier combinatorische probleme, Zeit. für. Math. Phys. 15 (1870) 361ĘC376.

4. Y.S. Song and J. Hein, Parsimonious reconstruction of sequence evolution and haplotype blocks: finding the minimum number of recombination events, to appear in: Lecture Notes in Computer Science, Proceedings of Workshop on Algorithms in Bioinformatics 2003, Springer-Verlag.

5. D.L. Swofford and G.J. Olsen, Phylogeny reconstruction, In: Molecular Systematics, D.M. Hillis et al., Eds., Sinauer Associates, Massachusetts, 1990, pp. 411ĘC501.