Advanced

Consensus Algorithms for Trees and Strings

Jansson, Jesper LU (2003) In Dissertations 17.
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
opponent
  • Professor Jiang, Tao, Department of Computer Science and Engineering, University of California, Riverside, U.S.A.
organization
publishing date
type
Thesis
publication status
published
subject
keywords
numerical analysis, computational complexity, Approximation algorithm, labeled tree, lowest common ancestor constraint, maximum agreement subtree, alignment between trees, clustering, Computer science, Hamming metric, systems, control, Datalogi, numerisk analys, system, kontroll
in
Dissertations
volume
17
pages
154 pages
publisher
Computer Science, Lund University
defense location
Room E:1406, E-building, Lund Institute of Technology
defense date
2003-04-14 10:15
ISSN
1404-1219
ISBN
91-628-5586-7
language
English
LU publication?
yes
id
9c6c0039-20b5-444b-a96e-a8db79aac3cd (old id 27612)
date added to LUP
2007-06-08 10:35:14
date last changed
2016-09-19 08:44:54
@phdthesis{9c6c0039-20b5-444b-a96e-a8db79aac3cd,
  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.<br/><br>
<br/><br>
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.<br/><br>
<br/><br>
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.<br/><br>
<br/><br>
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.},
  author       = {Jansson, Jesper},
  isbn         = {91-628-5586-7},
  issn         = {1404-1219},
  keyword      = {numerical analysis,computational complexity,Approximation algorithm,labeled tree,lowest common ancestor constraint,maximum agreement subtree,alignment between trees,clustering,Computer science,Hamming metric,systems,control,Datalogi,numerisk analys,system,kontroll},
  language     = {eng},
  pages        = {154},
  publisher    = {Computer Science, Lund University},
  school       = {Lund University},
  series       = {Dissertations},
  title        = {Consensus Algorithms for Trees and Strings},
  volume       = {17},
  year         = {2003},
}