Sebastian Wild

• It has been observed that for understanding the biological function of certain RNA molecules, one has to study joint secondary structures of interacting pairs of RNA. In this thesis, a new approach for predicting the joint structure is proposed and implemented. For this, we introduce the class of m-dimensional context-free grammars --- an extension of stochastic context-free grammars to multiple dimensions --- and present an Earley-style semiring parser for this class. Additionally, we develop and thoroughly discuss an implementation variant of Earley parsers tailored to efficiently handle dense grammars, which embraces the grammars used for structure prediction. A currently proposed partitioning scheme for joint secondary structures is transferred into a two-dimensional context-free grammar, which in turn is used as a stochastic model for RNA-RNA interaction. This model is trained on actual data and then used for predicting most likely joint structures for given RNA molecules. While this technique has been widely used for secondary structure prediction of single molecules, RNA-RNA interaction was hardly approached this way in the past. Although our parser has O(n^3 m^3) time complexity and O(n^2 m^2) space complexity for two RNA molecules of sizes n and m, it remains practically applicable for typical sizes if enough memory is available. Experiments show that our parser is much more efficient for this application than classical Earley parsers. Moreover the predictions of joint structures are comparable in quality to current energy minimization approaches.
• Es ist bekannt, dass die biologische Funktion bestimmter RNA-Moleküle von der Struktur abhängt, die das Molekül gemeinsam mit einem anderen RNA-Molekül formt, der sogenannten joint secondary structure. Wir stellen in dieser Arbeit einen neuen Ansatz zu deren Vorhersage vor. Dazu führen wir die Klasse der m-dimensionalen kontextfreien Grammatiken ein --- einer Erweiterung stochastischer kontextfreier Grammatiken auf mehrere Dimensionen --- und stellen einen Semiring-Earley-Parser für diese Klasse vor. Außerdem entwickeln wir eine Implementierungsvariante für Earley-Parser, die speziell dichte Grammatiken effizient verarbeitet. Dazu zählen insbesondere die Grammatiken, die zur Strukturvorhersage verwendet werden. Wir übersetzen ein aktuelles Partitionierungsschema für joint secondary structures in eine zwei-dimensionale kontextfreie Grammatik, die ein stochastisches Modell für gemeinsame Sekundarstrukturen impliziert. Dieses Modell trainieren wir anhand bekannter RNA-RNA-Interaktionen und sagen dann wahrscheinlichste Strukturen vorher. Diese Idee wurde bereits erfolgreich auf einzelne RNA-Moleküle angewandt, kaum jedoch auf interagierende RNA-Paare. Obwohl unser Parser Laufzeit in O(n^3 m^3) und Speicherplatz in O(n^2 m^2) für zwei RNAs der Länge n und m benötigt, sind typische Eingabegrößen mit vertretbarem Aufwand vorhersagbar, sofern genug Arbeitsspeicher zu Verfügung steht. Experimente zeigen, dass unsere Earley-Implementierung für diese Anwendung deutlich effizienter arbeitet als klassische Earley-Parser. Des Weiteren ist die Qualität der Vorhersagen vergleichbar mit der aktueller Energie-Minimierungsansätze.