Optimizing algorithms for the comparative analysis of non-coding RNAs

Medientyp: E-Book; Hochschulschrift

Titel: Optimizing algorithms for the comparative analysis of non-coding RNAs

Beteiligte: Otto, Christina [Verfasser]; Backofen, Rolf [Akademischer Betreuer]

Erschienen: Freiburg: Universität, 2015

Umfang: Online-Ressource

Sprache: Englisch

DOI: 10.6094/UNIFR/10162

Identifikator:

Schlagwörter: Non-coding RNA ; Bioinformatik ; Algorithmentheorie ; RNA secondary structure ; Simultaneous alignment and folding of RNAs ; Sparsification ; (local)doctoralThesis ; Hochschulschrift

Entstehung:

Hochschulschrift: Dissertation, Universität Freiburg, 2015

Anmerkungen:

Beschreibung: Zusammenfassung: Non-coding RNAs (ncRNAs) perform essential functions within the cell, such as the regulation of gene expression or catalytic functionalities. Until today, however, the function of most ncRNA molecules is still unknown. As the structure is key to the function of many ncRNAs, much effort has been devoted to the computational structure prediction of ncRNAs and the subsequent functional characterization. This thesis makes important contributions to this field of research by introducing novel fast methods for revealing the functionalities of ncRNA molecules.The basis of these methods is a novel sparsification technique, the ensemble-based sparsification, which is introduced in the first part of this thesis. Identifying likely structural elements within the structure ensembles of two RNA sequences allows to drastically reduce the search space and leads to a significant shorter runtime. We demonstrate the efficiency of this novel technique for speeding up algorithms for the identification of sequence-structure motifs and simultaneous alignment and folding. However, the applicability of ensemble-based sparsification is not limited to these instances such that this novel technique offers the possibility to speed up other RNA-related tasks in the future as well.In the second part of this thesis, we introduce the novel method ExpaRNA-P for identifying sequence-structure motifs common to two RNAs in entire Boltzmann-distributed structure ensembles. The core algorithm of the existing approach ExpaRNA solves this problem for a priori known input structures. However, such structures are rarely known; moreover, predicting them computationally beforehand is not an option, since single sequence structure prediction is highly unreliable. In our novel approach ExpaRNA-P, we match and fold RNAs simultaneously, analogous to the well-known simultaneous alignment and folding of RNAs. While this implies much higher flexibility compared with ExpaRNA, the novel approach ExpaRNA-P has the same very low complexity (quadratic in time and space), which is enabled by our novel ensemble-based sparsification. Furthermore, we devise a generalized chaining algorithm to compute compatible subsets of ExpaRNA-P’s sequence-structure motifs. We utilize the best chain asanchor constraints for the sequence-structure alignment tool LocARNA, resulting in the very fast RNA alignment program ExpLoc-P. ExpLoc-P is benchmarked in several variants and versus state-of-the-art programs. Across a benchmark set of typical ncRNAs, ExpLoc-P has similar accuracy to LocARNA but is on average four times faster, while it achieves a speedup over 30-fold for the longest benchmark sequences (=~400nt).In the third part of this thesis, we present the two novel methods PARSE and SPARSE for simultaneous alignment and folding. PARSE utilizes a lightweight energy model that is derived from a full-featured energy model to score structural contributions. In addition, it integrates Sankoff’s original structure prediction flexibility. By utilizing LocARNA’s base pair filter, a time complexity of O(n⁴) can be obtained for PARSE. Furthermore, we show how the novel ensemble-based sparsification can be applied to derive the sparsified variant SPARSE with a significantly reduced runtime of O(n²). This means that we introduce the firstmethod with quadratic runtime for simultaneous alignment and folding that does not resort to sequence-based heuristics that could corrupt the alignment quality – as for example the tool RAF does. Furthermore, we demonstrate the effectiveness of our method on benchmarks of real RNA sequences against the state-of-the-art programs LocARNA and RAF. The low computational complexity of SPARSE and RAF is reflected in an overall speedup of around 4 over LocARNA. Whereas RAF’s performance drops drastically for instances with low sequence identities, SPARSE benefits from the structure-based optimization and achieves similar alignment quality as LocARNA. Importantly, both tools produce high-quality alignments even for the hard instances with low sequence identity. In addition, we demonstrate the advantage of SPARSE’s flexible structure prediction model in comparison with LocARNA. For all sequence identity regions, SPARSE improves LocARNA’s structure prediction quality.In the final part of this thesis, we propose a general theory to describe and implement sparsification in dynamic programming (DP) algorithms. So far, sparsification is mostly a collection of loosely related examples and no general, well understood theory has been developed yet. Our approach is formalized as an extension of algebraic dynamic programming (ADP), which makes it applicable to a variety of algorithms and scoring schemes. In particular, this is the first approach that shows how to sparsify algorithms with scoring schemes that go beyond simple minimization or maximization – as for example the enumeration of suboptimal solutions. On the basis of Nussinov’s algorithm, we show how to sparsify RNA structure prediction algorithms.In summary, this thesis provides novel approaches to decipher the functionalities of ncRNAs. Particularly, we aim at maintaining high quality output while focusing at the same time on making our novel approaches most efficient regarding the runtime. Moreover, we demonstrate in this work the superior performance of our novel methods compared with state-of-the-art programs on real RNA sequences

