Algorithmic aspects of some combinatorial problems in bioinformatics [Elektronische Ressource] / vorgelegt von Dirk Bongartz

Sujets

• Biologie

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2006
• Nombre de lectures: 8
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Algorithmic Aspects of Some Combinatorial
Problems in Bioinformatics
Von der Fakulta¨t fu¨r Mathematik, Informatik und Naturwissenschaften der
Rheinisch-Westfa¨lischen Technischen Hochschule Aachen zur Erlangung des
akademischen Grades eines Doktors der Naturwissenschaften genehmigte
Dissertation
vorgelegt von
Diplom-Informatiker
Dirk Bongartz
aus Viersen
Berichter: Universita¨tsprofessor Dr. Juraj Hromkoviˇc
Universita¨tsprofessor Dr. Berthold Vo¨cking
Tag der mu¨ndlichen Pru¨fung: 13. April 2006
Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfu¨gbar.iiiii
Abstract
The consistently growing field of bioinformatics exhibits the success of coop-
erative work in biology and computer science. The interaction between new
experimental techniques gaining more and more data about molecular struc-
tures 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
theiramino-acidsequence. WeproposetwoextensionstothepopularHPmodel
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 mod-
els by HPd and α-DC-HP model, respectively. For the optimization problems
emerging from these models, we design and analyze approximation algorithms.
In particular, ourapproximationalgorithmsfor the HPd model achieveapprox-
26 8imation ratios of and for the two- and three-dimensional case respectively,
15 5
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
aprotein,hasbeenshowntoenhanceitsfunction often, whichmakesthedesign
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
structureconstraints. Amodeltoformulatethisgoalwasgivenintheliterature.
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 com-
mon 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
andtranspositions. Insteadofmerecountingthenumberofoperationsrequired,
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 this thesis how to
transfer most of these results to the transpositions, too, establishing upper and
lowerboundsonthediameter,i.e., the maximalweighteddistancebetweentwo
arbitrary genomes, and showing approximation results as well.ivv
Zusammenfassung
Das stetig wachsende Gebiet der Bioinformatik veranschaulicht den Erfolg der
fa¨cheru¨bergreifenden Kooperation zwischen Biologen und Informatikern. Das
ZusammenspielvonneuenexperimentellenMethoden,diemehrundmehrDaten
u¨ber molekulareStrukturen und Prozesseliefern, und dem Wissen, diese Daten
aufzubereiten, zu strukturieren und zu analysieren und daru¨berhinaus auch
Vorhersagenauf Basis dieser Daten zu treffen, ist die treibende Kraft in diesem
Arbeitsgebiet.
In der vorliegenden Dissertation untersuchen wir Modelle und kombina-
torische Fragestellungen, die sich aus der aktuellen Bioinformatikforschung er-
geben, auf ihre algorithmischen Eigenschaften.
Die Vorhersage von Proteinstrukturen, die manchmal auch als der “Heilige
Gral” der Bioinformatik bezeichnet wird, bescha¨ftigt sich mit der Bestimmung
der ra¨umlichen Struktur von Proteinen aus deren Aminosa¨uresequenz. Wir
schlagenzwei Erweiterungendes popula¨renHP-Modells fu¨r dieses Problemvor,
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 α-DC-HP-Modell. Fu¨r die sich aus diesen Model-
len ergebenden Optimierungsprobleme entwerfen und analysieren wir Approxi-
26mationsalgorithmen. Insbesondere erzielen wir Approximationsgu¨ten von 15
8bzw. fu¨r den zwei- bzw. drei-dimensionalen Fall, welches die besten bislang5
erreichten Approximationsgu¨ten fu¨r HP-a¨hnliche Modelle insgesamt sind.
Ein weiterer Teil dieser Dissertation bescha¨ftigt sich mit der Untersuchung
eines Modells, das im Kontext der Protein-Synthese vorgeschlagen wurde. Der
Einbau der 21. Aminos¨aure Selenocystein in ein Protein fu¨hrt oft zu einer
Erho¨hung dessen funktionaler Aktivit¨at, wodurch die Entwicklung solcher Se-
lenoproteine ein begehrtes Ziel wird. Da der Einbau von Selenocystein auf
einer bestimmten ra¨umlichen Struktur der mRNA wa¨hrend der Proteinbiosyn-
these beruht, zielen wir darauf ab, eine geeignete mRNA zu entwerfen, die den
entsprechenden Strukturbedingungen genu¨gt. Ein Modell, das dieses Ziel for-
malisiert, wurde in der Literatur vorgeschlagen. Wir zeigen, dass einige der aus
diesemModellresultierendenOptimierungsproblemeAPX-schwersind,d.h.,sie
k¨onnenunter derAnnahme P=NPnicht beliebig gut approximiertwerden. Da-
her erscheint es sinnvoll, eingeschr¨anktere Modelle zu betrachten, die sorgf¨altig
die spezifischen Eigenschaften des zugrundeliegenden realen Problems model-
lieren, aber nicht zu allgemein werden.
Der letzte Teil dieser Arbeit bescha¨ftigt sich mit der Berechnung von gene-
tischenDistanzenzwischenOrganismen. UmdenVerwandtschaftsgradzwischen
Organismen zu messen, beispielsweise als Vorbereitung auf die Rekonstruktion
eines Stammbaums, ist es u¨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 u¨berfu¨hren. Die
popula¨rsten Operationen in diesem Zusammenhang sind Reversals und Trans-
positionen. Anstatt lediglich die Anzahl der beno¨tigten Operationen zu za¨hlen,
6vi
wurde ku¨rzlich vorgeschlagen, jede durchgefu¨hrte Operation hinsichtlich der
La¨ngederGensequenzzugewichten,aufdersieoperiert. Dieswurdevorkurzem
ausfu¨hrlich im Hinblick auf Reversals untersucht. Wir werden in dieser Arbeit
zeigen, wie sich die meisten der Resultate auch auf Transpositionen u¨bertragen
lassen, wobei wir untere und obere Schranken bezu¨glich des Diameters, dem
maximalen gewichteten Abstand zwischen zwei beliebigen Genomen, vorlegen
und auch Approximationsresultate beweisen.viiviii
Acknowledgments
A thesis cannot be created out of nothing, on the contrary, it is, besides the
personal work, the result of many discussions, pieces of advice, encouragement,
andlovingsupportwithandbyothers. Forthesereasons,Iwouldliketoexpress
my cordial thank to all those, who supported me during my doctoral studies
and while writing it down.
First ofall, I would like to thank my advisorJurajHromkoviˇcfor giving me the
opportunity to do my doctoral studies under his supervision, for his advice and
encouragement, and for initiating my studies on problems from bioinformatics.
I am also grateful to Berthold Vo¨cking for his kindness to act as a co-referee,
for his support during the last year, and for his warm welcome in his research
group.
ManythanksalsotomyformerandpresentcolleaguesandfriendsWalterUnger,
SebastianSeibert,andJoachimKupke,aswellastothewholeteamofComputer
Science1atRWTHAachen,formanyinspiringdiscussions,piecesofadvice(also
concerning LaTeX), pleasant common evenings and birthday parties, and the
nice working atmosphere. I would like to thank Yvonne Moh for enlightening
discussions on the topic of sorting by transpositions. Thanks also to Peter
WidmayerandhisgroupatETHZu¨richfortheirhospitalitywhileIwasstaying
with them.
VeryspecialthanksgotoHans-JoachimB¨ockenhauer,asacolleagueandfriend,
for his supervision, encouragement, advice, support, and in particular also for
his tireless proofreading of this thesis.
Last but not least, I am grateful t