Sequence to graph alignment : theory, practice and applications

Abstract

All species, including humans, have genetic variation between individuals. Traditionally the reference genome used for humans is one sequence that represents a mosaic of individual genomes. Recently, pangenomic approaches that take into consideration genetic diversity have become more common. One representation of pangenomes is the sequence graph or the pangenome graph, which uses a graph format to represent genetic diversity. Graphs also have other uses in bioinformatics, for example de Bruijn graphs and string graphs used for genome assembly. Due to the growing importance of sequence graphs, methods for handling graph-based data structures are becoming more important. In this work I examine the generalization of sequence alignment to graphs. First, I present a theoretical basis for quick bit-parallel sequence-to-graph alignment. The bit-parallel method outperforms previous algorithms by a factor of 3-21x in runtime depending on graph topology. The bit-parallel method enables provably optimal sequence-to-graph alignment to scale to bacterial genomes. Next I present GraphAligner, a practical tool for aligning sequences to graphs. GraphAligner generalizes banded alignment to graphs. Previous sequence-to-graph alignment tools could not align long reads to human sized de Bruijn graphs. GraphAligner enables sequence-to-graph alignment to scale to mammalian sized genomes. GraphAligner is as accurate as linear aligners when aligning to linear genomes. When aligning to graphs, GraphAligner is more accurate and an order of magnitude faster than previous graph alignment tools. To show the utility of GraphAligner, I present a long read genotyping pipeline, and an error correction pipeline that outperforms existing tools by a factor of two in correction accuracy and an order of magnitude in runtime. I also show two applications where GraphAligner is an essential part. First, AERON is a tool for quantifying RNA expression and detecting gene fusion events with long reads. AERON recovered known fusion events in the K562 cancer cell line. Second, I present a hybrid graph-based genome assembly pipeline. The genome assembly pipeline uses novel methods to combine short read and long read technologies

Jede Spezies, einschließlich des Menschen, weist genetische Variation zwischen den Individuen auf. Das Referenzgenom, das traditionell für Menschen verwendet wird, ist eine Sequenz, die ein Mosaik aus individuellen Genomen darstellt. In letzter Zeit werden pangenomische Ansätze, die die genetische Diversität berücksichtigen, immer häufiger verwendet. Der Sequenzgraph oder Pangenomgraph ist eine Methode zur Darstellung des Pangenoms, die ein Graph-Format verwendet, um genetische Vielfalt darzustellen. Graphen finden auch andere Anwendungen in der Bioinformatik, beispielsweise De Bruijn-Graphen und Stringgraphen, die für Genomassemblierung verwendet werden. Durch die wachsende Bedeutung von Sequenzgraphen werden auch Methoden für graphenbasierte Datenstrukturen immer wichtiger. In dieser Arbeit untersuche ich die Verallgemeinerung von Sequenzalignement zu Graphen. Zuerst stelle ich die theoretischen Grundlagen für schnelles bitparalleles Sequenz-zu-GraphAlignement vor. Die Laufzeit der bitparallelen Methode unterbietet frühere Algorithmen um einen Faktor von 3 bis 21, abhängig von der Topologie des Graphen. Darüber hinaus liefert die bitparallele Methode beweisbar optimale Ergebnisse und erreicht praxisgerechte Laufzeiten bis hin zu Eingaben der Größe eines bakteriellen Genoms, was mit existierenden Algorithmen nicht zu erreichen ist. Danach stelle ich GraphAligner, ein praktisches Programm zur Alignement von Sequenzen an Graphen, vor. GraphAligner enthält außerdem theoretische Entdeckungen durch die Verallgemeinerung von gebändertem Alignement zu Graphen. Frühere Programme für Sequenz-zu-GraphAlignement waren nicht in der Lage, lange Sequenzierungsfragmente an Graphen in der Größe menschlicher Genome zu alignieren. GraphAligner ermöglicht Sequenz-zu-Graph-Alignement bis zu einer Größe von Säugetiergenomen. GraphAligner ist beim Alignement an lineare Genome ebenso präzise wie herkömmliche lineare Alignier-Programme. Beim Alignement an Graphen ist GraphAligner präziser und um eine Größenordnung schneller als bisherige Programme. Um die Nützlichkeit von GraphAligner zu zeigen, stelle ich eine Genotypisierungspipeline sowie eine Fehlerkorrekturpipeline vor, die bisherige Programme um einen Faktor von 2 in der Korrekturgenauigkeit und um eine Größenordnung in der Laufzeit übertrifft. Weiterhin zeige ich zwei Anwendungen, in denen GraphAligner eine essenzielle Rolle spielt. Bei der ersten handelt es sich um AERON, ein Programm zur Quantifizierung von RNA-Expression und zur Erkennung von Genfusionsereignissen mittels langer Sequenzierungsfragmente. AERON konnte bekannte Genfusionsereignisse in der K562 Krebszelllinie aufdecken. Als zweites stelle ich eine graphenbasierte Methode zur Genomassemblierung vor. Die Genomassemblierungspipeline verwendet neuartige Methoden, um kurze und lange DNA-Sequenzierungstechnologien zu kombinieren.