Zusammenfassung: Nichtcodierende RNAs (ncRNAs) führen essentielle Aufgaben innerhalb der Zelle aus, wie etwa die Regulierung der Genexpression oder katalytische Funktionen. Jedoch ist bis heute die Funktion der meisten ncRNA Moleküle noch immer unbekannt. Da die Struktur entscheidend für die Funktion vieler ncRNAs ist, wurden große Anstrengungen in die computergestützte Strukturvorhersagevon ncRNAs und die anschließende funktionelle Charakterisierung investiert.Diese Arbeit leistet wichtige Beiträge zu diesem Forschungsfeld, indem neue, schnelle Methoden präsentiert werden, die die Funktionsweisen von ncRNA Molekülen aufdecken.Die Basis dieser Methoden ist eine neuartige Sparsifizierungsmethode, die Ensemble-basierte Sparsifizierung, die im ersten Teil dieser Arbeit eingeführt wird. Die Identifikation wahrscheinlicher struktureller Elemente innerhalb der Strukturensembles von zwei RNA Sequenzen erlaubt es den Suchraum drastisch zu reduzieren und führt zu einer signifikant kürzeren Laufzeit. Wir demonstrieren die Effizienz dieser neuen Methode, indem Algorithmen für die Identifizierung von Sequenz-Struktur-Motiven und die simultane Berechnung von Alignment und Faltung beschleunigt werden. Die Einsetzbarkeit der Ensemble-basierten Sparsifizierung ist jedoch nicht auf diese Anwendungen beschränkt, so dass diese neue Methode die Möglichkeit bietet, in Zukunft auch andere RNA-bezogene Aufgaben zu beschleunigen.Im zweiten Teil dieser Arbeit präsentieren wir die neue Methode ExpaRNA-P, die Sequenz-Struktur-Motive zwischen zwei RNAs in gesamten Boltzmann-verteilten Strukturensembles identifiziert. Der Kern-Algorithmus des existierenden Ansatzes ExpaRNA löst dieses Problem für a priori bekannte Eingabe-Strukturen. Solche Strukturen sind jedoch selten bekannt; darüber hinaus ist die computergestützte Vorhersage im Voraus keine Lösung, da die Faltung einzelner Sequenzen höchst unzuverlässig ist. In unserem neuen Ansatz ExpaRNA-P wird der Mustervergleich simultan zu der Faltung der RNAs durchgeführt, analog zu der bereits bekannten simultanen Berechnung von Alignment und Faltung von RNAs. Während dies, verglichen mit ExpaRNA, eine viel höhere Flexibilität impliziert, hat der neue Ansatz ExpaRNA-P die gleiche sehr geringe Komplexität (quadratisch in Zeit und Speicherplatz), die durch unsere neue Ensemble-basierte Sparsifizierung ermöglicht wird. Zusätzlich entwickeln wir einen generalisierten Chaining Algorithmus, der kompatible Teilmengen von ExpaRNA-P’s Sequenz-Struktur-Motiven berechnet. Wir benutzen die beste Auswahl als Ankerpunkte für das Sequenz-Struktur-Alignment Tool LocARNA, was zu dem sehr schnellen RNA Alignment Programm ExpLoc-P führt. ExpLoc-P wird in verschiedenen Varianten und im Vergleich zu dem Stand der Technik entsprechenden Ansätzen bewertet. In einem Benchmark typischer ncRNAs erreicht ExpLoc-P eine ähnliche Genauigkeit wie LocARNA, ist aber im Durchschnitt vier mal schneller. Darüber hinaus erzielt es einen über 30-fachen Speedup für die längsten Benchmarksequenzen (=~400nt).Im dritten Teil der Arbeit stellen wir die zwei neuen Methoden PARSE und SPARSE für die simultane Berechnung von Alignment und Faltung vor. PARSE verwendet ein leichtgewichtiges Energie-Modell welches von einem vollständigen Energie-Modell herrührt, um die strukturellen Beiträge zu bestimmen. Zusätzlich integriert es Sankoff’s ursprüngliche Flexibilität der Strukturvorhersage. Indem LocARNA’s Basenpaar-Filter verwendet wird, kann eine Zeitkomplexität von O(n⁴) für PARSE erreicht werden. Darüber hinaus zeigen wir, wie die neue Ensemble-basierte Sparsifizierung angewendet werden kann, um die sparsifizierte Variante SPARSE mit erheblich reduzierter Laufzeit von O(n²) zu erzielen. Das bedeutet, dass wir die erste Methode für die simultane Berechnung von Alignment und Faltung mit quadratischer Laufzeit vorstellen, welche nicht auf Sequenz-basierte Heuristiken zurückgreift, die die Alignmentqualität beeinträchtigen können – wie es zum Beispiel das Tool RAF tut. Zusätzlich zeigen wir die Effektivität unserer Methode auf Benchmarks realer RNA Sequenzen im Vergleich zu den Stand der Technik entsprechenden Ansätzen LocARNA und RAF. Die niedrige Komplexität von SPARSE und RAF zeigt sich in einem Gesamt-Speedup von ungefähr 4 im Vergleich zu LocARNA. Während jedoch RAF’s Leistungsfähigkeit für Instanzen mit niedriger Sequenzidentität drastisch fällt, profitiert SPARSE von der Struktur-basierten Optimierung und erreicht eine ähnliche Alignmentqualität wie LocARNA. Insbesondere erzeugen beide Tools hoch-qualitative Alignments sogar für die schwierigen Instanzen mit niedriger Sequenzidentität. Wir demonstrieren außerdem den Vorteil des flexiblen Strukturvorhersage-Modells von SPARSE im Vergleich zu LocARNA. SPARSE verbessert die Qualität der Strukturvorhersage von LocARNA für alle Sequenzidentitätsbereiche.Im letzten Teil dieser Arbeit schlagen wir eine allgemeine Theorie vor, um Sparsifizierung innerhalb von Algorithmen mit dynamischer Programmierung (DP) zu beschreiben und zu implementieren. Bis jetzt ist Sparsifizierung hauptsächlich eine Sammlung von lose zusammenhängenden Beispielen und es wurde noch keine allgemeine, wohlverstandene Theorie entwickelt. Unser Ansatz ist als Erweiterung der algebraischen dynamischen Programmierung (ADP) formalisiert, wodurch er auf eine Vielzahl von Algorithmen und Bewertungsschemata anwendbar ist. Insbesondere ist dies der erste Ansatz, der zeigt wie Algorithmen mit Bewertungsschemata, die über die einfache Minimierung oder Maximierung hinausgehen, sparsifiziert werden können – wie zum Beispiel die Aufzählung von suboptimalen Lösungen. Anhand des Nussinov Algorithmus zeigen wir, wie Algorithmen zur RNA Strukturvorhersage sparsifiziert werden können.Insgesamt stellt diese Arbeit neue Ansätze bereit, um die Funktionsweisen von ncRNAs zu entschlüsseln. Insbesondere streben wir an, hochwertige Ergebnisse zu erhalten, während wir uns gleichzeitig darauf konzentrieren unsere neuen Ansätze so effizient wie möglich bezüglich der Laufzeit zu gestalten. Darüber hinaus zeigen wir in dieser Arbeit die überlegene Leistungsfähigkeit unserer neuen Methoden verglichen mit dem Stand der Technik entsprechenden Programmen auf echten RNA Sequenzen

Zugangsstatus: Freier Zugang

Nur in Feld suchen:

Zuletzt gesuchte Begriffe: