Combinatorial Aspects of Leaf-Labelled Trees

Type of content
Theses / Dissertations
Publisher's DOI/URI
Thesis discipline
Mathematics
Degree name
Doctor of Philosophy
Publisher
University of Canterbury. Mathematics and Statistics
Journal Title
Journal ISSN
Volume Title
Language
Date
2008
Authors
Humphries, Peter John
Abstract

Leaf-labelled trees are used commonly in computational biology and in other disciplines, to depict the ancestral relationships and present-day similarities between both extant and extinct species. Studying these trees from a mathematical perspective provides a foundation for developing tools and techniques that have practical applications.

We begin by examining some quartet problems, namely determining the number of quartets that are required to infer the structure of a particular supertree. The quartet graph is introduced as a tool for tackling quartet problems, and is subsequently used to give new characterisations of compatible, definitive and identifying quartet sets.

We then turn to investigating some properties of the subtrees induced by a collection of trees. This is motivated in part by the problem of reconstructing two or more trees simultaneously from their combined collection of subtrees. We also use some ideas drawn from Ramsey theory to show the existence of arbitrarily large common subtrees.

Finally, we explore some extremal properties of the metric that is induced by the tree bisection and reconnection operation. This includes finding new (asymptotically) tight upper and lower bounds on both the size of the neighbourhoods in the metric space and on the diameter of the corresponding adjacency graph.

Description
Citation
Keywords
graph theory, phylogenetics
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Rights
Copyright Peter John Humphries