Approximate string matching for high-throughput sequencing

Abstract

Over the past years, high-throughput sequencing (HTS) has become an invaluable method of investigation in molecular and medical biology. HTS technologies allow to sequence cheaply and rapidly an individual’s DNA sample under the form of billions of short DNA reads. The ability to assess the content of a DNA sample at base-level resolution opens the way to a myriad of applications, including individual genotyping and assessment of large structural variations, measurement of gene expression levels and characterization of epigenetic features. Nonetheless, the quantity and quality of data produced by HTS instruments call for computationally efficient and accurate analysis methods. In this thesis, I present novel methods for the mapping of high-throughput sequencing DNA reads, based on state of the art approximate string matching algorithms and data structures. Read mapping is a fundamental step of any HTS data analysis pipeline in resequencing projects, where DNA reads are reassembled by aligning them back to a previously known reference genome. The ingenuity of approximate string matching methods is crucial to design efficient and accurate read mapping tools. In the first part of this thesis, I cover practical indexing and filtering methods for exact and approximate string matching. I present state of the art algorithms and data structures, give their pseudocode and discuss their implementation. Furthermore, I provide all implementations within SeqAn, the generic C++ template library for sequence analysis, which is freely available under http://www.seqan.de/. Subsequently, I experimentally evaluate all implemented methods, with the aim of guiding the engineering of new sequence alignment software. To the best of my knowledge, this is the first study providing a comprehensive exposition, implementation and evaluation of such methods. In the second part of this thesis, I turn to the engineering and evaluation of read mapping tools. First, I present a novel method to find all mapping locations per read within a user- defined error rate; this method is published in the peer-reviewed journal Nucleic Acids Research and packaged in a open source tool nicknamed Masai. Afterwards, I generalize this method to quickly report all co-optimal or suboptimal mapping locations per read within a user-defined error rate; this method, packaged in a tool called Yara, provides a more practical, yet sound solution to the read mapping problem. Extensive evaluations, both on simulated and real datasets, show that Yara has better speed and accuracy than de-facto standard read mapping tools.

In den letzten Jahren wurde die Hochdurchsatz-Sequenzierung (HTS) zu einem unverzichtbaren Bestandteil der molekularmedizinischen Forschung. HTS Technologien ermöglichen es DNS-Proben von Individuuen schnell und günstig in Form von Milliarden kurzer DNS-Reads zu sequenzieren. Die Fähigkeit, die Basenpaarabfolge einer DNS-Probe zu bestimmen, eröffnet viele neue Anwendungsgebiete, wie zum Beispiel die Genotypisierung, die Beurteilung von strukturellen Variationen, die Messung der Genexpressionslevel oder die Etablierung von epigenetischen Faktoren. Jedoch setzen sowohl Quantität als auch die Qualität der von HTS-Technologien produzierten Daten rechereffiziente und akkurate Analysemethoden voraus um als Standardverfahren im biomedizinischen Bereich eingesetzt werden zu können. In dieser Arbeit stelle ich neue Methoden für das sogenannte Read Mapping von HTS Daten vor. Read Mapping ist ein essentielles Verfahren, bei dem aus den Produkten einer HTS Applikation mit Hilfe eines bereits bekannten Referenzgenoms die ursprüngliche DNS-Reads assembliert wird. Die Entwicklung von speziellen und neuartigen Algorithmen für die approximative Stringsuche spielt dabei eine entscheidende Rolle, um akkurate und effiziente Read Mapping Programme zu entwicklen. Im ersten Teil dieser Arbeit beschreibe ich praktische Index-Datenstrukturen sowie Filtermethoden, die bei der approximativen Stringsuche angewendet werden. Ich stelle die Algorithmen im Pseudocode dar und bespreche deren Funktionsweise und Implementierung im Detail. Sämtliche Algorithmen und Datenstrukturen, die ich in dieser Arbeit vorstelle, wurden in SeqAn einer generischen C++ Template-Bibliothek für Sequenzanalyse implementiert und sind darüber verfügbar (siehe http://www.seqan. de/). Anschließend analysiere und vergleiche ich die vorgestellten Methoden in verschiedenen Experimenten ausführlich miteinander, mit dem Ziel neue verbesserte Alignmentalgorithmen entwerfen zu können. Nach meinem besten Wissen und Gewissen, ist dies die erste Arbeit, die die genannten Methoden umfassend in ihrer Implementierung und Funktionsweise diskutiert und bewertet. Im zweiten Teil dieser Arbeit beschreibe und diskutiere ich zwei neue Read Mapping Programme und vergleiche diese mit bisherigen Anwendungen. Dabei stelle ich zuerst eine neue Methode vor, welche alle potentiellen genomischen Urpsprungspositionen für jeden DNS- Read mit einer spezifizierten Fehleranzahl lokalisiert. Die beschriebene Methode wurde im Open Source Programm Masai implementiert und wurde in der Zeitschrift Nucleic Acids Research publiziert. Anschließend generalisiere ich die Methode und zeige wie alle co-optimalen oder suboptimalen Positionen, gegeben einer vom Nutzer definierten Fehlerrate, effizient gefunden werden können. Das Open Source Programm Yara implementiert dieses Verfahren und bietet somit eine wesentlich praktischere und noch dazu solide Lösung für das Read Mapping Problem. Eine umfassende Analyse auf simulierten und realen Daten ergab, dass Yara schneller und genauer als De-facto-Standard Read Mapping Programme ist.