On the combinatorics of rooted binary phylogenetic trees. (English) Zbl 1045.05031

Song, Yun S.

Ann. Comb. 7, No. 3, 365-379 (2003).

This paper studies the subtree pruning and regrafting (SPR) operation on rooted phylogenetic trees: a subtree is pruned by deleting an edge and it is regrafted by inserting it into another edge. In unrooted trees the size of SPR-related neighborhood is dependent on the topology of the tree, and it was determined by B. Allen and M. Steel [Ann. Comb. 5, No. 1, 1–15 (2001; Zbl 0978.05023)]. However, in the rooted case this size independents upon the topology. This paper gives an efficient algorithm to determine this size. It gives also sharp bounds on this size, which in turn may allow to investigate the diameter of the tree-space.

Reviewer: Péter L. Erdős (Budapest)

MSC:

05C05	Trees
92D15	Problems related to evolution

Keywords:

rooted phylogenetic tree; evolutionary tree; \(X\)-tree; subtree pruning and regrafting; unit-neighborhood