RNA secondary structure prediction including pseudoknots

Wolfgang Beyer

doi:10.25365/thesis.11587

You are here: University of Vienna PHAIDRA Detail o:1269450

Title (eng)

RNA secondary structure prediction including pseudoknots

Parallel title (deu)

Vorhersage von RNA Sekundärstrukturen mit Pseudoknoten

Author

Wolfgang Beyer

Advisor

Ivo Hofacker

Assessor

Ivo Hofacker

Abstract (deu)

RNAs sind sehr wichtige Biomoleküle. Früher sah man in ihnen nur die Zwischenstufe zwischen DNA, dem Träger der genetischen Information, und Proteinen, den Katalysatoren biochemischer Reaktionen. Heute wissen wir von der Existenz verschiedenster Klassen von RNAs, die selbst katalytische Eigenschaften haben. Die Funktion eines RNA-Moleküls ist von seiner dreidimensionalen Struktur (der Tertiärstruktur) abhängig, die wiederum von den Basenpaarung innerhalb des RNA-Moleküls (der Sekundärstruktur) abhängig ist. Um von der linearen Sequenz (der Primärstruktur) auf die Funktion eines RNA-Moleküls schließen zu können, sollte man im Idealfall in der Lage sein, allein von der Sequenz die komplette dreidimensionale Struktur vorhersagen zu können. Weil aber RNA-Faltung als hierarchischer Prozess betrachtet werden kann, wobei sich die Sekundärstruktur vor jeglichen tertiären Interaktionen ausbildet, kann schon die Sekundärstruktur als Ausgangspunkt für die funktionelle Analyse dienen. Dementsprechend ist RNA-Sekundärstrukturvorhersage ein zentrales Problem der Bioinformatik. Der Großteil aller RNA-Basenpaare ist perfekt verschachtelt, was bedeutet, daß alle Nukleotide, die von einem Basenpaar umschlossen sind, nicht mit Nukleotiden außerhalb dieses Basenpaars interagieren. Diese Eigenschaft erlaubt es, die gesamte RNA Sekundärstruktur in einfachere und voneinander unabhängige Substrukturen, die sogenannten Loops, für deren freie Energien man Parameter kennt, zu zerlegen. Dynamic Programming, der am häufigsten verwendete Ansatz zur RNA-Sekundärstrukturvorhersage, ist auf diese Loop-Zerlegung angewiesen. Pseudoknoten, von denen man in letzter Zeit immer mehr entdeckt hat, sind RNA-Strukturen, die diesen vereinfachenden Schritt nicht zulassen. Bei einem Pseudoknoten formen Nukleotide innerhalb eines Loops Basenpaare mit Nukleotiden außerhalb des Loops und verletzen damit die Bedingung der perfekt verschachtelten Sekundärstrukturen. Deshalb ist die Berücksichtigung von Pseudoknoten rechnerisch komplizierter und aufwändiger und herkömmliche Algorithmen zur RNA-Sekundärstrukturvorhersage schließen Pseudoknoten der Einfachkeit halber aus. Erst in den letzten Jahren wurden Ansätze zur Vorhersage von Pseudoknoten entwickelt, die entweder auf Dynamic Programming oder auf heuristischen Methoden beruhen. In dieser Diplomarbeit präsentiere ich PKplex, einen neuen, Dynamic Programming-basierten Algorithmus zur Vorhersage von RNA Sekundärstrukturen mit Pseudoknoten. Zuerst wird die grundlegende Idee hinter PKplex und ihre Umsetzung beschrieben, und dann wird der Algorithmus auf einen großen Datensatz bekannter RNA Pseudoknoten angewandt und seine Ergebnisse mit denen anderer publizierter Algorithmen verglichen.

Abstract (eng)

RNAs are very important biological molecules. Previously they were thought of as being only the intermediary between DNA, which carries the genetic information, and proteins, which catalyze biochemical reactions. Today we know about the existence of diverse classes of RNAs which exhibit catalytic functions themselves. The function of an RNA molecule is dependent on its three-dimensional structure (the tertiary structure), which is in turn dependent on the base pairing within the RNA molecule (the secondary structure). In order to draw functional conclusions from the linear sequence of an RNA molecule (the primary structure), one would ideally be able to predict the whole three-dimensional fold based on the sequence alone. But because the folding process of RNA is mainly a hierarchical process, with the secondary structure forming before any tertiary interactions, the secondary structure can already be used as a starting point for functional analysis. Therefore prediction of the secondary structure of RNAs is a central problem in bioinformatics. The majority of all RNA base pairs are perfectly nested, meaning that all nucleotides enclosed by a specific base pair do not interact with any nucleotides outside of this base pair. This property allows the decomposition of the whole RNA secondary structure into simpler and independent substructures called loops, for which free energy parameters exist. The most common approach to predicting RNA secondary structures is based on dynamic programming, which relies heavily on this loop decomposition. A certain group of RNA secondary structures called pseudoknots, of which more and more have been discovered in recent years, do not allow this simplification. In a pseudoknot nucleotides within a loop form base pairs with nucleotides outside of the loop, violating the condition of perfectly nested secondary structures. Pseudoknots are therefore more difficult and more expensive to handle computationally and the standard RNA secondary structure prediction algorithms simply do not take pseudoknots into account. Approaches for predicting pseudoknots have only been developed in recent years, some of them based on dynamic programming, others on heuristic methods. In this diploma thesis I present PKplex, a new dynamic programming based algorithm for the prediction of RNA secondary structures including pseudoknots. After describing the basic idea behind PKplex and its implementation, the algorithm is then evaluated against a large set of known RNA pseudoknots and its performance compared with other published algorithms.

Keywords (eng)

RNAsecondary structurestructure predictionpseudoknotdynamic programmingbioinformatics

Keywords (deu)

RNASekundärstrukturStrukturvorhersagePseudoknotenDynamic ProgrammingBioinformatik

Subject (deu)

Theoretische Biologie

Subject (deu)

Informatik: Sonstiges

Subject (deu)

Molekularbiologie

Subject (deu)

Biologie: Sonstiges