title: RNA folding kinetics with basin hopping graphs
Creators: name: Kucharik, Marcel
Publisher: name: :none
Year: 2015

description: Während der letzten Jahre wurden zahlreiche neue Funktionen von RNA entdeckt. Neben dem Speichern und Transportieren von genetischer Information im Prozess der Transkription wirkt RNA auch als wichtige regulatorische und katalytische Einheit. Im Gegensatz zu DNA, welche in der Natur als Doppelstrang vorliegt, sind RNA-Moleküle Ketten von Nukleotiden in einem einzelnen Strang, wodurch sie auf sich selbst falten und dadurch vielfältige Strukturen mit potentiell unterschiedlichen Funktionen bilden können. Es gibt seit längerem, unter anderem im frei verfügbaren Vienna RNA package, effiziente Algorithmen um Strukturen und thermodynamische Eigenschaften von RNA-Molekülen zu berechnen. Die Funktion von RNA Molekülen ist eng verknüpft mit ihrer Fähigkeit, situationsabhängig verschiedene, jeweils spezielle, Konformationen einzunehmen, entweder von sich aus oder als Reaktion auf bestimmte zelluläre Signale, wie etwa durch Erkennen von Proteinen, Nukleinsäuren, Metallionen, Temperaturänderungen, oder auch während der RNA-Biosynthese selbst. Daher ist es von großer Bedeutung, den Prozess des Faltens und Umfaltens von RNA zu studieren und dominante Strukturen als Funktion der Zeit vorherzusagen. Ziel dieser Dissertation ist es, die geringe Auswahl an verfügbaren Programmen, welche die Faltungslandschaft untersuchen und Faltungskinetik berechnen können, zu erweitern. Der Schlüssel, um das komplexe molekulare System der Faltung von RNA zu verstehen, liegt im effizienten Modellieren der Energielandschaft des Faltungsprozesses von RNA. Da jedoch die Anzahl an möglichen Strukturen exponentiell mit der Sequenzlänge ansteigt, müssen dafür Teile des Zustandsraumes zusammengefasst werden. Die Topologie der Energielandschaft und insbesondere die Lage der lokalen Minima und der Sattelpunkte zwischen diesen, bestimmt die jeweilige Faltungskinetik. Zum Zwecke der Dimensionsreduzierung verwenden wir daher die lokalen Minima als Ausgangspunkt und verbinden zwei Minima nur, wenn ein direkte Kante zwischen diesen vorhanden ist, wodurch wir eine neue Abstraktion der Landschaft, genannt Basin Hopping Graph (BHG), erzeugen. Um diesen BHG zu berechnen, müssen wir nicht - wie frühere Programme - zuerst alle möglichen Strukturen generieren, sondern wir können durch eine Heuristik eine Approximation der Landschaft erhalten. Dieser Zugang erlaubt es uns, die Energielandschaft und Faltungskinetik von Molekülen mit einer Länge von bis zu 200 Nukleotiden zu untersuchen. Im Vergleich zu früheren, erschöpfenden Studien, welche nur bis zu 100 Nukleotide lange Sequenzen untersuchen konnten, fast ohne Genauigkeitverlust. Das Framework, welches in dieser Dissertation beschrieben ist, kann in 3 Teile gegliedert werden: 1.) die effiziente Berechnung von Lokalen Minima als Ausgangspunkt für die Reduktion des Zustandsraumes. 2.) die Erstellung des Basin Hopping Graphs, in welchem Knoten die lokalen Minima und Linien die Übergänge zwischen diesen repräsentieren, und 3.) die Berechnung der Faltungskinetik basierend auf dieser BHG-Abstraktion der Energielandschaft. Üblicherweise ist die Faltungskinetik als Markov Prozess modelliert, wobei die Zustände entweder Strukturen oder ganze Umgebungen lokaler Minima sind. Dieser Zugang erlaubt es uns, Systeme einer Größe von bis zu 10.000 Zuständen direkt zu lösen. Außerdem können wir, aufgrund der geringen Konnektivität des zugrundeliegenden Graphen, Systeme einer Größe von bis zu mehreren hunderttausend Nukleotiden auf eine praktikable Größe reduzieren, ohne merkbar an Genauigkeit einzubüßen. Schließlich erlaubt unser Zugang auch die Untersuchung des Formens und Umfaltens von Pseudoknoten. Wir haben eine Erweiterung unseres Frameworks implementiert, welche mit nicht-trivialen Sets an Pseudoknoten - genannt ``1-structures''- umgehen kann. Sie hilft uns, die Bedeutung der Bildung von Pseudoknoten während des Umfaltens von RNA-Molekülen zu zeigen, und dadurch die Genauigkeit unserer Abschätzung der Faltungskinetik zu verbessern.
description: The list of known roles of RNA has widely expanded during the last few years. RNA not only stores and transfers genetic information during transcription, but it also serves as an important regulatory and catalytic unit. While DNA appears double-stranded in nature, RNA molecules occur as single-stranded chains of nucleotides, and thus can fold onto themselves and create multiple structural patterns with potentially different functions. Efficient algorithms to compute the structures and thermodynamic properties of RNA molecules have been developed and are available in the Vienna RNA Package among others. However, the function of RNA molecules is intimately connected to their ability to adaptively acquire very distinct conformations on their own or in response to specific cellular signals including the recognition of proteins, nucleic acids, metal ions, changes in temperature, and even RNA biosynthesis itself. One therefore needs to study the process of (re)folding and infer dominant structure as the function of time. This thesis aims to extend the limited available tools to explore the folding landscape and predict the folding kinetics. The key to studying a complex molecular system such as the folding of RNA lies in building an efficient model of the energy landscape of the RNA folding process. Since the number of possible structures for one sequence increases exponentially with its length, a state space reduction approach needs to be applied. Folding kinetic properties are determined by the topology of the energy landscape, in particular the local minima and saddles that separate them. We therefore use the local minima as bases for the reduction and connect them only where a direct transition between minima is present to create a novel landscape abstraction called the Basin Hopping Graph (BHG). In order to create a BHG, we do not rely on enumeration as previous approaches, but use heuristics to obtain an approximation of the landscape. Our approach allows us to study the energy landscapes and the folding kinetics of molecules with lengths up to 200nt with almost no loss of accuracy as compared to previous exhaustive approaches capable of processing molecules only below 100nt. The framework described in this thesis can be split into three parts: 1.) efficient generation of local minima as the basis of state space reduction, 2.) creation of the Basin Hopping Graph, where vertices represent the local minima basins and edges represent the transitions between them, and 3.) computation of the folding kinetics based on the BHG landscape abstraction. The RNA folding kinetics is usually modeled as a Markov process, where the states are structures or whole local minima basins. Direct use of this approach allows us to solve systems of size up to 10,000 states. Nevertheless, due to the sparsity of the underlying graph, we are able to shrink systems with sizes of up to several hundred thousand states to the manageable level with no observable impact on the accuracy. Finally, our approach enables us to study the process of pseudoknot formation and refolding and we have implemented an extension of the framework for a non-trivial set of pseudoknot types called ``1-structures''. This extension helps us to show the importance of pseudoknot formation during refolding, and therefore, improve the accuracy of the folding kinetics estimation.