On the Combinatorics of Rooted Binary Phylogenetic Trees |
| |
Authors: | Yun S Song |
| |
Institution: | (1) Department of Statistics, University of Oxford, OX1 3TG Oxford, United Kingdom |
| |
Abstract: | 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
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.AMS Subject Classification: 05C05, 92D15. |
| |
Keywords: | rooted trees ordered trees subtree prune regraft neighbourhood |
本文献已被 SpringerLink 等数据库收录! |
|