Title :
On the Neighborhoods of Trees
Author :
Humphries, Peter J. ; Taoyang Wu
Author_Institution :
Dept. of Math. & Phys., North Carolina Central Univ., Durham, NC, USA
Abstract :
Tree rearrangement operations typically induce a metric on the space of phylogenetic trees. One important property of these metrics is the size of the neighborhood, that is, the number of trees exactly one operation from a given tree. We present an exact expression for the size of the TBR (tree bisection and reconnection) neighborhood, thus answering a question first posed by Allen and Steel . In addition, we also obtain a characterization of the extremal trees whose TBR neighborhoods are maximized and minimized.
Keywords :
biology computing; evolution (biological); genetics; trees (mathematics); TBR neighborhood maximization; TBR neighborhood minimization; TBR neighborhood size expression; extremal tree characterization; phylogenetic tree space metric; tree bisection and reconnection neighborhood; tree neighborhood size; tree number; tree rearrangement operation; Binary trees; Indexes; Measurement; Phylogeny; Shape; Steel; Vegetation; Binary trees; Indexes; Measurement; Phylogeny; Shape; Steel; TBR neighborhood maximization; TBR neighborhood minimization; TBR neighborhood size expression; Tree rearrangement; Vegetation; biology computing; evolution (biological); extremal tree characterization; genetics; phylogenetic tree space metric; phylogenetics; tree bisection and reconnection; tree bisection and reconnection neighborhood; tree neighborhood size; tree number; tree rearrangement operation; trees (mathematics); unit neighborhood;
Journal_Title :
Computational Biology and Bioinformatics, IEEE/ACM Transactions on
DOI :
10.1109/TCBB.2013.66
