Albert-Ludwigs-Universtita¨t Freiburg im Breisgau/Germany Ant Colony Optimization based Inverse Folding of mono- and bistable RNA Macromolecules Dissertation zur Erlangung des akademischen Grades Doctor rerum naturalium (Dr. rer. nat.) vorgelegt dem Rat der Technischen Fakult¨at der Albert-Ludwigs Universt¨at Freiburg von Diplom Bioinformatiker Robert Kleinkauf 2016 Dekan Prof. Dr. Georg Lausen Gutachter Prof. Dr. Rolf Backofen Zweitgutachter Prof. Dr. Ivo Hofacker Kommissionsvorsitz Prof. Dr. Christoph Scholl Kommissionsbeisitz Prof. Dr. Gerald Urban Datum der Promotion 27.06.2016 I will take the Ring, though I do not know the way. Frodo Baggins The Council of Elrond ACKNOWLEDGEMENT ...I salute Mr. Frodo Baggins for carrying the Ring and ultimatively destroying it in the fires of Mount Doom... Well, yes, in that case, it was me who ’handed in’ the Ring! But it is very selfish to start with oneself, however, on the way to Mount Doom, Frodo received support, help and company through direct and indirect open and secret support by friends and benefactors. Without those fundamental prerequisites, he would not have gotten any further than to the borders of the Shire. Therefore, ... Iwant tothankRolfBackofen: Thankyouvery muchforgiving metheopportunity to be part of your chair in Freiburg and let me have my software tinkering workbench in the lab. ...I want to thank Ivo Hofacker for the kindness of accepting my thesis in the role as the second supervisor. ...I want to thank Martin Mann for his very patient style of mentorship, support and care. ...EspeciallyIwanttothankMonikaforbeingthegoodspriteallthetime! Withoutyou some peculiarities would have been unnecessary burdens! I also want to thank Stefan, the ghost in the machine. Without you, life would have been even more complicated, and I would have been stuck. ...I want to thank the ever changing composition of the Bioinformatics hair working alongside during the time. You have been the cause of the constant puzzle and the partially collaborative possibility to get back on track! Without you, the whole chair would be just another dusty place filled with nothing but streamlined smoothies and other strange characters! It was a nice experience with you! Last but not least I want to thank my family and my friends for their lively support, their constructive encouragement to diverse concerns and their being themselves in di- verse situations. Without you, this whole endeavor would have been impossible. Thank You! ABSTRACT SincethediscoveryofstructuralconformationsofDNAinthemiddleofthe20thcentury not only technologies that can elucidate structures of biologically relevant molecules have become more sophisticated, but the understanding of biological processes on the molecular level in general has grown tremendously in the last 60 years of research. In this same time, the early and dogmatic statement, according to which proteins are the only entities in molecular biological perception that can perform and provide necessary biological, e.g. enzymatic, functions within organisms, has undergone major revision. Of course, proteins do still perform the functions, which have been annotated, but in additiontothelevelofcontroloftheproteins,specificRNAmolecules,namelythenon- coding RNAs, have been accounted to the executing functional level so far exclusive to proteins. As in the case of the proteins, a functional RNA receives its specific function from a biologically active structure conformation, which strongly correlates with the respective RNA sequence. A comparatively large number of sequences can fold into a similar structural RNA conformation. However, small perturbations as for example pointmutationsorsequesteringofpartsoftheRNAsequencethroughotherinteracting entitiescanbekeyforthedisruptionofthefunctionalstructureoftheRNA.Alongside with the exploration of new RNA functionalities, RNA based technologies have been derived from single RNA based functionalities and corresponding mechanisms. Their analyticalandcreativepotentialincombinationwithhereofderivedcomputerprograms, e.g. predictingstructuresfromRNAsequencesorviceversa,predictingRNAsequences from structures, extend the classical biological approach beyond its investigative origin by adding a progressive engineering spirit to the former purely research character. In this dissertation, a computational RNA design tool and its application performance are presented. The tool is conceptually based on a relatively long heritage of tools, which can solve the ’RNA inverse fold’ problem: Given a structure (mostly secondary RNAstructure),theprogramspursuitdifferentstrategiestoproduceasequence,which can fold into the specified structure input. Classically a single structure was given as input. With the presented tool and its several capabilities of solving different levels of structuralcomplexitybasedonRNAsecondarystructures,notonlyanewwayofsolving the problem with the heuristic approach of the ant-colony optimization technique was introduced. Furthermore, new constraints such as the regulation of a very precise GC contentofthesolutionsequencehasbeengivenmajorconcernintheconceptaswellas new structural constraint possibilities of pseudoknots and bistable RNA entities. The new introduced features are benchmarked and tested on structure complexity specific data sets, which have been gained from online data bases and corresponding literature efforts. Alsocomparativerepresentationswithotherstateoftheartcomputerprograms are given. ZUSAMMENFASSUNG SeitderEntdeckungderStrukturkonformationvonDNAinderMittedes20.Jahrhun- derts wurden nicht nur die strukturellen Aufkl¨arungsmethoden fu¨r biologisch relevante Mikro- und Makromoleku¨le weiterentwickelt, vielmehr wurde auch das Wissen um bio- logische Prozesse auf molekularer Ebene enorm erweitert. Im selben Zeitrahmen wurde aber auch das sehr lange vorherrschende Dogma, nach welchem ausschließlich Proteine dieeinzigenEntit¨ateninnerhalbvonOrganismenseien,diebiologischrelevante,wiez.B. enzymatischeFunktioneninnehaben,durchWeiterentwicklungenundNeuentdeckungen wiederlegt,beziehungsweiseu¨berholt.Selbstverst¨andlichvollziehendieProteineweiter- hin deren annotierten charakteristischen Funktionen innerhalb der Organismen, den- nochwurdedieWeltderProteinefunktionalumdieKlassedernichtcodierendenRNA erweitert.DiesesindinderLage,¨ahnlicheAufgabenzubewerkstelligen,wiedieProteine selbst.WiebeidenProteinenleitetsichdieFunktioneinerRNAvonderenStrukturkon- formation ab, die wiederum von der jeweiligen RNA Sequenz abh¨angt. Obwohl eine im Vergleich zu den Proteinen gr¨oßere Anzahl an Sequenzen in immernoch die selbe RNA Struktur falten kann, k¨onnen durch kleine St¨orungen, wie zum Beispiel Punktmutatio- nenoderauchdurchInteraktionvonanderenFaktorenanbestimmtenStellenderRNA die Faltungskompetenz einer RNA Sequenz drastisch ver¨andern, so dass die eigentliche biologische Funktion unterbrochen werden kann. Mit den Entdeckungen neuer RNA Funktionen, wurden RNA basierende Techologien aus einzelnen Funktionen und deren Mechanismen abgleitet. Das hierbei innewohnende analytische und kreative Potenti- al der jeweiligen Technogien gekoppelt und einhergehend mit theoretisch-biologischen Computerprogrammen,diez.B.durchFaltungsvorhersagenfu¨rSequenzen,d.h.gegeben einer RNA Sequenz, deren Structur berechnen k¨onnen, bzw. umgekehrt, durch inverse FaltungsvorhersagenvonStrukturen,d.h.gegebeneinerStruktur,diejeweiligeSequenz berechnen k¨onnen, l¨asst es zu, bzw. fordert es gerade zu heraus, dass der klassische biologische Forschungsansatz u¨ber seinen investigativen Charakter hinausw¨achst und sich zu einer Ingeneursdisziplin weiterentwickelt. Innerhalb der vorliegenden Dissertation wird ein Konzept zum L¨osen des Problems des RNA Inverse Folding vorgestellt. Die Anwendungsperformanz der daraus hervorgegan- genen Implementierung wird vergleichend zu bisherigen Programmen dargestellt. Das ProblemdesRNAinversefoldingswurdeineinemrelativlangemErbevonProgrammen schon zu vor gel¨ost. Die jeweiligen Programme gehen hierbei das Progblem des RNA inverse folding auf unterschiedliche Arten und Weisen an und erlauben es mit einer jeweilig spezifischen L¨osungskomplexit¨at das Problem zu l¨osen. Auch die in der Arbeit verwendeteMethodederAmeisen-KolonieOptimirunghateineHistorieundkaminun- terschiedlichsten Bereichen bereits zum Einsatz. Alle RNA inverse folding Programme liefernRNASequenzen,diedieEigenschaftbesitzensollen,ineinealsEingabedefinier- te Sekund¨arstruktur der RNA falten zu k¨onnen. Hierbei wurde in klassischen Ans¨atzen eine einzelne Struktur als Eingabe zugelassen. Mit dem hier pr¨asentierten Programm undseinenunterschiedlichenM¨oglichkeitenderProbleml¨osungdesRNAinversefolding auf unterschiedlichen strukturellen Komplexit¨atsebenen der RNA SekundÃďrstruktur, wurde nicht nur ein neuartiger Weg zur L¨osung des Problems mit Hilfe der heuris- tischen ant-colony optimization (Ameisen Kolonie Optimierung) dargestellt, vielmehr wurden neuartige Problemrandbedingungen (Constraints) mit beru¨cksichtigt und zur L¨osung des Problems herangezogen, so dass es mit nun Hilfe des dargestellten Weges m¨oglichist,sehrpr¨azisedenGC-GehaltderzudesignendenRNASequenzeinstellenzu k¨onnen.Zus¨atzlichk¨onnendurchdieEntwicklunggeeigneterDarstellungsm¨oglichkeiten komplexe Struktureingaben gemacht werden, so dass es mit dem vorgestellten Ansatz auch m¨oglich ist, Pseudoknoten und bistabile Strukturkonformationen zu modellieren. Nach einer generellen EinfÃijhrung in die Themen nicht codierende RNA und deren Faltung, wird die Adaption der Ameisen Kolonie Optimierung hinsichtlich des RNA inverse foldings afgebaut. Die jeweilig benutzten Konzepte und deren Zusammenspiel werdendargestellt.LetztlichwerdendieF¨ahigkeitendesProgrammsinVergleichs-und Leistungstests auf der Basis von verschiedenen Strukturkomplexit¨aten mit Hilfe von Datenermittelt,dieausOnline-Datenbankenentnommenwurden,sowieausLiterturre- cherchenhervorgegangensind.VergleichendeErgebnissezubisherigen’state-of-the-art’ Programmen werden pr¨asentiert.