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.
| Identifer | oai:union.ndltd.org:canterbury.ac.nz/oai:ir.canterbury.ac.nz:10092/2852 |
| Date | January 2009 |
| Creators | Collins, Joshua Stewart |
| Publisher | University of Canterbury. Mathematics and Statistics |
| Source Sets | University of Canterbury |
| Language | English |
| Detected Language | English |
| Type | Electronic thesis or dissertation, Text |
| Rights | Copyright Joshua Stewart Collins, http://library.canterbury.ac.nz/thesis/etheses_copyright.shtml |
| Relation | NZCU |
Page generated in 0.0021 seconds