Consensus Algorithms for Trees and Strings
(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:
https://lup.lub.lu.se/record/27612
- author
- Jansson, Jesper LU
- supervisor
- opponent
-
- Professor Jiang, Tao, Department of Computer Science and Engineering, University of California, Riverside, U.S.A.
- organization
- publishing date
- 2003
- 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:00
- 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
- 2016-04-01 15:54:12
- date last changed
- 2021-05-06 17:43:51
@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}},
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}},
language = {{eng}},
publisher = {{Computer Science, Lund University}},
school = {{Lund University}},
series = {{Dissertations}},
title = {{Consensus Algorithms for Trees and Strings}},
url = {{https://lup.lub.lu.se/search/files/4507904/1693337.pdf}},
volume = {{17}},
year = {{2003}},
}