Algorithms and Tools for Genome Assembly and Metagenome Analysis

Abstract

Um einen umfassenden Einblick in die genetische Vielfalt und molekular-biologische Funktionalität eines Organismus zu bekommen, ist die Sequenzierung dessen Genoms unabdingbar. Allerdings erlaubt keine der gegenwärtigen Sequenziertechnologien, das gesamte Genom in einem einzigen Schritt „abzulesen“. Stattdessen wird eine große Menge an kurzen Fragmenten (Reads) produziert, die um ein Vielfaches kürzer sind als das ursprüngliche Genom. Um letztendlich die vollständige Genomsequenz zu erhalten, werden die Reads mittels Algorithmen der Genomassemblierung möglichst optimal miteinander verknüpft. Die maschinelle Automatisierung der DNA-Sequenzierung basierte lange Zeit ausschließlich auf einer Methode, die in den siebziger Jahren von Frederick Sanger entwickelt wurde. Seit dem Jahr 2005 jedoch kommt eine neue Generation von Sequenziertechnologien auf den Markt, die es nun ermöglichen, in kürzerer Zeit eine große Menge Sequenzierdaten bei reduzierten Kosten zu produzieren. In dieser Arbeit werden verschiedene Methoden und deren Implementierungen vorgestellt, die solche Sequenzdaten verarbeiten und für die biologische Interpretation aufarbeiten. Obwohl die neuen Sequenziertechnologien vielfältige Optimierungen versprechen, bleibt die Genomassemblierung eine ernstzunehmende Herausforderung für Bioinformatiker und Biologen. Eines der hier vorgestellten Programme ist OSLay. Es berechnet unter Einbeziehung eines verwandten Referenzgenoms sogenannte Scaffolds. Diese Scaffolds, eine definierte Menge von geordneten assemblierten DNA-Fragmenten, sind später hilfreich für die korrekte Zusammensetzung und somit auch für die abschließende Fertigstellung der Genomsequenz. Der Einsatz von Hochdurchsatz-Technologien fördert die Erschließung und den Ausbau neuer molekular-biologischer Forschungsfelder. So profitiert zum Beispiel der junge Forschungszweig der Metagenomik stark von diesen neuen Entwicklungen. Dessen Schwerpunkt ist die genomischen Analyse von nicht-kultivierbaren mikrobiellen Organismen, die in diversen Habitaten (Biotopen) gefunden werden. In dieser Arbeit werden Methoden vorgestellt, die einerseits die Häufigkeitsverteilungen von Spezies visualisieren und die andererseits die Analyse mikrobieller Eigenschaften innerhalb eines Metagenoms ermöglichen. Hauptaugenmerk liegt jedoch auf einer neuartigen Methode, die, basierend auf einer Homologiesuche, Reads mit Hilfe der Gene Ontology funktionell klassifiziert. Die intuitive Graphvisualisierung von GOAnalyzer ist Teil der MEGAN Software und erlaubt die effiziente Analyse von einem, sowie den Vergleich der gefundenen Genprodukte von mehreren metagenomischen Datensätzen. Die sich rasant entwickelnden Sequenziertechnologien erfordern innovative Softwarelösungen, die die Hochdurchsatz-Daten nicht nur verarbeiten, sondern auch helfen, sie nutzbar machen. Um das Testen und Bewerten von Software zu erleichtern, wurde MetaSim, ein Simulationsprogramm für DNA-Sequenzen, entwickelt. Basierend auf einer Datenbank bekannter Genomsequenzen generiert MetaSim simulierte Readsequenzen, die parametrisierbaren Fehlermodellen unterliegen, welche die Fehlerraten und -typen bekannter Sequenziertechnologien widerspiegeln. Zusätzlich können Spezieshäufigkeiten festgelegt werden, um ganze Metagenome zu modellieren. In dieser Arbeit werden neben OSLay, GOAnalyzer und MetaSim weitere Methoden und Erkenntnisse vorgestellt, die die Auswertung und Interpretation von genomischen und metagenomischen Datensätzen unterstützen.

The sequencing of the genome is the first step to gain profound insights into the genetic diversity and the molecular-biological functions of an organism. The existing approaches to sequence DNA do not allow to „read“ a whole genome sequence at once in a single step. Instead, many short fragments (reads) are produced that are actually orders of magnitude shorter than the original genome. To finally obtain the complete genome sequence, genome assemblers try to piece the reads back together. For a long time, the automatized and machine-based sequencing of DNA was dominated by an approach originally conceived by Frederick Sanger in the 1970s. Since 2005, several new (next-generation'') sequencing technologies appeared on the market that are able to generate much more sequencing data in shorter time and at lower costs compared to the Sanger sequencing. This thesis introduces several computational methods that process and structure this sequencing data to assist in their biological analysis and interpretation. Despite the improvements of the new sequencing technologies, genome assembly still poses serious challenges for (computational) biologists to obtain a finished genome sequence. In this work, a software (OSLay) is described that computes so-called scaffolds by ordering and sorting large fragments (contigs) of an unfinished genome assembly with regard to a related reference genome. The computed ordering of fragments later facilitates the successful completion of the final genome sequence. The application of high-throughput technologies accelerates biological research and enables new sorts of large-scale genome investigations. One emerging research discipline that strongly benefits from these advancements is metagenomics. It is the study of uncultured microbial organisms directly derived from their natural environment. In this work, methods are presented to facilitate the visualization of species abundances and to enable the analysis of microbial properties of a metagenomic sample. Furthermore, a major focus is given to a novel homology-based approach for the functional annotation of metagenomic reads based on the Gene Ontology. Incorporated into the MEGAN software and provided with an intuitive graph visualization, the GOAnalyzer can be used to efficiently explore and compare the gene products of one or more metagenomic data sets. The fast-evolving sequencing technologies demand for innovative software concepts that are able to efficiently deal with high-throughput data. To support the testing and benchmarking of computational methods, a sequencing simulator software is introduced.Based on known genome sequences, MetaSim simulates sequencing reads that may serve as verifiable test data sets for any type of read processing software. The synthetic reads are generated according to adaptable error models reflecting the typical error characteristics of various sequencing technologies. Additionally, species abundance profiles can be determined to model realistic metagenome data sets. Beside the introduction of OSLay, GOAnalyzer and MetaSim, additional methods and findings are presented in this thesis that support the analysis and interpretation of genomic and metagenomic data sets.