2015/08/15 by Jamie V. de Jong, de Jong, Jamie V., Jeanette C. McLeod +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Biological sciences #FOS: Mathematics #Genetic diversity and population structure #Genomics and Phylogenetic Studies #Populations and Evolution (q-bio.PE)
paper · pdf · doi:10.48550/arxiv.1508.03774
openalex publication_date 2015/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A central theme in phylogenetics is the reconstruction and analysis of evolutionary trees from a given set of data. To determine the optimal search methods for reconstructing trees, it is crucial to understand the size and structure of the neighbourhoods of trees under tree rearrangement operations. The diameter and size of the immediate neighbourhood of a tree has been well-studied, however little is known about the number of trees at distance two, three or (more generally) k from a given tree. In this paper we provide a number of exact and asymptotic results concerning these quantities, and identify some key aspects of tree shape that play a role in determining these quantities. We obtain several new results for two of the main tree rearrangement operations - Nearest Neighbour Interchange and Subtree Prune and Regraft -- as well as for the Robinson-Foulds metric on trees.