Neighbourhoods of Phylogenetic Trees: Exact and Asymptotic Counts

Type of content
Theses / Dissertations
Publisher's DOI/URI
Thesis discipline
Mathematics
Degree name
Master of Science
Publisher
University of Canterbury. Mathematics and Statistics
Journal Title
Journal ISSN
Volume Title
Language
Date
2015
Authors
de Jong, Jamie Victoria
Abstract

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 the reconstruction of trees, it is crucial to understand the size and structure of 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 thesis we explore previous results on the size of these neighbourhoods under common tree rearrangement operations (NNI, SPR and TBR). We obtain new results concerning the number of trees at distance k from a given tree under the Robinson-Foulds (RF) metric and the Nearest Neighbour Interchange (NNI) operation, and the number of trees at distance two from a given tree under the Subtree Prune and Regraft (SPR) operation. We also obtain an exact count for the number of pairs of binary phylogenetic trees that share a first RF or NNI neighbour.

Description
Citation
Keywords
Phylogenetic tree, splits, Robinson-Foulds metric, tree rearrangements, asymptotics
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Rights
Copyright Jamie Victoria de Jong