Indices and Applications in High-Throughput Sequencing

Abstract

Recent advances in sequencing technology allow to produce billions of base pairs per day in the form of reads of length 100 bp an longer and current developments promise the personal $1,000 genome in a couple of years. The analysis of these unprecedented amounts of data demands for efficient data structures and algorithms. One such data structures is the substring index, that represents all substrings or substrings up to a certain length contained in a given text. In this thesis we propose 3 substring indices, which we extend to be applicable to millions of sequences. We devise internal and external memory construction algorithms and a uniform framework for accessing the generalized suffix tree. Additionally we propose different index-based applications, e.g. exact and approximate pattern matching and different repeat search algorithms. Second, we present the read mapping tool RazerS, which aligns millions of single or paired-end reads of arbitrary lengths to their potential genomic origin using either Hamming or edit distance. Our tool can work either lossless or with a user-defined loss rate at higher speeds. Given the loss rate, we present a novel approach that guarantees not to lose more reads than specified. This enables the user to adapt to the problem at hand and provides a seamless tradeoff between sensitivity and running time. We compare RazerS with other state-of-the-art read mappers and show that it has the highest sensitivity and a comparable performance on various real-world datasets. At last, we propose a general approach for frequency based string mining, which has many applications, e.g. in contrast data mining. Our contribution is a novel and lightweight algorithm that is faster and uses less memory than the best available algorithms. We show its applicability for mining multiple databases with a variety of frequency constraints. As such, we use the notion of entropy from information theory to generalize the emerging substring mining problem to multiple databases. To demonstrate the improvement of our algorithm we compared to recent approaches on real-world experiments of various string domains, e.g. natural language, DNA, or protein sequences.

In den letzen Jahren konnte der Sequenzierdurchsatz mit Einführung sogenannter Hochdurchsatz-Sequenziertechnologien dramatisch gesteigert werden. Sie erzeugen mehrere Milliarden Basenpaare pro Tag in Form von Reads der Länge 100 bp und mehr und aktuelle Entwicklungen versprechen das persönliche 1000 -Dollar-Genom in den kommenden Jahren. Diese technologischen Fortschritte erfordern neue Ansätze und effiziente Datenstrukturen, die speziell für die Analyse von Massendaten konzipiert sind. Eine solche Datenstruktur ist der Substring-Index, welcher alle Substrings oder Substrings bis zu einer festen Länge repräsentiert, die in einem Text vorkommen. In dieser Arbeit präsentieren wir 3 Substring-Indizes, die für die Indizierung von Millionen Sequenzen erweitert werden. Wir entwickeln Primär- und Sekundärspeicher- Algorithmen für deren Aufbau und eine einheitliche Schnittstelle zum Zugriff auf den generalisierten Suffixbaum. Zusätzlich stellen wir verschiedene indexbasierte Anwendungen, bspw. exakte und approximative Stringsuche und verschiedene Algorithmen zur Suche von Rep Stringsuche eats vor. Als Zweites stellen wir RazerS vor — ein Programm, das einfache oder gepaarte Reads beliebiger Länge an ihren potentiellen genomischen Ursprung aligniert. RazerS kann entweder vollsensitiv oder mit einer spezifizierten Verlustrate und höherer Geschwindigkeit verwendet werden. Wir stellen einen neuen Ansatz vor, mit dem eine geforderte Mindestsensitivität garantiert werden kann. So wird dem Benutzer ein nahtloser Trade-off zwischen Sensitivität und Laufzeit ermöglicht. Wir vergleichen RazerS mit aktuellen Read-Alignment Programmen und zeigen auf verschiedenen Realdatensätzen, dass es die höchste Sensitivität bei vergleichbarer Geschwindigkeit erzielt. Zuletzt stellen wir einen generischen Ansatz für das frequenzbasierte String Mining vor mit Anwendungen bspw. im kontrastiven Data Mining. Unser Beitrag ist ein neuer Algorithmus, der einen dynamisch aufgebauten Suffixbaum verwendet und schneller und speichersparender ist als die besten verfügbaren Algorithmen. Wir zeigen die Anwendbarkeit für das String Mining mehrerer Datenbanken an Hand einer Reihe von Suchproblemen. Als ein solches führen wir das entropiebasierte String Mining Problem als Verallgemeinerung des Emerging String Mining Problems ein. Wir bewerten unseren Algorithmus auf verschiedenen Datenbasen, bspw. natürlichsprachlichen Texten, DNA- und Proteinsequenzen. Die Experimente demonstrieren die Verbesserung unseres Algorithmus gegenüber existierenden Ansätzen.