On the computational complexity of inferring evolutionary trees

摘要: 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 such have been shown NP-complete [Day87, DJS86, DS86, DS87, GF82, Kri88, KM86]. In this thesis, a framework is established that incorporates all studied date. Within framework, NP-completeness results for are extended by applying theorems from [CT91, Gas86, GKR02, GKR92, JVV86, KST89, Kre88, Sel91] derive bounds on computational complexity several functions each these problems, namely -- • evaluation functions, which return cost optimal tree(s), solution tree, spanning number trees, enumeration systematically enumerate and random-selection randomly-selected member set trees. Where applicable, also presented versions restricted given or less than greater limit. Based in part [BH90, GJ79, KMB81, Kre88], derived how closely polynomial-time algorithms approximate particular, it using recent [ALMSS92] no phylogenetic inference optimal-cost problem examined thesis has approximation scheme unless P = NP.