Constructing Evolutionary Trees - Algorithms and Complexity
Anna Östlin
PhD Thesis. Department of Computer Science, Lund University. June
2001.
Abstract
In this thesis three general problems concerning construction
of evolutionary trees are considered. Algorithms for the problems
are presented and the complexity of the problems is investigated.
The thesis consists of three corresponding parts. The first part is
devoted to the problem of constructing evolutionary trees in the
experiment model. Different algorithms for the problem are given,
including an optimal algorithm for constructing evolutionary trees and
an optimal algorithm for merging two evolutionary trees. Matching
lower bounds are also provided.
The second part of the thesis presents results related to the
inferred consensus tree problem. The optimization version of
the problem is shown to be NP-complete and two heuristic algorithms
are presented. Further, the ordered version of the problem
is studied.
In the last part of the thesis the complexity of the maximum
homeomorphic subtree problem is examined.
The problem is shown to be hard to approximate, unless P=NP, even for
trees of constant height, whereas a constant approximation
ratio is obtained in case of a constant number of
trees of constant height.