Consensus Algorithms for Trees and Strings
(2003) In Dissertations 17. Abstract
 This thesis studies the computational complexity and polynomialtime 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 leaflabeled tree from a set of constraints on lowest common ancestor relations. Our NPhardness proofs, polynomialtime approximation algorithms, and polynomialtime 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 polynomialtime 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 leaflabeled tree from a set of constraints on lowest common ancestor relations. Our NPhardness proofs, polynomialtime approximation algorithms, and polynomialtime exact algorithms indicate that these problems become computationally easier if the resulting tree is required to comply with a prespecified lefttoright 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 polynomialtime 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 polynomialtime 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, Ebuilding, Lund Institute of Technology
 defense date
 20030414 10:15:00
 ISSN
 14041219
 ISBN
 9162855867
 language
 English
 LU publication?
 yes
 id
 9c6c003920b5444ba96ea8db79aac3cd (old id 27612)
 date added to LUP
 20160401 15:54:12
 date last changed
 20210506 17:43:51
@phdthesis{9c6c003920b5444ba96ea8db79aac3cd, abstract = {This thesis studies the computational complexity and polynomialtime 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 leaflabeled tree from a set of constraints on lowest common ancestor relations. Our NPhardness proofs, polynomialtime approximation algorithms, and polynomialtime exact algorithms indicate that these problems become computationally easier if the resulting tree is required to comply with a prespecified lefttoright 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 polynomialtime 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 polynomialtime algorithms for certain restrictions of the problems.}, author = {Jansson, Jesper}, isbn = {9162855867}, issn = {14041219}, 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/ws/files/4507904/1693337.pdf}, volume = {17}, year = {2003}, }