On the combinatorics of rooted binary phylogenetic trees
type: Item
instance of: scholarly article
title: On the combinatorics of rooted binary phylogenetic trees
zbMATH Open document ID: 1045.05031
author: Yun S. Song
published in: Annals of Combinatorics
publication date: 2004-05-27T00:00:00Z
review text: 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 \textit{B. Allen} and \textit{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.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 92D15
zbMATH DE Number: 2067288
zbMATH Keywords: rooted phylogenetic tree
zbMATH Keywords: evolutionary tree
zbMATH Keywords: \(X\)-tree
zbMATH Keywords: subtree pruning and regrafting
zbMATH Keywords: unit-neighborhood
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
full work available at URL: s00026-003-0192-0
OpenAlex ID: W2138821506
DOI: 10.1007/S00026-003-0192-0
description: scientific article; zbMATH DE number 2067288