zbMATH — the first resource for mathematics

On the combinatorics of rooted binary phylogenetic trees. (English) Zbl 1045.05031
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.

05C05 Trees
92D15 Problems related to evolution
Full Text: DOI