LOCAS - a Low Coverage Assembler for Next Generation Sequencing and Resequencing Data

Abstract

Within the last five years, a new generation of sequencing technologies has dramatically reduced cost and at the same time increased throughput of genome sequencing. For most application fields these technologies have proven to be good alternatives to the traditional Sanger sequencing although they generate shorter read sequences. For the study of sequence variations like SNPs, indels and longer variant regions between highly related genomes, resequencing has become increasingly popular. Such analyses help to reveal the impact of sequence variations on responses to the environment and in developing diseases. They are, thus, of great interest to disease control, personal genomics and phylogenetic studies. Currently, the most popular approach to resequencing large and complex genomes is the mapping-consensus approach. It maps the read sequences to a highly related reference genome and from the alignment calculates a consensus sequence which can be compared to the reference genome. Unfortunately, only SNPs and small indels can be detected with this approach. A more promising approach is homology-guided assembly. Here, the reads are mapped against a reference sequence and the layout of the reads is refined before the calculation of the consensus sequence. This method has the capability to additionally reveal the sequences of longer variant regions such as long insertions. In this thesis, I present an extension to homology-guided assembly that aims at assembling not only regions that are homologous between the target and reference genome but also longer variant regions. After the reads have been mapped to the reference sequence, the reference sequence is partitioned into regions of a fixed length, called blocks. In a reassembly step, the reads of each pair of consecutive blocks are assembled together. In order to also find long variant regions, reads that cannot be mapped onto the reference genome, so called left-over reads, are recruited and incorporated in the assembly of the current blocks. The main focus of this work was on the development of assembly algorithms for current resequencing projects. To meet the needs of these projects the developed algorithms were especially designed for short read data at low sequencing depth. Furthermore, this work comprises extensions to these assembly algorithms, which are used in the reassembly step of our homology-guided assembly approach. These algorithms additionally incorporate left-over reads in the assembly and can utilize mapping positions that are available for the reads. The assembly algorithms are implemented in the assembly tool LOCAS (Low Coverage ASsembly) and its extension SUPERLOCAS. The developed tools were evaluated and compared to state-of-the-art assemblers on short read data within a homology-guided assembly approach. For this purpose, resequencing scenarios with a low sequencing depth were simulated. In the first study, which simulated assemblies of blocks, LOCAS showed better or comparable results regarding error rate and contig size while producing contigs with the best trade-off between both measures. In the second study, which simulated assemblies of blocks with the incorporation of left-over reads, SUPERLOCAS proved to be the superior tool regarding contig size, error rate and runtime while assembling the same amount of long insertion regions as comparable assemblers. In a third study, which used real world data, LOCAS and SUPERLOCAS performed similar as in the simulated studies. In all studies both tools proved to be very robust to different parameter settings. In conclusion, my homology-guided assembly approach overcomes the problems of the mapping-consensus approach. In addition to homologous regions, it also assembles longer variant regions. Compared to other assembly methods, LOCAS and SUPERLOCAS are well suited for reassembly and show superior performances in this scenario.

