<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume10 Issue1" %>
Properties of Subtree-Prune-and-Regraft Operations on Totally-Ordered Phylogenetic Trees
Yun S. Song
Department of Computer Science, University of California, Davis, CA 95616, USA
Annals of Combinatorics 10 (1) p.147-163 March, 2006
AMS Subject Classification: 05C05, 92D15
We study some properties of subtree-prune-and-regraft (SPR) operations on leaflabelled rooted binary trees in which internal vertices are totally ordered. Since biological events occur with certain time ordering, sometimes such totally-ordered trees must be used to avoid possible contradictions in representing evolutionary histories of biological sequences. Compared to the case of plain leaf-labelled rooted binary trees where internal vertices are only partially ordered, SPR operations on totally-ordered trees are more constrained and therefore more difficult to study. In this paper, we investigate the unit-neighbourhood U(T), defined as the set of totally-ordered trees one SPR operation away from a given totally-ordered tree T. We construct a recursion relation for |U(T)| and thereby arrive at an efficient method of determining |U(T)|. In contrast to the case of plain rooted trees, where the unit-neighbourhood size grows quadratically with respect to the number n of leaves, for totally-ordered trees |U(T)| grows like O(n3). For some special topology types, we are able to obtain simple closed-form formulae for |U(T)|. Using these results, we find a sharp upper bound on |U(T)| and conjecture a formula for a sharp lower bound. Lastly, we study the diameter of the space of totally-ordered trees measured using the induced SPR-metric.
Keywords: SPR, ordered trees, neighbourhood, recombination


1. B.L. Allen and M. Steel, Subtree transfer operations and their induced metrics on evolutionary trees, Ann. Comb. 5 (2001) 1--13.

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

3. E. Schröder, Vier combinatorische probleme, Z. für. Math. Phys. 15 (1870) 361--376.

4. Y.S. Song, On the combinatorics of rooted binary phylogenetic trees, Ann. Comb. 7 (2003) 365--379.

5. Y.S. Song and J. Hein, Parsimonious reconstruction of sequence evolution and haplotype blocks: finding the minimum number of recombination events, In: Algorithms in Bioinformatics (Proceedings of WABI 2003), G. Benson and R. Page, Eds., Springer-Verlag, Berlin, (2003) pp. 287--302.

6. D.L. Swofford and G.J. Olsen, Phylogeny reconstruction, In: Molecular Systematics, D.M. Hillis et al., Eds., Sinauer Associates, Massachusetts, (1990) pp. 411--501.