Return to search

Rekernelisation Algorithms in Hybrid Phylogenies

It has become well known that an evolutionary tree is inadequate to represent fully the history of life. Two possible ways of dealing with this are the rooted subtree prune and regraft distance between a pair of trees, which measures how different they are, and the slightly more biologically sound hybridisation number of a set of trees that attempts to determine the minimum number of hybrid events that must have occurred for a given set of evolutionary trees. When characterised via agreement forests both problems are, although NP hard, fixed parameter tractable---meaning the problem can be converted to a similar problem with a smaller input size. This thesis investigates ways of improving existing algorithms for calculating the minimum rooted subtree prune and regraft distance and hybridisation number for a pair or, in the latter case, set of trees. In both cases a technique is used that allows the problem to be rekernelised during the run of the program. Another, less effective method, is also looked at which finds the rooted subtree prune and regraft distance or hybridisation number solely on what cannot be contained within any agreement forest. Additionally the characterisation of the minimum rooted subtree prune and regraft distance via maximum agreement forests is extended to non-binary trees and the hybridisation number of a set of phylogenetic trees is extended to unrooted trees.

Identiferoai:union.ndltd.org:ADTP/274106
Date January 2009
CreatorsCollins, Joshua Stewart
PublisherUniversity of Canterbury. Mathematics and Statistics
Source SetsAustraliasian Digital Theses Program
LanguageEnglish
Detected LanguageEnglish
RightsCopyright Joshua Stewart Collins, http://library.canterbury.ac.nz/thesis/etheses_copyright.shtml

Page generated in 0.0017 seconds