Properties of Subtree-Prune-and-Regraft Operations on Totally-Ordered Phylogenetic Trees |
| |
Authors: | Yun S Song |
| |
Institution: | (1) Department of Computer Science, University of California, Davis, CA 95616, USA |
| |
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(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.
Received May 18, 2004 |
| |
Keywords: | SPR ordered trees neighbourhood recombination |
本文献已被 SpringerLink 等数据库收录! |
|