Mikroorganismen, typischerweise in Form von großen Gemeinschaften aus einer Vielzahl von Spezies, sind ein allgegenwärtiger Bestandteil unserer Umwelt. Solche Gemeinschaften sind ein wesentlicher Bestandteil ihrer Umgebung und beeinflussen diese auf verschiedenen Ebenen. Besonders Wirt-assoziierte Mikroben werden wegen ihres Einflusses auf die menschliche Gesundheit intensiv untersucht. Darüber hinaus entwickelt sich ein wachsendes Interesse an mikrobiellen Gemeinschaften wegen ihrer Rolle in der Landwirtschaft, Abfalltechnik, im Bergbau und in der Biotechnologie. Metagenomik ist ein vergleichsweise neues wissenschaftliches Feld, welches mikrobielle Gemeinschaften auf der Basis von genetischem Material aus einer definierten Umgebung untersucht. Technische Fortschritte bei der DNA Sequenzierung haben es möglich gemacht, auf diese Weise taxonomisches Profiling durchzuführen, d.h. die mikrobiellen Spezies qualitativ und quantitativ zu erfassen.
Bei der ``whole genome shotgun sequencing (WGS)'' Methode wird die DNA aus der Probe direkt fragmentiert und sequenziert. Taxonomische Profiling-Methoden, welche auf diesem Verfahren beruhen, sind weniger anfällig für PCR Biase im Vergleich zu anderen Methoden, wie z.B. 16S-rDNA basierten Verfahren. Allerdings stellt hierbei die enorme Größe und Redundanz der Datenbanken sowie der hohe Grad an Homologie unter den in den Datenbanken erfassten Organismen einen Nachteil dar. In dieser Arbeit stellen wir zwei rechnergestützte Verfahren vor, die beide Probleme adressieren.
Die erste Methode ist ein taxonomischer Profiler, mit dem Ziel, die Mehrfachzuweisungen von Reads zu Referenzsequenzen homologer Spezies auf der Basis der unterschiedlichen Abdeckungsprofile zu korrigieren. Durch die sorgfältige Auswertung der Read-Abdeckungen werden hierbei falsch positive Referenzgenome von der Auswahl entfernt. Durch diese Filterstrategie erhöht sich die Genauigkeit und Auflösung des Verfahrens, da ein größerer Teil der Reads eindeutig einem Genom zugeordnet werden kann. Wir zeigen darüberhinaus, dass durch die Methode auch die Häufigkeiten der Organismen präziser bestimmt werden können.
Die zweite Methode ist ein verteilter Read-Mapper, welcher das Problem der großen und sich häufig ändernden Referenzdatenbanken in der Metagenomik dadurch adressiert, dass die Referenzdatenbanken systematisch in Partitionen unterteilt werden. Hierdurch kann der Bedarf an Rechenzeit und Speicher für die Berechnung von Indizes um Größenordnungen verringert und Index Aktualisierungen in wenigen Minuten anstelle von Tagen durchgeführt werden. Um trotz der hohen Zahl von kleinen Indizes eine hohe Performanz beim alignieren der Reads zu erreichen, haben wir eine neue, schnelle und kompakte Filter-Datenstruktur entwickelt, den interleaved bloom filter. Dadurch sind wir in der Lage, die beschriebenen Verbesserungen beim Erzeugen und Aktualisieren der Indizes ohne Einbußen bei der Mapping-Geschwindigkeit zu erreichen.
Microorganisms, typically occurring as large, species diverse communities, are a ubiquitous part of nature. These communities are a vital part of their environment, influencing it through various layers of interaction. Host-associated microbial communities are particularly scrutinized for their influence on the host’s health. Additionally, there is a growing interest in microbial communities due to their role in livestock, agriculture, waste treatment, mining, and biotechnology. Metagenomics is a relatively young scientific field that aims to study such microbial communities based on genetic material recovered directly from an environment. Advances in DNA sequencing have enabled us to perform taxonomic profiling, i.e. to identify microbial species quantitatively and qualitatively at increasing depth.
In whole genome shotgun sequencing (WGS), environmental DNA is taken directly from an environment and sequenced after being fragmented, without PCR amplification. Taxonomic profiling methods based on such sequencing data introduce less PCR bias compared to their amplicon based counterparts such as 16S-rDNA based profiling methods. However, the challenges posed by the enormous and redundancy of databases and the high degree homology among reference genomes of microorganisms put WGS methods at a disadvantage. In this thesis, we will present and discuss two separate computational methods that address both challenges.
The first method is a taxonomic profiler that leverages coverage landscapes created by mapping sequencing reads across reference genomes to address the challenge posed by homologous regions of genomes. By carefully evaluating the coverage profile of reference genomes we drop spurious references from consideration. This filtration strategy results in more uniquely mapping reads to the remaining reference genomes improving both the resolution and accuracy of the taxonomic profiling process. We have also shown that this method improves the quality of relative abundances assigned to each detected member organism.
The second method is a distributed read mapper which addresses the issue of large and frequently changing databases by systematically partitioning it into smaller bins. It significantly reduces the time, and computational resources required to build indices from such large databases by orders of magnitudes and updates can be performed very quickly in a few minutes compared to days in earlier methods. To achieve a competitive mapping speed while maintaining many small indices, we implemented a novel, fast and lightweight filtering data structure called interleaved bloom filter. With that, we are able to achieve the described improvements in the index building and updating time without compromising the read-mapping speed.
