Data structures and algorithms for analysis of alternative splicing with RNA- seq data

Abstract

Research in molecular biology was revolutionized by the invention of semi- automated Sanger sequencing for DNA in the early 1990’s. It was the foundation for the se- quencing of several genomes including the human genome. In the last few years a second revolution in the field of DNA sequencing has occurred that has changed the field. Next-generation sequencing (NGS) approaches suddenly enable the sequencing of millions of DNA fragments leading to short sequencing reads in less than a day. These NGS technologies are still in its infancy and their further development will herald a new era where DNA sequencing is inexpensive and easily manageable. This development has shifted the largest proportion of the workload onto the workbench of the computational biologist that has to cope with gigabases of sequence data, creating a bottleneck for scientific discovery. This thesis deals with the challenges related to the application of Next-generation sequencing (NGS) technologies to the sequencing of expressed mRNAs (RNA-Seq) and the detection of alternative exon events (AEEs), summarizing alternative splicing, alternative promoter, and alternative polyadenylation events. There are three main contributions. First, methods are introduced that enable the detection of AEEs within or between conditions, e.g. disease and normal, based on given gene annotation and mapped RNA-Seq reads. All methods are based on a Poisson model that describes the random placement of reads along a transcript. The methods are applied to a dataset from a human embryonic kidney (HEK) and a B cell line. Several thousand AEEs were predicted in these cell lines. The robustness and correctness of the predictions was assessed by simulations, bootstrapping, and RT-PCR validation experiments. In addition, a comparison of splicing prediction by RNA-Seq with prediction from exon arrays shows higher sensitivity and accuracy for RNA-Seq based predictions. Second, a new method for inferring isoform expression levels from RNA-Seq data is proposed, given annotated isoform structures and mapped read information. The method is based on the Expectation-Maximization framework. The theoretical power of the approach is demonstrated with simulations. Application to HEK and B cell RNA- Seq data and comparison to isoform expression quantification with quantitative RT-PCR experiments show the accuracy of the porposed method. Finally, the first method that allows the de novo assembly of an organism’s transcrip- tome from short read RNA-Seq data is presented, an important problem that enables functional analysis and gene discovery when the genome of an organism was not se- quenced yet. A transition from the traditional Overlap-Layout-Consensus paradigm to the Eulerian path approach to transcriptome assembly is made, similar to the de- velopment for de novo genome assembly. The similarities between de Bruijn graphs and splicing graphs are explored and a theory for de novo prediction of AEEs is developed. Further, algorithms for the assembly of full length sequences considering alternative gene isoforms are designed. An application to real data demonstrates the improvement compared to de novo genome assemblers that have been utilized so far for RNA-Seq datasets. For a mouse RNA-Seq dataset with approximately 67 Mio. reads a total output of 63 megabases of transcript sequences is assembled of which approximately 6,900 are full-length mRNAs, underlining the success of the approach with few lanes of sequencing.

