Advanced

Exact and approximation algorithms for graph problems with some biological applications

Lundell, Eva-Marta LU (2009)
Abstract
In this thesis we study several combinatorial problems in algorithmic graph theory and computational biology, and different algorithmical approaches for solving them.

In particular, we focus on graph algorithms, seeking for the most part polynomial or sub-exponential exact solutions, but in some cases also approximate solutions.

In the first part we study two problems on phylogenetic trees, the problem of finding a consensus tree for a set of phylogenetic trees, and the problem of combining a set of not necessarily consistent three-taxon trees into a phylogenetic tree that represents the input trees as closely as possible.

The second part is devoted to the problem of the embedding of graphs into integer lattices.... (More)
In this thesis we study several combinatorial problems in algorithmic graph theory and computational biology, and different algorithmical approaches for solving them.

In particular, we focus on graph algorithms, seeking for the most part polynomial or sub-exponential exact solutions, but in some cases also approximate solutions.

In the first part we study two problems on phylogenetic trees, the problem of finding a consensus tree for a set of phylogenetic trees, and the problem of combining a set of not necessarily consistent three-taxon trees into a phylogenetic tree that represents the input trees as closely as possible.

The second part is devoted to the problem of the embedding of graphs into integer lattices. In particular, we extend the problem to integer lattices of higher dimensions. We present a subexponential-time method for optimal embedding of an arbitrary graph into a d-dimensional integer lattice. In particular, it yields a subexponential-time algorithm for optimal protein folding in the HP-model.

Next, we study the problem of efficiently finding shortest cycles, and present approximation algorithms for both the weighted and unweighted variants of this problem.

Finally, we consider the approximability of the maximum and minimum edge clique partition problems, giving upper and lower bounds, and present approximation algorithms for both variants. (Less)
Please use this url to cite or link to this publication:
author
supervisor
opponent
  • Professor Heggernes, Pinar, Institutt for Informatikk, Universitetet i Bergen, Norway
organization
publishing date
type
Thesis
publication status
published
subject
keywords
Graph algorithms, computational biology, approximation algorithms, computational complexity, evolutionary trees, maximum agreement subtree, graph embedding, shortest cycle, clique partitioning
pages
92 pages
defense location
E:1406, E-building, Ole Römers väg 3
defense date
2009-05-20 13:00
ISSN
1650-1268
ISBN
978-91-628-7785-9
language
English
LU publication?
yes
id
3ac9524a-89fc-40bc-9b39-5b50884d3287 (old id 1390503)
date added to LUP
2009-04-27 09:20:56
date last changed
2016-09-19 08:45:01
@misc{3ac9524a-89fc-40bc-9b39-5b50884d3287,
  abstract     = {In this thesis we study several combinatorial problems in algorithmic graph theory and computational biology, and different algorithmical approaches for solving them.<br/><br>
In particular, we focus on graph algorithms, seeking for the most part polynomial or sub-exponential exact solutions, but in some cases also approximate solutions.<br/><br>
In the first part we study two problems on phylogenetic trees, the problem of finding a consensus tree for a set of phylogenetic trees, and the problem of combining a set of not necessarily consistent three-taxon trees into a phylogenetic tree that represents the input trees as closely as possible.<br/><br>
The second part is devoted to the problem of the embedding of graphs into integer lattices. In particular, we extend the problem to integer lattices of higher dimensions. We present a subexponential-time method for optimal embedding of an arbitrary graph into a d-dimensional integer lattice. In particular, it yields a subexponential-time algorithm for optimal protein folding in the HP-model.<br/><br>
Next, we study the problem of efficiently finding shortest cycles, and present approximation algorithms for both the weighted and unweighted variants of this problem.<br/><br>
Finally, we consider the approximability of the maximum and minimum edge clique partition problems, giving upper and lower bounds, and present approximation algorithms for both variants.},
  author       = {Lundell, Eva-Marta},
  isbn         = {978-91-628-7785-9},
  issn         = {1650-1268},
  keyword      = {Graph algorithms,computational biology,approximation algorithms,computational complexity,evolutionary trees,maximum agreement subtree,graph embedding,shortest cycle,clique partitioning},
  language     = {eng},
  pages        = {92},
  title        = {Exact and approximation algorithms for graph problems with some biological applications},
  year         = {2009},
}