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

yssong@cs.ucdavis.edu

Annals of Combinatorics 10 (1) p.147-163 March, 2006

Abstract:

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*(*n*^{3}).
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.

References:

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.