New Approaches to Long-Read Assembly under High Error Rates

Das Gebiet der Genomassemblierung beschäftigt sich mit der Entwicklung von Algorithmen, die Genome am Computer anhand von Sequenzierungsdaten rekonstruieren. Es geriet erstmals in den Neunzigern mit dem Human Genome Project in den Fokus der Öffentlichkeit. Da nur kurze Abschnitte des menschlichen Genoms ausgelesen werden konnten, musste die Rekonstruktion längerer Genomsequenzen aus den ausgelesenen Abschnitten im Nachhinein am Computer erfolgen. Auch fast 20 Jahre nach der Veröffentlichung der menschlichen Genomsequenzen stellt die Genomeassemblierung nach wie vor noch einen essentiellen Verarbeitungsschritt für Sequenzierungsdaten dar. ... mehrNur Datendurchsatz, Länge und Fehlerprofil der ausgelesenen Genomabschnitte haben sich verändert und damit einhergehend auch die algorithmischen Anforderungen.
Damit komplementiert das Forschungsgebiet der Genomeassemblierung die Sequenzierungstechnologien, die sich mit enormer Geschwindigkeit weiter entwickelt haben. Zusammen erlauben sie die Entschlüsselung der Genome einer stark zunehmenden Anzahl von Lebewesen und bilden damit die Grundlage für einen Großteil der Forschung in verschiedensten Bereichen der Biologie und Medizin.
Trotz der beeindruckenden technologischen und algorithmischen Entwicklungen der vergangenen Jahrzehnte ist es bisher nur für bakterielle Genome gelungen, die komplette Genomsequenz zu rekontruieren. Bei der Assemblierung der wesentlich größeren eukaryotischen Genome bestehen mehrere ungelöste algorithmische Probleme. Diese Probleme hängen mit verschiedenen repetitiven Strukturen zusammen, die in fast allen Genomen höherer Lebewesen vorkommen. Deshalb werden eukaryotische Genome immer in wesentlich mehr unzusammenhängenden Sequenzen veröffentlicht als die jeweiligen Lebewesen Chromosomen haben.
Die repetitiven Strukturen, die für die Lücken in den Genomsequenzen verantwortlich sind, lassen sich grob in drei Klassen unterteilen. Mikrosatelliten und Minisatelliten sind sehr kurze Sequenzen, die sich tausende oder zehntausende Male direkt aufeinander folgend wiederholen können. Dieses Muster ist typisch für sogenannte Centromere und Telomere, die sich in der Mitte und an den Enden vieler Chromosome befinden. Sogenannte Interspersed Repeats, oft auch als Transposons bezeichnet, sind längere Sequenzen, die häufig in fast identischer Form an unterschiedlichen Stellen im Genome vorkommen. Sogenannte Tandem Repeats dagegen sind längere Sequenzen, die direkt aufeinanderfolgend mehrere Male in einem Genom auftreten können. Oft sind Tandem Repeats Genkomplexe, das heißt Ansammlungen fast identischer proteinkodierender Abschnitte, die es der Zelle erlauben, die kodierten Proteine besonders schnell zu produzieren.
Jede dieser repetitive Strukturen stellt spezifische Anforderung an Assemblierungsalgorithmen. In dieser Doktorarbeit leisten wir mehrere Beiträge zur Lösung der letzteren zwei vorgestellten Probleme, der Assemblierung von Interspersed Repeats und Tandem Repeats.
In Teil 1 der Arbeit stellen wir mehrere Datenverarbeitungsprozeduren vor, die Sequenzierungsdaten aufbereiten, um die seltenen Unterschiede zwischen mehrfach auftretenden Genomsequenzen zu identifizieren. Diese beinhalten Softwareprogramme zur Berechnung und Optimierung von Multiplen Sequenz Alignments (MSA) anhand dynamischer Programmierung und zur statistischen Modellierung und Analyse der Unterschiede, wie das MSA sie präsentiert.
In Teil 2 bauen wir auf dieser Analyse auf und präsentieren ein Softwareprogramm zur Assemblierung von Interspersed Repeats. Dieses Programm baut auf mehreren algorithmischen Neuerungen auf und ist in der Lage, Transposonfamilien mit sehr langen Sequenzen und sehr vielen verschiedenen Kopien effektiv zu assemblieren. Es ist das erste Programm dieser Art, welches in der Lage ist, Transposonfamilien mit dutzenden von Kopien zu assemblieren. Es gelingt uns zu zeigen, dass es auch für kleinere Transposonfamilien akkurater und schneller ist als das bisher einzige Konkurrenzprogramm, welches auf dieses Assemblierungsproblem spezialisiert ist.
In Teil 3 beschreiben wir eine Analysepipeline, die es uns ermöglicht, Genkomplexe aus dutzenden von Tandem Repeats zu assemblieren. Diese Pipeline enthält Clustering und Graph Drawing Algorithmen. Ihr Herzstück ist ein Fehlerkorrekturalgorithmus, der auf Neuronalen Netzwerken basiert. Wir demonstrieren den praktischen Nutzen dieser Pipeline durch die Assemblierung des Drosophila Histone Komplexes.
Im Abschluss diskutieren wir die Möglichkeit, Mikro- und Minisatelliten zu assemblieren und schlagen Forschungsansätze für weitere Verbesserungen im Bereich der Interspersed Repeat- und Genkomplexassemblierung vor.