Eine neue Generation von Sequenziertechnologien hat in den letzten fünf Jahren die Kosten für die Genomsequenzierung deutlich verringert und gleichzeitig den Sequenzierdurchsatz erhöht. Die neuen Sequenziertechnologien haben sich in vielen Anwendungsgebieten als vielversprechende Alternative zur traditionellen Sangersequenzierung erwiesen, obwohl die erzeugten Sequenzfragmente, welche als Reads bezeichnet werden, deutlich kürzer sind. Zur Untersuchung von Punkttmutationen (SNPs), kleinen Insertionen und Deletionen (Indels) sowie längeren variablen Bereichen von nahverwandten Genomen wird inzwischen immer häufiger das Verfahren der Resequenzierung eingesetzt. Mit diesem Analyseverfahren kann die Bedeutung von Sequenzvariationen bei Krankheiten festgestellt werden und ist daher von großem Interesse bei der Kontrolle von Krankheiten und im Bereich Personal-Genomics. Momentan wird bei der Resequenzierung von langen und komplexen Genomen vor allem der Mapping-Consensus Ansatz verwendet. Dabei werden die Reads gegen ein nahverwandtes Referenzgenom aligniert und die Consensus-Sequenz der alignierten Reads berechnet, sodass diese mit der Referenzsequenz verglichen werden kann. Da die Reads meist nur diskontinuierlich aligniert werden können, besteht die Consensus-Sequenz meist aus mehreren Teilsequenzen, welche als Contigs bezeichnet werden. Der Nachteil bei diesem Ansatz ist, dass meist nur SNPs und Indels bestimmt werden können, während lange variable Bereiche unentdeckt bleiben. Ein Ansatz, der hierfür weitaus erfolgversprechender ist, ist das Homology-Guided Assembly. Hier werden die Reads ebenfalls gegen eine Referenzsequenz aligniert. Jedoch wird die Anordnung der Reads anschließend noch einmal verbessert, bevor schließlich die Consensus-Sequenz berechnet wird. Dieser Ansatz hat das Potenzial auch die Sequenz von längeren variable Bereichen zu bestimmen. In meiner Dissertation stelle ich einen erweiterten Ansatz des Homology-Guided Assemblies vor. Durch diesen neuen Ansatz werden nicht nur homologe Bereiche des Referenz- und Zielgenoms assembliert sondern auch lange variable Bereiche. Nachdem die Reads gegen die Referenzsequenz aligniert worden sind, wird die Referenzsequenz in Abschnitte unterteilt, welche als Blocks bezeichnet werden. Diese Blocks werden anschließend reassembliert, d.h., alle Reads die zu zwei aufeinanderfolgenden Blocks zugeordnet sind werden miteinander assembliert. Dabei werden Reads, die nicht gegen das Referenzgenom aligniert werden konnten (Left-Over Reads), in das Assembly eingebaut, sodass auch lange variable Bereiche assembliert werden können. Der Hauptaugenmerk meiner Arbeit lag auf der Entwicklung von Assemblierungsalgorithmen, die in Resequenzierungsprojekten mit neueren Sequenziertechnologien angewendet werden können. Um den Anforderungen dieser Projekte Rechnung zu tragen, wurden die Algorithmen speziell an eine kurze Länge der Reads und an eine niedrige Sequenziertiefe angepasst. Darüber hinaus wurden die Algorithmen so erweitert, dass sie auch zur Reassemblierung genutzt werden können. Durch diese Erweiterung werden auf eine effiziente Weise auch Left-Over Reads mit in das Assembly einbezogen. Weiterhin können vorhandene Positionen der Reads bezüglich der Referenzsequenz genutzt werden. Die Algorithmen wurden in das Assemblierungsprogramm LOCAS bzw. in dessen Erweiterung SUPERLOCAS implementiert. Die entwickelte Software wurde in einer Vergleichsstudie evaluiert und mit anderen aktuellen Assemblern verglichen. Die Assembler wurden zur Reassemblierung innerhalb des beschriebenen Homology-Guided Assembly Ansatzes verwendet. Zu diesem Zweck wurden kurze Reads mit einer niedrigen Sequenziertiefe innerhalb von Resequenzierungsszenarien simuliert. In der ersten Studie, welche die Reassemblierung von Blocks simulierte, erzielte LOCAS bessere oder vergleichbare Ergebnisse bezüglich der Fehlerrate und der Contig-Länge. Gleichzeitig erreichte es den besten Kompromiss zwischen beiden Maßen. In der zweiten Studie, welche die Reassemblierung von Blocks unter Einbeziehung von Left-Over Reads simulierte, stellte sich SUPERLOCAS als der beste Assembler bezüglich der Contig-Länge, der Fehlerrate und der Laufzeit heraus. In einer dritten Studie, die auf realen Daten basierte, zeigten LOCAS und SUPERLOCAS die gleiche Leistung wie in den Simulationsstudien. In allen Studien waren beide Assembler sehr robust gegenüber unterschiedlichen Parametereinstellungen. Aus den Ergebnissen dieser Arbeit lässt sich folgern, dass die angesprochenen Probleme des Mapping-Consensus Ansatzes durch den vorgestellten Homology-Guided Assembly Ansatz in weiten Punkten gelöst werden. Zusätzlich zu den homologen Bereichen werden nun auch längere variable Bereiche assembliert. LOCAS und SUPERLOCAS erwiesen sich für die Reassemblierung von Genomen innerhalb des Homology-Guided Assembly-Ansatzes als sehr geeignete Assembler, da sie ausgezeichnete Ergebnisse für dieses Szenario erzielten.