Digital Archives Initiative
Memorial University - Electronic Theses and Dissertations 2
menu off  add document to favorites : add page to favorites : reference url back to results : previous : next
 Search this object:
 0 hit(s) :: previous hit : next hit
  previous page : next page
Document Description
TitleOn the computational complexity of inferring evolutionary trees
AuthorWareham, Harold Todd, 1963-
DescriptionThesis (M.Sc.)--Memorial University of Newfoundland, 1993. Computer Science
Paginationxiii, 177 leaves : ill.
SubjectTrees (Graph theory); Hypergraphs; Cladistic analysis
Degree GrantorMemorial University of Newfoundland. Dept. of Computer Science
DisciplineComputer Science
NotesBibliography: leaves 141-166.
AbstractThe 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.
Resource TypeElectronic thesis or dissertation
FormatImage/jpeg; Application/pdf
SourcePaper copy kept in the Centre for Newfoundland Studies, Memorial University Libraries
Local Identifier76165750
RightsThe 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.
CollectionElectronic Theses and Dissertations
Scanning StatusCompleted
PDF File(19.09 MB) --
CONTENTdm file name225465.cpd