Consensus Algorithms for Trees and Strings
Jesper Jansson
April, 2003
Ph.D. Thesis in Computer Science
Abstract
This thesis studies the computational complexity and polynomial-time
approximability of a number of discrete combinatorial optimization problems
involving labeled trees and strings.
The problems considered
have applications to computational molecular biology,
pattern matching,
and many other areas of computer science.
The thesis is divided into three parts.
In the first part, we study some problems in which the goal is to infer a
leaf-labeled tree from a set of constraints on lowest common ancestor
relations.
Our NP-hardness proofs, polynomial-time approximation algorithms, and
polynomial-time exact algorithms indicate that these problems become
computationally easier if the resulting tree is required to comply with a
prespecified left-to-right ordering of the leaves.
The second part of the thesis deals with two problems related to identifying
shared substructures in labeled trees.
We first investigate how the polynomial-time approximability of the maximum
agreement subtree problem depends on the maximum height of the input trees.
Then, we show how the running time of the currently fastest known algorithm
for the alignment between ordered trees problem can be reduced for problem
instances in which the two input trees are similar and the scoring scheme
satisfies some natural assumptions.
The third part is devoted to radius and diameter clustering problems for
binary strings
where distances between strings are measured using the Hamming metric.
We present new inapproximability results and various types of approximation
algorithms as well as exact polynomial-time algorithms for certain
restrictions of the problems.
The thesis can be downloaded by clicking on the links below:
A printed version of the thesis can be obtained from:
Technical Reports Librarian
Department of Computer Science
Lund University
Box 118
SE-221 00 Lund
Sweden
E-mail:
Anne-Marie.Westerberg@cs.lth.se
Back