Die molekulare biologische Forschung wurde durch die Erfindung der halbautoma- tisierten Sanger Sequenzierung für DNS in den frühen 1990er Jahren revolutioniert. Sie legte den Grundstein für die Sequenzierung von mehreren Genomen einschließlich des menschlichen Genoms. In den letzten Jahren hat es eine zweite Revolution im Bereich der DNS Sequenzierung gegeben. Die so genannten Next-Generation Se- quencing (NGS) Verfahren erlauben die Sequenzierung von Millionen von DNS Frag- menten, in Form von kurzen "Reads", in weniger als einem Tag. Diese NGS Tech- nologien sind noch nicht voll ausgereift und ihre weitere Entwicklung wird eine neue Ära in der DNS Sequenzierung einläuten, in der DNS Sequenzierung preiswert und einfach zu handhaben ist. Diese Entwicklung bedeutet einen entscheidenden Anstieg des Arbeitsaufwand von Bioinformatikern, die Gigabasen von Sequenzdaten bewälti- gen müssen, was derzeitig den Flaschenhals für wissenschaftliche Analysen mit NGS Daten darstellt. Diese Dissertation beschäftigt sich mit den Herausforderungen, die sich auf Applika- tionen von NGS Technologien zum Sequenzieren von exprimierten mRNAs (RNA- Seq) beziehen. Im besonderen wird die Ermittlung von alternativen Exon Ereignissen (AEEs) betrachtet, was zusammenfassend steht für alternatives Spleißen, alterna- tive Promotoren und alternative Polyadenylierungsereignisse. Im folgenden die drei wichtigsten Beiträge. Zuerst werden Methoden eingeführt, die die Vorhersage von AEEs in einer oder zwis- chen zwei Konditionen, zum Beispiel krank gegen normal, ermöglichen. Diese Metho- den basieren auf bestehender Genannotation und bereits genomisch platzierten RNA- Seq Reads. Alle Methoden basieren auf einem Poisson Modell, welches das zufällige Platzieren der Reads entlang der mRNA beschreibt. Die Methoden werden auf RNA- Seq Datensätze von einer humanen- embryonalen Niere (HEK) und einer humanen B-Zell Zelllinie angewendet. Mehrere Tausend AEEs wurden in diesen Zelllinien vorhergesagt. Die Robustheit und Genauigkeit der Vorhersagen wurde durch Sim- ulationen, Bootstrapping und RT- PCR Validierungsexperimente bestätigt. Darüber hinaus wurde ein Vergleich von den neuen Methoden für RNA-Seq und bestehenden Methoden für Exon Arrays durchgeführt, der erhöhte Sensitivität und Genauigkeit für die RNA-Seq basierten Vorhersagen offenbart. Zweitens wird eine neue Methode für die Abschätzung von mRNA Expressions Leveln aus RNA-Seq Daten vorgeschlagen, basierend auf vorhandenen Transkriptannotatio- nen und bereits genomisch platzierten RNA-Seq Reads. Die Methode basiert auf dem Expectation- Maximization Optimierungsverfahren. Die Korrektheit und theoretische Leistung des Ansatzes wird durch Simulationen demonstriert. Anwendung auf HEK und B-Zell RNA-Seq Daten und Vergleich mit Quantifizierung durch quantitative RT- PCR Experimente bestätigen die Genauigkeit der Methode. Schlussendlich wird die erste Methode vorgestellt die es erlaubt ein de novo "Assem- bly" eines Transkriptoms eines Organismuses ausgehend von RNA-Seq Daten anzufer- tigen. Dies ist ein wichtiges Problem, welches funktionale Analysen und Genentdeck- ung für Organismen ermöglicht, von denen das Genom noch nicht sequenziert wurde. Ein Wechsel vom traditionellen Overlap-Layout-Consensus Paradigma zur Anwen- dung des Eulerpfad Ansatzes für Transkriptom Assembly wird vorgeschlagen, ver- gleichbar mit der Entwicklung für de novo Genom Assembly. Die Gemeinsamkeiten zwischen de Bruijn Graphen und Splicing Graphen wurden erforscht und eine Theorie für de novo Vorhersagen von AEEs entwickelt. Ausgehend von de Bruijn Graphen wurden Algorithmen entwickelt, die die Vorhersage von kompletten mRNA Sequen- zen, unter Berücksichtigung von AEEs, ermöglichen. Die Anwendung auf reellen RNA-Seq Daten demonstriert die Verbesserung des neuen Ansatzes im Vergleich zur Anwendung von de novo Genom Assemblierungsprogrammen, die bis dato für RNA- Seq Datensätze benutzt wurden. Für einen RNA-Seq Datensatz einer Maus Zelllinie mit ungefähr 67 Mio. Reads wurde ein Assembly von insgesamt 63 Megabasen erstellt . Dieses Assembly beinhaltet ungefähr 6,900 mRNAs in vollständiger Länge, welches den Erfolg des Ansatzes untermauert.