Efficient methods for matching RNA sequence-structure patterns

Abstract

The secondary structure of RNA molecules is intimately related to their function and often more conserved than the sequence. Hence, the important task of searching databases for functionally related RNAs evolving from a common ancestor, i.e. RNA homology search, requires to match sequence-structure patterns. However, current tools for this task have, in the best case, a running time that is only linear in the size of the sequence databases. Consequently, they are not well suited for searching large databases. This can be explained by their failure to use an appropriate index data structure for fast searches. Furthermore, a disadvantage of current tools for matching sequence-structure patterns is their limited capacity to find approximate matches to structural RNA patterns, which poses an obstacle to sensitive and specific searches. In this thesis, we present novel methods and readily applicable software for fast matching of RNA sequence-structure patterns in sequence databases. Our first method is based on affix arrays, a recently introduced index data structure, preprocessed from the target database. Unlike established index data structures like suffix trees or arrays, affix arrays support bidirectional pattern search, which is required for efficiently handling the structural constraints of the pattern. Structural patterns like stem-loops can be matched inside out, such that the loop region is matched first and then the pairing bases on the boundaries are matched consecutively. This allows to exploit base pairing information for search space reduction and leads to an expected running time that is sublinear in the size of the sequence database. To support the description of RNA molecules that fold into complex secondary structures with multiple ordered sequence-structure patterns, we incorporate in the pattern search a new chaining approach. The chaining removes spurious matches from the set of intermediate results, in particular of patterns with little specificity. In benchmark experiments on the Rfam database, our method runs up to two orders of magnitude faster than previous methods. While our first method is extremely fast, it has limited capacity to find approximate matches to RNA patterns, such as matches with insertions or deletions at arbitrary positions relative to the pattern or mutations affecting the secondary structure. This limitation often does not allow to define patterns that are specific and sensitive enough to match the sequences belonging to the sought RNA family. Therefore, we have developed novel index-based and online algorithms for approximate matching of RNA sequence-structure patterns supporting a full set of edit operations on single bases and base pairs. Due to the high computational cost of the underlying sequence-structure alignment problem, our algorithms efficiently compute semi-global alignments of structural RNA patterns and substrings of the target sequence whose costs satisfy a user-defined sequence-structure edit distance threshold. For this purpose, we introduce a new computing scheme to reuse the entries of the required dynamic programming matrices for all substrings and combine it with a technique for avoiding the alignment computation of non-matching substrings. Our new index-based algorithms exploit suffix arrays preprocessed from the target database and achieve running times that are sublinear in the size of the searched sequences. Moreover, all the new algorithms integrate our approach for chaining matches. Benchmark experiments show that our best index-based algorithm is two to three orders of magnitude faster than previous methods.

