Phylogenetics is the study of evolutionary relationships. It is a scientific
endeavour to discover history, and it is not easy. Massive amounts of data
together with computationally difficult optimization problems mean that
heuristics are prevalent, and ever better techniques are sought. New
approaches are valuable if they are more accurate, but are considered even more
so if they are faster than pre-existing methods. Improvements to existing
algorithms, whether in terms of space requirements, or faster running times,
are also worthwhile. This dissertation explores three new techniques, each of
which is valuable according to the previous definitions.
The first contribution is TASPI, a system for storing collections of
phylogenetic trees, and performing post-tree analyses. TASPI stores collections
of trees more compactly than the previous method, and this compact structure
lends itself to post-tree analyses. This results in the ability to compute
strict and majority consensus trees faster than common alternatives. As an
added benefit, TASPI is written in ACL2, which allows properties of the
algorithms and data structures to be formally verified.
The second contribution is an improved method to generate phylogenetic trees.
A common methodology involves two steps, first estimating a Multiple Sequence
Alignment (MSA), and then estimating a tree using that MSA. This method
changes the way in which the MSA is estimated, and this leads to improved
accuracy of the resultant trees. Also, in some cases, the time required is
also reduced.
The third contribution is BLuTGEN, a method by which a phylogenetic tree is
estimated from sequence data, but without ever generating an MSA for the full
dataset. BLuTGEN is as accurate as one of the best published tree estimation
techniques (SATé), but takes a novel approach which allows it to be applied
to much larger datasets. / text
| Identifer | oai:union.ndltd.org:UTEXAS/oai:repositories.lib.utexas.edu:2152/ETD-UT-2009-12-529 |
| Date | 13 August 2010 |
| Creators | Nelesen, Serita Marie |
| Contributors | Hunt, Warren A., 1958-, Warnow, Tandy, 1955- |
| Source Sets | University of Texas |
| Language | English |
| Detected Language | English |
| Type | thesis |
| Format | application/pdf |
Page generated in 0.002 seconds