On the neighborhoods of trees

Peter J. Humphries, Taoyang Wu

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)721-728
Number of pages8
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Issue number3
Publication statusPublished - 1 May 2013

Cite this