Detailansicht
Grammatical approaches to problems in RNA bioinformatics
Christian Höner zu Siederdissen
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Lebenswissenschaften
Betreuer*in
Ivo Hofacker
DOI
10.25365/thesis.28648
URN
urn:nbn:at:at-ubw:1-29596.38582.317055-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Formale Sprachen und Grammatiken sind ein klassisches Thema in der Informatik und maechtiges Werkzeug um die Komplexitaet algorithmischen Designs zu beherrschen. In dieser Arbeit werden vier wissenschaftliche Arbeiten zur Loesung von Problemen in der computergestuetzten Biologie praesentiert. Diese Probleme, ausgewaehlt aus dem Bereich der RNA-Bioinformatik, sind die Vorhersage von RNA Sekundaerstrukturen und die Suche nach homologen Sequenzen bekannter nichtkodierender (nc-) RNA Familien. Ausserdem wird eine effiziente Einbettung dieser Grammatiken in eine funktionale Programmiersprache vorgestellt.
Zuerst werden zwei Algorithmen zu strukturellen RNA Familien praesentiert. Eine strukturelle ncRNA Familie is ein Alignment von verwandten RNA Sequenzen zusammen mit ihrer gemeinsamen Struktur. Sie kann in ein stochastisches Modell verwandelt werden. Solch ein Modell ermoeglicht das Auffinden von weiteren verwandten Sequenzen auf genomweiter Ebene. Verschiedene Moeglichkeiten existieren um solche Modelle zu erzeugen. In Kapitel 5 werden die Konsequenzen verschiedener Kodierungen diskutiert.
Der Algorithmus in Kapitel 6 bietet eine Loesung fuer ein anderes Problem mit ncRNA Familien. Um die Qualitaet der vorhandenen Familien sicherzustellen wird eine Methode bereitgestellt, die es erlaubt festzustellen ob eine Familie genuegend stark von allen anderen Familien differenziert.
Der Algorithmus zu erweiterten RNA Sekundaerstrukturen in Kapitel 7 erweitert das nearest-neighbor Sekundaerstrukturmodell zu einem das das bekannte Wissen zu RNA Strukturen besser reflektiert. Insbesondere sind Basenpaarungen ueber das kanonische Watson-Crick Paarungsmodell hinaus moeglich. Solch ein erweitertes Modell dient der besseren Vorhersage von Basenpaarungen in Regionen welche als wichtig in der biologischen Rolle vieler RNAs erkannt wurden.
Zuletzt wird eine domaenenspezische Sprache, eingebettet in die funktionale Programmiersprache Haskell, in Kapitel 8 besprochen. Eine solche Einbettung ermoeglicht ein einfacheres Entwickeln in einer Hochsprache. Insbesondere ist es moeglich die vorherigen Algorithmen einfach zu formulieren und zu erweitern ohne auf C-nahe Geschwindigkeit verzichten zu muessen.
Abstract
(Englisch)
Formal languages and grammars are a classical topic in computer science and a powerful tool to deal with complexity in terms of algorithmic design. In this thesis, four scientific works are presented that aim to solve problems in computational biology. These problems, from the area of RNA bioinformatics, are prediction of RNA secondary structure and the search for homologous sequences of known non-coding (nc-) RNA families. Also, an efficient embedding of these grammars in a functional programming language is presented.
First, two algorithms on structural non-coding RNA families are presented. A structural ncRNA family is an alignment of related RNA sequences together with their consensus structure. From it a stochastic model can be calculated which, in turn, can be used to search for further related sequences on a genome-wide scale. A number of different possibilities exist to produce a stochastic model from a structural alignment. In Chapter 5 the ramifications of different encodings are discussed.
The algorithm in Chapter 6 provides a solution to another problem on ncRNA families. In order to facilitate quality control on ncRNA family libraries, a method is provided to determine whether an RNA family is sufficiently well separated from all other families.
The algorithm on extended RNA secondary structures presented in Chapter 7 extends the nearest-neighbor secondary structure model toward better reflection of the knowledge gained from RNA tertiary structure. In particular, base pairing beyond the six canonical Watson-Crick pairs is taken into account. Some regions of the RNA with important biological roles contain almost exclusively non-canonical base pairs which can now be predicted in contrast to previous approaches which would model such regions as essentially unstructured.
Finally, in Chapter 8, a domain-specific language embedded in the functional programming language Haskell is presented. This embedding allows for simplified algorithmic development on a high level. In particular, this embedded language makes it possible to write and extend the previous algorithms easily, while providing performance close to that of the C programming language.
Schlagwörter
Schlagwörter
(Englisch)
RNA secondary structure RNA families covariance model semantic ambiguit discriminatory power context-free grammar domain-specific language functional language Haskell
Schlagwörter
(Deutsch)
RNA Sekundaerstruktur RNA Familien Covarianzmodell Semantische Mehrdeutigkeit Trennschaerfe kontext-freie Grammatik domaenenspezifische Sprache funktionale Sprache Haskell
Autor*innen
Christian Höner zu Siederdissen
Haupttitel (Englisch)
Grammatical approaches to problems in RNA bioinformatics
Paralleltitel (Deutsch)
Grammatikalische Ansätze für Probleme in der RNA Bioinformatik
Publikationsjahr
2013
Umfangsangabe
142 S. : graph. Darst.
Sprache
Englisch
Beurteiler*innen
Rolf Backofen ,
Thomas Rattei
Klassifikationen
42 Biologie > 42.13 Molekularbiologie ,
54 Informatik > 54.89 Angewandte Informatik: Sonstiges
AC Nummer
AC11591391
Utheses ID
25577
Studienkennzahl
UA | 091 | 490 | |