Algorithmic aspects of some combinatorial problems in bioinformatics
type: CreativeWork
description: The consistently growing field of bioinformatics exhibits the success of cooperative work in biology and computer science. The interaction between new experimental techniques gaining more and more data about molecular structures and processes and the knowledge how to prepare, structure, and analyze this data and even more to predict relations based on this data, is the driving force within this field.In this thesis, we study models and combinatorial problems arising from current bioinformatics research focussing on the algorithmic point of view.Protein structure prediction, sometimes referred to as the "holy grail" of bioinformatics, is the problem to infer the spatial structure of proteins from their amino-acid sequence. We propose two extensions to the popular HP model for this task, which significantly improve its applicability in practice. Namely, we remove the drawback of bipartiteness of the grid lattice that was used in the original HP model to discretize the space. We denote these extended models by HPd and $alpha$-DC-HP model, respectively. For the optimization problems emerging from these models, we design and analyze approximation algorithms. In particular, our approximation algorithms for the HPd model achieve approximation ratios of $frac{26}{15}$ and $frac{8}{5}$ for the two- and three-dimensional case respectively, which are the best approximation ratios obtained for HP-like problems so far.In the next part of this thesis, we study a model proposed in the context of protein engineering. The installation of the 21th amino acid selenocysteine into a protein, has been shown to enhance its function often, which makes the design of such selenoproteins a desired goal. Since the incorporation of selenocystein depends on the spatial structure of the mRNA in the process of biosynthesis, we are aiming to design an appropriate mRNA that obeys the corresponding structure constraints. A model to formulate this goal was givenin the literature. We will prove that so…
abstract: The consistently growing field of bioinformatics exhibits the success of cooperative work in biology and computer science. The interaction between new experimental techniques gaining more and more data about molecular structures and processes and the knowledge how to prepare, structure, and analyze this data and even more to predict relations based on this data, is the driving force within this field.In this thesis, we study models and combinatorial problems arising from current bioinformatics research focussing on the algorithmic point of view.Protein structure prediction, sometimes referred to as the "holy grail" of bioinformatics, is the problem to infer the spatial structure of proteins from their amino-acid sequence. We propose two extensions to the popular HP model for this task, which significantly improve its applicability in practice. Namely, we remove the drawback of bipartiteness of the grid lattice that was used in the original HP model to discretize the space. We denote these extended models by HPd and $alpha$-DC-HP model, respectively. For the optimization problems emerging from these models, we design and analyze approximation algorithms. In particular, our approximation algorithms for the HPd model achieve approximation ratios of $frac{26}{15}$ and $frac{8}{5}$ for the two- and three-dimensional case respectively, which are the best approximation ratios obtained for HP-like problems so far.In the next part of this thesis, we study a model proposed in the context of protein engineering. The installation of the 21th amino acid selenocysteine into a protein, has been shown to enhance its function often, which makes the design of such selenoproteins a desired goal. Since the incorporation of selenocystein depends on the spatial structure of the mRNA in the process of biosynthesis, we are aiming to design an appropriate mRNA that obeys the corresponding structure constraints. A model to formulate this goal was givenin the literature. We will prove that so…
author: Bongartz, Dirk
language: eng
keywords: info:eu-repo/classification/ddc/004, Informatik, bioinformatics, approximation algorithms, HP model, protein folding, MRSO problem
date published: 2006
date modified: 2026-07-30T19:43:10Z
provider: RWTH Aachen University
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: Publikationsserver der RWTH Aachen University