Algorithmic aspects of some combinatorial problems in bioinformatics

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 some optimization problems resulting from this model are APX-hard, i.e., they cannot be approximated arbitrarily well unless P=NP. Therefore, it seems to be appropriate to consider more restricted models that more carefully take into account the specific characteristics of the real problem setting, but do not become too general.The last part of this thesis focuses on the computation of genomic distances between organisms. To measure the degree of relationship between organisms, for instance as a preliminary step for the construction of phylogenies, a common step is to model their genomes as sequences of homologous genes and to compute the number of specific genomic operations required to transform one genome into the other. Most popular operations in this context are reversals and transpositions. Instead of mere counting the number of operations required, recently it was proposed to measure each performed operation according to the length of the touched gene sequence. This was comprehensively studied lately with respect to the reversal operation. We will show in thisthesis how to transfer most of these results to the transpositions, too, establishing upper and lower bounds on the diameter, i.e., the maximal weighted distance between two arbitrary genomes, and showing approximationresults as well.

Grantor dc:publisher

Publikationsserver der RWTH Aachen University

Year dc:date

2006

Author dc:creator

• Bongartz, Dirk

Contributors dc:contributor

• Hromkovic, Juraj

• info:eu-repo/classification/ddc/004
• Informatik
• bioinformatics
• approximation algorithms
• HP model
• protein folding
• MRSO problem

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-123214%22

OAI identifier oai:identifier

oai:publications.rwth-aachen.de:61560