Die Sekundärstruktur eines RNA Moleküls ist eng mit seiner Funktion verbunden und häufig stärker konserviert als die Sequenz. Folglich ist für die wichtige Aufgabe der Datenbanksuche nach funktionell ähnlichen RNAs, welche sich evolutionär von einem gemeinsamen Vorgängermolekül entwickelt haben (RNA Homologiesuche), die Suche nach Sequenz-Struktur-Mustern von großer Bedeutung. Allerdings verfügen aktuelle Werkzeuge für diese Aufgabe nur über ein Laufzeitverhalten, welches im besten Fall linear von der Größe der zu durchsuchenden Sequenzdatenbank abhängt. Deshalb sind sie häufig wenig geeignet für die Suche in großen Datenbanken. Der Grund hierfür ist der Verzicht auf Index-Datenstrukturen zur Beschleunigung der Suche. Ein weitere Nachteil aktueller Werkzeuge zur Suche mit Sequenz-Struktur-Mustern, welcher insbesondere ein Hindernis bei sensitiven und spezifischen Suchen darstellt, ist die nur sehr eingeschränkt vorhandene Möglichkeit approximative Treffer struktureller RNA Suchmuster zu finden. In dieser Arbeit präsentiere ich neue Methoden und direkt einsetzbare Werkzeuge zur schnellen Suche mit RNA Sequenz-Struktur Mustern in großen Sequenzdatenbanken. Die erste vorgestellte Methode basiert auf Affix-Arrays, einer relativ neuen Indexdatenstruktur, welche durch Vorverarbeitung der Zieldatenbank erstellt wird. Im Gegensatz zu etablierten Indexdatenstrukturen wie Suffixbäumen oder arrays, unterstützen Affix-Arrays die bidirektionale Mustersuche. Diese ist notwendig, um die strukturellen Nebenbedingungen eines Suchmusters effizient zu berücksichtigen. Strukturelle Muster, wie zum Beispiel Stem-Loops können von innen nach außen gesucht werden, sodass zuerst die innere Loop Region und dann die paarenden Basen des Stem-Bereiches konsekutiv gesucht werden. Diese Vorgehensweise erlaubt das Ausnutzen von Basenpaarinformationen, um den Suchraum zu reduzieren und führt zu einer erwarteten Laufzeit, welche sich sublinear zur Größe der zu durchsuchenden Sequenzdatenbank verhält. Um die Beschreibung von RNA Molekülen, welche in komplexere Sekundärstrukturen mit multiplen Sequenz-Struktur Mustern falten, zu unterstützen, wurde eine neue Methode zur Verkettung (Chaining) von Mustertreffern in die Mustersuche integriert. Durch die Verkettung werden zufällige Mustertreffer, insbesondere hervorgerufen durch unspezifische Muster, aus der Menge von Zwischenresultaten entfernt. In Benchmark-Experimenten auf der Rfam Datenbank war unsere Methode um bis zu zwei Größenordnungen schneller als bisherige Methoden. Während die erste in dieser Arbeit vorgestellte Methode zur effizienten Suche mit Sequenz-Struktur- Mustern sehr schnell ist, verfügt sie nur über beschränkte Möglichkeiten approximative Treffer eines RNA Suchmusters, welche zum Beispiel Insertionen/Deletionen an beliebigen Positionen oder die Sekundärstruktur verändernde Mutationen enthalten, zu finden. Diese Einschränkung erlaubt oftmals nicht die Beschreibung einer RNA Familie mit einem Muster, welches sowohl sensitiv, als auch spezifisch genug ist, um alle Familienmitglieder zu finden. Aus diesem Grund habe ich neue indexbasierte und online Verfahren zur approximativen Suche mit Sequenz-Struktur-Mustern entwickelt, welche Edit-Operationen auf Einzelbasen und Basenpaaren erlauben. Aufgrund des hohen Berechnungsaufwands des hierfür erforderlichen Sequenz-Struktur-Alignments, berechnet das vorgestellte Verfahren effizient nur semi-globale Alignments zwischen strukturellen RNA Mustern und Teilworten der zu durchsuchenden Sequenz, deren Alignmentkosten einen benutzerspezifischen Schwellwert nicht überschreiten. Hierzu wird ein neues, auf dynamischer Programmierung (DP) basierendes Berechnungsschema vorgestellt, welches (1) die Einträge der DP-Matrizen wieder verwendet und (2) die Alignmentberechnung für Teilworte, welche keinen Treffer erzeugen können, vermeidet. Dieses neue Verfahren verwendet ein aus der zu durchsuchenden Sequenzdatenbank generiertes Suffix-Arrays und erzielt eine Laufzeit, welche sublinear mit der Größe der zu durchsuchenden Sequenzen skaliert. Des Weiteren enthalten alle vorgestellten Algorithmen unseren neuen Ansatz zum Verketten von Mustertreffern. Laufzeitexperimente zeigen, dass unser bestes indexbasiertes Verfahren um zwei bis drei Größenordnungen schneller ist als bisherige Methoden.