Return to search

Combinatorial Aspects of Leaf-Labelled Trees

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.
Date January 2008
CreatorsHumphries, Peter John
PublisherUniversity of Canterbury. Mathematics and Statistics
Source SetsUniversity of Canterbury
Detected LanguageEnglish
TypeElectronic thesis or dissertation, Text
RightsCopyright Peter John Humphries,

Page generated in 0.0162 seconds