Algorithmic aspects of some combinatorial problems in bioinformatics

Bongartz, Dirk; Hromkovic, Juraj

doi:27025

Algorithmic aspects of some combinatorial problems in bioinformatics = Algorithmische Aspekte einiger kombinatorischer Probleme der Bioinformatik

Bongartz, Dirk

2006

Verantwortlichkeitsangabevorgelegt von Dirk Bongartz

ImpressumAachen : Publikationsserver der RWTH Aachen University 2006

UmfangX, 139 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2006

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Hromkovic, Juraj (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2006-04-13

Online
URN: urn:nbn:de:hbz:82-opus-15276
URL: https://publications.rwth-aachen.de/record/61560/files/Bongartz_Dirk.pdf

Einrichtungen

Fakultät für Mathematik, Informatik und Naturwissenschaften (100000)

Inhaltliche Beschreibung (Schlagwörter)
Informatik (frei) ; bioinformatics (frei) ; approximation algorithms (frei) ; HP model (frei) ; protein folding (frei) ; MRSO problem (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Das stetig wachsende Gebiet der Bioinformatik veranschaulicht den Erfolg der fächerübergreifenden Kooperation zwischen Biologen und Informatikern. Das Zusammenspiel von neuen experimentellen Methoden, die mehr und mehr Daten über molekulare Strukturen und Prozesse liefern, und dem Wissen, diese Daten aufzubereiten, zu strukturieren und zu analysieren und darüberhinaus auch Vorhersagen auf Basis dieser Daten zu treffen, ist die treibende Kraft in diesem Arbeitsgebiet.In der vorliegenden Dissertation untersuchen wir Modelle und kombinatorische Fragestellungen, die sich aus der aktuellen Bioinformatikforschung ergeben, auf ihre algorithmischen Eigenschaften.Die Vorhersage von Proteinstrukturen, die manchmal auch als der „Heilige Gral” der Bioinformatik bezeichnet wird, beschäftigt sich mit der Bestimmung der räumlichen Struktur von Proteinen aus deren Aminosäuresequenz. Wir schlagen zwei Erweiterungen des populären HP-Modells für dieses Problem vor, die dessen reale Anwendbarkeit wesentlich verbessern. Insbesondere beseitigen wir die Bipartitheit des zugrundeliegenden Gitters, welches zur Diskretisierung des Raumes im originalen HP-Modell dient. Wir bezeichnen die resultierenden Modelle als HPd- bzw. als $alpha$-DC-HP-Modell. Für die sich aus diesen Modellen ergebenden Optimierungsprobleme entwerfen und analysieren wir Approximationsalgorithmen. Insbesondere erzielen wir Approximationsgüten von $frac{26}{15}$ bzw. $frac{8}{5}$ für den zwei- bzw. drei-dimensionalen Fall, welches die besten bislang erreichten Approximationsgüten für HP-ähnliche Modelle insgesamt sind.Ein weiterer Teil dieser Dissertation beschäftigt sich mit der Untersuchung eines Modells, das im Kontext der Protein-Synthese vorgeschlagen wurde. Der Einbau der 21. Aminosäure Selenocystein in ein Protein führt oft zu einer Erhöhung dessen funktionaler Aktivität, wodurch die Entwicklung solcher Selenoproteine ein begehrtes Ziel wird. Da der Einbau von Selenocystein auf einer bestimmten räumlichen Struktur der mRNA während der Proteinbiosynthese beruht, zielen wir darauf ab, eine geeignete mRNA zu entwerfen, die den entsprechenden Strukturbedingungen genügt. Ein Modell, das dieses Ziel formalisiert, wurde in der Literatur vorgeschlagen. Wir zeigen, dass einige der aus diesem Modell resultierenden Optimierungsprobleme APX-schwer sind, d.h., sie können unter der Annahme P $eq$ NP nicht beliebig gut approximiert werden. Daher erscheint es sinnvoll, eingeschränktere Modelle zu betrachten, die sorgfältig die spezifischen Eigenschaften des zugrundeliegenden realen Problems modellieren, aber nicht zu allgemein werden.Der letzte Teil dieser Arbeit beschäftigt sich mit der Berechnung von genetischen Distanzen zwischen Organismen. Um den Verwandtschaftsgrad zwischen Organismen zu messen, beispielsweise als Vorbereitung auf die Rekonstruktion eines Stammbaums, ist es üblich, ihre Genome als Abfolgen von homologen Genen darzustellen und die Anzahl von bestimmten Operationen auf diesen Genomen zu bestimmen, die das eine Genom in das andere überführen. Die populärsten Operationen in diesem Zusammenhang sind Reversals und Transpositionen.Anstatt lediglich die Anzahl der benötigten Operationen zu zählen, wurde kürzlich vorgeschlagen, jede durchgeführte Operation hinsichtlich der Länge der Gensequenz zu gewichten, auf der sie operiert. Dies wurde vor kurzem ausführlich im Hinblick auf Reversals untersucht. Wir werden in dieser Arbeit zeigen, wie sich die meisten der Resultate auch auf Transpositionen übertragen lassen, wobei wir untere und obere Schranken bezüglich des Diameters, dem maximalen gewichteten Abstand zwischen zwei beliebigen Genomen, vorlegen und auch Approximationsresultate beweisen.

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.

OpenAccess:
PDF
(additional files)