Universitätsbibliothek Wien

RNA secondary structure prediction including pseudoknots

Beyer, Wolfgang (2010) RNA secondary structure prediction including pseudoknots.
Diplomarbeit, University of Vienna. Fakultät für Lebenswissenschaften
BetreuerIn: Hofacker, Ivo

[img]
Preview
PDF
Alle Rechte vorbehalten / All rights reserved

Download (2837Kb)
DOI: 10.25365/thesis.11587
URN: urn:nbn:at:at-ubw:1-29254.88966.172066-8

Link zu u:search

Abstract in English

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.

Schlagwörter in Englisch

RNA / secondary structure / structure prediction / pseudoknot / dynamic programming / bioinformatics

Abstract in German

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.

Schlagwörter in Deutsch

RNA / Sekundärstruktur / Strukturvorhersage / Pseudoknoten / Dynamic Programming / Bioinformatik

Item Type: Hochschulschrift (Diplomarbeit)
Author: Beyer, Wolfgang
Title: RNA secondary structure prediction including pseudoknots
Umfangsangabe: 95 S. : graph. Darst.
Institution: University of Vienna
Faculty: Fakultät für Lebenswissenschaften
Publication year: 2010
Language: eng ... Englisch
Supervisor: Hofacker, Ivo
Assessor: Hofacker, Ivo
Classification: 42 Biologie > 42.10 Theoretische Biologie
54 Informatik > 54.99 Informatik: Sonstiges
42 Biologie > 42.13 Molekularbiologie
42 Biologie > 42.99 Biologie: Sonstiges
AC Number: AC08519140
Item ID: 11587
(Das PDF-Layout ist ident mit der Druckausgabe der Hochschulschrift.)

Urheberrechtshinweis: Für Dokumente, die in elektronischer Form über Datennetze angeboten werden, gilt uneingeschränkt das österreichische Urheberrechtsgesetz; insbesondere sind gemäß § 42 UrhG Kopien und Vervielfältigungen nur zum eigenen und privaten Gebrauch gestattet. Details siehe Gesetzestext.

Edit item (Administrators only) Edit item (Administrators only)