The research area of Genome Assembly engages in the development of algorithms for the computational reconstruction of genomes. It was subject of considerable media attention during the Human Genome Project in the 1990s and early 2000. Because only short sections of the genome could be deciphered in one go, longer sections of the genome had to be reconstructed on the computer in a post-processing step. Although it has almost been 20 years since the Human Genome Project published the sequence of the human genome, Genome Assembly still constitutes an essential step for analysing sequencing data. ... mehrOnly throughput, length, and error profile of the reads provided by sequencing machines have changed considerably, and with them the algorithmic requirements.
Genome Assembly is complementary to the rapidly developing sequencing technologies. Together, they allow for deciphering a steadily increasing number of genomes and provide the foundation for a substantial part of the research in different areas of biology and medicine.
Despite the extraordinary technological and algorithmic development over recent decades, so far only bacterial genomes have been fully assembled. There are several unresolved problems in the assembly of the substantially larger eukaryotic genomes. These problems are due to different repeat structures, which occur in almost all genomes of higher organisms. The draft genomes of eukaryotic genomes are currently published in many more disparate parts than the respective animal or plant has chromosomes.
The repeat structures that are responsible for the preponderance of these gaps in chromosomes can be roughly divided into three classes.
Micro- and Minisatellites are very short sequences that repeat directly adjacent to each other for thousands or tens of thousands of times. This pattern is typical for centromeric or telomeric regions in the middle and at the end of many chromosomes. Interspersed repeats, also denoted as transposable elements, are longer sequences that occur in almost identical form many times in different regions of the genome. Tandem repeats are longer sequences that occur numerous times directly adjacent to each other. Often, tandem repeats form part of so called gene complexes, that means, collections of repeated protein coding sequences that allow for the rapid production of the encoded protein in the cell.
Each of these repetitive structures poses unique assembly challenges. In this thesis, we contribute several ideas for improving the assembly of interspersed repeats as well as gene complexes.
In part 1 of this thesis, we present several data processing procedures that allow for the detection and extraction of rare differences between different copies of a repeat sequence. These are implemented in tools for computing and optimising multiple sequence alignments (MSA) utilising dynamic programming, as well as a tool for the statistical modelling and analysis of repeat differences as they can be extracted from the MSA.
In part 2, we build on these pre-processing procedures and present a software program for the assembly of interspersed repeats. This program is based on several novel algorithmic ideas and is capable of assembling transposon families with long sequences and a high number of copies. It is the first such program that can handle transposon families with dozens of copies. We show that our method is superior in speed and accuracy to the only existing competing repeat resolution tool.
In part 3, we describe an analysis pipeline for the assembly of gene complexes, consisting of dozens of tandem repeats. This pipeline contains clustering and graph drawing algorithms. Its core is a de-noising algorithm that is based on neural networks. We demonstrate the practical utility of this pipeline by assembling the Drosophila Histone Complex, a long standing gap in the genome of this important model organism.