Wareham, Harold Todd (1992) On the computational complexity of inferring evolutionary trees. Masters thesis, Memorial University of Newfoundland.
PDF (Migrated (PDF/A Conversion) from original format: (application/pdf))
- Accepted Version
Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission.
The process of reconstructing evolutionary trees can be viewed formally as an optimization problem. Recently, decision problems associated with the most commonly used approaches to reconstructing such trees have been shown to be NP-complete [Day87, DJS86, DS86, DS87, GF82, Kri88, KM86]. In this thesis, a framework is established that incorporates all such problems studied to date. Within this framework, the NP-completeness results for decision problems are extended by applying theorems from [CT91, Gas86, GKR02, GKR92, JVV86, KST89, Kre88, Sel91] to derive bounds on the computational complexity of several functions associated with each of these problems, namely -- • evaluation functions, which return the cost of the optimal tree(s), -- • solution functions, which return an optimal tree, -- • spanning functions, which return the number of optimal trees, -- • enumeration functions, which systematically enumerate all optimal trees, and -- • random-selection functions, which return a randomly-selected member of the set of optimal trees. -- Where applicable, bounds are also presented for the versions of these functions that are restricted to trees of a given cost or of cost less than or greater than a given limit. Based in part on these results and theorems from [BH90, GJ79, KMB81, Kre88], bounds are derived on how closely polynomial-time algorithms can approximate optimal trees. In particular, it is shown using the recent results of [ALMSS92] that no phylogenetic inference optimal-cost solution problem examined in this thesis has a polynomial-time approximation scheme unless P = NP.
|Item Type:||Thesis (Masters)|
|Additional Information:||Bibliography: leaves 141-166.|
|Department(s):||Science, Faculty of > Computer Science|
|Library of Congress Subject Heading:||Trees (Graph theory); Hypergraphs; Cladistic analysis|
Actions (login required)