Abstract:
Die DNS (englisch: DNA) bildet die vererbbare Grundlage allen bekannten Lebens auf dem Planeten. Entsprechend wichtig ist ihre "Entschlüsselung" für die Biologie im Allgemeinen, und für die Erforschung der evolutionären Zusammenhänge verschiedener biologischer Artern im Besonderen. In den letzten Jahrzehnten hat eine rasante technologische Entwicklung im Bereich der DNS-Sequenzierung stattgefunden, die auch auf absehbare Zeit noch nicht zum Stillstand kommen wird. Die biologische Forschung hat daher den Bedarf an computer-gestützten Methoden erkannt, sowohl in Bezug auf die Speicherung und Verarbeitung der immensen Datenmengen, die bei der Sequenzierung anfallen, als auch in Bezug auf deren Analyse und Visualisierung.
... mehr
Eine grundlegene Fragestellung ist dabei die nach dem Stammbaum des Lebens, der die evolutionäre Verwandtschaft der Arten beschreibt. Diese Wissenschaft wird Phylogenetik, und die resultierenden Strukturen phylogenetische Bäume genannt. Häufig basieren diese Bäume auf dem Vergleich von DNS-Sequenzen der Arten, mit der Idee, dass Arten mit ähnlicher DNS auch im Baum nah beieinander liegen. Die Berechnung eines solchen Baumes aus DNS-Daten kann als Optimierungsproblem formuliert werden, das durch die stetig wachsende Menge an Daten für die Informatik eine Herausforderung darstellt. Aktuell beschäftigt sich die Mikrobiologie zum Beispiel mit der Erkundung und Erforschung von Proben (Samples), die aus Meereswasser, dem Erdreich, dem menschlichen Körper, und ähnlichen Umgebungen gewonnen wurden: Welche mikrobischen Arten, Bakterien und andere Einzeller, bewohnen diese Umgebungen und Proben? Das zugehörige Forschungsfeld ist die Meta-Genetik. Einen verlässlichen Stammbaum für die aber-millionen an Sequenzen aus solchen Proben zu errechnen ist praktisch unmöglich. Eine Alternative bietet die phylogenetische Platzierung der Sequenzen auf einem gegebenen Referenz-Baum von bekannten Arten (so genanntes phylogenetisches Placement): Hierbei wird ein Stammbaum aus Referenz-Sequenzen bekannter Arten gewählt, der möglichst viel der in den Proben zu erwartenden Artenvielfalt abdeckt, und dann für jede Sequenz aus den Proben die nächste Verwandtschaft innerhalb des Baumes bestimmt. Dies resultiert in einer Zuordnung von Sequenzen auf die Positionen verwandter Arten im Referenz-Baum. Diese Zuordnung kann auch als Verteilung der Sequenzen auf dem Baum verstanden werden: In dieser Interpretation kann man beispielsweise erkennen, welche Arten (und deren Verwandtschaft) besonders häufig in den Proben vertreten sind.
Diese Arbeit beschäftigt sich mit neuen Methoden zur Vor- und Nachbereitung, Analyse, und Visualisierung rund um den Kernbereich des phylogenetischen Placements von DNS-Sequenzen. Zunächst stellen wir eine Methode vor, die einen geeigneten Referenz-Baum für die Platzierung liefern kann. Die Methode heißt PhAT (Phylogenetic Automatic (Reference) Trees), und nutzt Datenbanken bekannter DNS-Sequenzen, um geeigenete Referenz-Sequenzen für den Baum zu bestimmen. Die durch PhAT produzierten Bäume sind beispielsweise dann interessant, wenn die in den Proben zu erwartende Artenvielfalt noch nicht bekannt ist: In diesem Fall kann ein breiter Baum, der viele der bekannten Arten abdeckt, helfen, neue, unbekannte Arten zu entdecken. Im gleichen Kapitel stellen wir außerdem zwei Behilfs-Methoden vor, um den Prozess und die Berechnungen der Placements von großen Datensätzen zu beschleunigen und zu ermöglichen. Zum einen stellen wir Multilevel-Placement vor, mit dem besonders große Referenz-Bäume in kleinere, geschachtelte Bäume aufgeteilt werden können, um so schnellere und detalliertere Platzierungen vornehmen können, als auf einem einzelnen großen Baum möglich wären. Zum anderen beschreiben wir eine Pipeline, die durch geschickte Lastverteilung und Vermeidung von Duplikaten den Prozess weiter beschleunigen kann. Dies eignet sich insbesondere für große Datensätze von zu platzierenden Sequenzen, und hat die Berechnungen erst ermöglicht, die wir zum testen der im weiteren vorgestellten Methoden benötigt haben.
Im Anschluss stellen wir zwei Methoden vor, um die Placement-Ergebnisse verschiedener Proben miteinander zu vergleichen. Die Methoden, Edge Dispersion und Edge Correlation, visualisieren den Referenz-Baum derart, dass die in Bezug auf die Proben interessanten und relevanten Regionen des Baumes sichtbar werden. Edge Dispersion zeigt dabei Regionen, in denen sich die Häufigkeit der in den Proben vorhandenen mikrobischen Arten besonders stark zwischen den einzelnen Proben unterscheided. Dies kann als erste Erkundung von neuen Datensätzen dienen, und gibt Aufschluss über die Varianz der Häufigkeit bestimmter Arten. Edge Correlation hingegen bezieht zusätzlich Meta-Daten mit ein, die zu den Proben gesammelt wurden. Dadurch können beispielsweise Abhängigkeiten zwischen Häufigkeiten von Arten und Faktoren wie dem pH-Wert des Bodens oder dem Nitrat-Gehalt des Wassers, aus dem die Proben stammen, aufgezeigt werden. Es hat damit ähnlichkeiten zu einer bestehenden Methode names Edge PCA, die ebenfalls relevante Regionen des Baumen identifizieren kann, allerdings die vorhandenen Meta-Daten nur indirekt einbeziehen kann.
Eine weitere Fragestellung ist die Gruppierung (Clustering) von Proben anhand von Gemeinsamkeiten, wie beispielweise einer ähnlichen Verteilungen der Sequenzen auf dem Referenz-Baum. Anhand geeigneter Distanz-Maße wie der Kantorovich-Rubinstein-Distanz (KR-Distanz) können ähnlichkeiten zwischen Proben quantifiziert werden, und somit ein Clustering erstellt werden. Für große Datensätze mit hunderten und tausenden von einzlnen Proben stoßen bestehende Methoden für diesen Einsatzzweck, wie zum Beispiel das so genannte Squash Clustering, an ihre Grenzen. Wir haben daher die $k$-means-Methode derart erweitert, dass sie für Placement-Daten genutzt werden kann. Dazu präsentieren wir zwei Methoden, Phylogenetic $k$-means und Imbalance $k$-means, die verschiedene Distanzmaße zwischen Proben (KR-Distanz, und ein weiteres geeignetes Maß) nutzen, um Bäume mit ähnlichen Verteilungen von platzierten Sequenzen zu gruppieren. Sie betrachten jede Probe als einen Datenpunkt, und nutzen die zugrunde liegende Struktur des Referenz-Baumes für die Berechnungen. Mit diesen Methoden können auch Datensätze mit zehntausenden Proben verarbeitet werden, und Clusterings und ähnlichkeiten von Proben erkannt und visualisiert werden.
Wir haben außerdem ein Konzept namens Balances für Placement-Daten adaptiert, welches ursprünglich für so genannte OTU-Sequenzen (Operational Taxonomic Units) entwickelt wurde. Balances erlauben eine Beschreibung des Referenz-Baumes und der darauf platzierten Sequenzen, die ganze Gruppen von Referenz-Arten zusammenfasst, statt jede Art einzeln in die Berechnungen einfließen zu lassen. Diese Beschreibung der Daten bietet verschiedene Vorteile für die darauf basierenden Analysen, wie zum Beispiel eine Robustheit gegenüber der exakten Wahl der Referenz-Sequenzen, und einer anschaulichen Beschreibung und Visualisierung der Ergebnisse. Insbesondere aus mathematischer Sicht sind Balances für die Analyse interessant, da sie problematische Artefakte aufgrund der kompositionellen Natur meta-genetischer Daten beheben. Im Zuge dieser Arbeit dienen Balances hauptsächlich als Zwischenschritt zur Daten-Repräsentation.
Eine Anwendung von Balances ist die so genannte Phylofactorization. Diese recht neue Methode teilt einen gegebenen Baum derart in Sub-Bäume ein, dass jeder Sub-Baum eine Gruppe von Arten darstellt, die in Bezug auf gegebene Meta-Daten pro Probe relevant sind. Dadurch können beispielsweise Gruppen identifiziert werden, deren evolutionäre Merkmale sich in Abhängigkeit von Meta-Daten wie pH-Wert angepasst haben im Vergleich zu anderen Gruppen. Dies ist ähnlich zur oben genannten Edge Correlation, aber kann zum einen durch geschickte mathematische Ansätze (insbesondere der Nutzung von Generalized Linear Models) mehrere Meta-Daten gleichzeitig einbeziehen, und zum anderen auch verschachtelte Gruppen finden. Die zugrunde liegenden Ideen dieser Methoden bieten einen großen Spielraum sowohl für Analysen von Daten, als auch für Weiterentwicklungen und Ergänzungen für verwandte Fragestellungen. Wir haben diese Methode für Placement-Daten adaptiert und erweitert, und stellen diese Variante, genannt Placement-Factorization, vor. Im Zuge dieser Adaption haben wir außerdem verschiedene ergänzende Berechnungen und Visalisierungen entwickelt, die auch für die ursprüngliche Phylofactorization nützlich sind.
Alle genannten neuen Methoden wurden ausführlich getestet in Bezug auf ihre Eignung zur Erforschung von mikrobiologischen Zusammenhängen. Wir haben dazu verschiedene bekannte Datzensätze von DNS-Sequenzen aus Wasser- und Bodenproben, sowie Proben des menschlichen Mikrobioms, verwendet und diese auf geeigneten Referenz-Bäumen platziert. Anhand dieser Daten haben wir zum einen die Plausibilität der durch unsere Analysen erzielten Ergebnisse geprüft, als auch Vergleiche der Ergebnisse mit ähnlichen, etablierten Methoden vorgenommen. Sämtliche Analysen, Visualisierungen, und Vergleiche werden in den jeweils entsprechenden Kapiteln vorgestellt, und die Ergebnisse dargestellt. Alle Tests zeigen, dass unsere Methoden auf den getesteten Datensätzen zu Resultaten führen, die konsistent mit anderen Analysen sind, und geeignet sind, um neue biologische Erkenntnisse zu gewinnen.
Sämtliche hier vorgestellten Methoden sind in unserer Software-Bibliothek genesis implementiert, die wir im Zuge dieser Arbeit entwickelt haben. Die Bibliothek ist in modernem C++11 geschrieben, hat einen modularen und funktions-orientierten Aufbau, ist auf Speichernutzung und Rechengeschwindigkeit optimiert, und nutzt vorhandene Multi-Prozessor-Umgebungen. Sie eignet sich daher sowohl für schnelle Tests von Prototypen, als auch zur Entwicklung von Analyse-Software für Endanwender. Wir haben genesis bereits erfolgreich in vielen unserer Projekte eingesetzt. Insbesondere bieten wir sämtliche hier präsentierten Methoden über unser Software-Tool gappa an, das intern auf genesis basiert. Das Tool stellt einen einfachen Kommandozeilen-Zugriff auf die vorhandenen Analysemethoden bereit, und bietet ausreichend Optionen für die Analysen der meisten End-Anwender.
Im abschließenden Kapitel wagen wir einen Ausblick in weitere Forschungsmöglichkeiten im Bereich der Methoden-Entwicklung für meta-genetische Fragestellungen im Allgemeinen, und der placement-basierten Methoden im Speziellen. Wir benennen verschiedene Herausforderungen in Bezug auf die Nutzbarkeit solcher Methoden für Anwender und ihrer Skalierbarkeit für immer größer werdende Datensätze. Außerdem schlagen wir verschiedene weitergehende Ansätze vor, die zum Beispiel auf neuronalen Netzwerken und Deep Learning basieren könnten. Mit aktuellen Datensätzen wären solche Methoden nicht robust trainierbar; durch das in Zukuft zu erwartenden Wachstum an Daten kann dies allerdings bald in den Bereich des Möglichen kommen. Schließlich identifizierenden wir einige tiefer gehende Forschungsfragen aus der Biologie und Medizin, bei deren Beantwortung unsere Methoden in Zukunft helfen können.
Abstract (englisch):
The DNA is the hereditary basis of all known life on the planet. Deciphering this "code of life" is hence of key importance for biology in general, and for unravelling the evolutionary relationships between biological species in particular. The last few decades have seen rapid technological advances in DNA sequencing, with no slowdown of this trend being in sight. Research in biology hence has high demand for computational methods, both with respect to storage and processing of these huge datasets, and with respect to analysis and visualization thereof.
A basic concept in biology is that of the tree of life, which describes the evolutionary relationship between species. ... mehrThe respective field of science is called phylogenetics, and the resulting structures are called phylogenetic trees. Often, these trees are based on the comparison of DNA sequences of the species, and are build on the idea that species with similar sequences are located on nearby branches of the tree. The inference of such a tree based on DNA data can be formulated as an optimization problem, that poses a challenge for computer science due to the ever increasing amount of available data. For example, a current directive in micro-biology is to investigate the composition of samples taken from environments such as ocean water, soil, or the human body: Which microbial species, bacteria and other single cellular organisms, are present in these environments and samples? This field of research is called meta-genomics. It is infeasible to compute a robust phylogenetic tree for the millions of sequences obtained from such samples. An alternative approach is the so called phylogenetic placement of the sequences on a reference tree: Given a tree of reference sequences of known species that covers the expected diversity in the samples as much as possible, the evolutionary relationship of the sequences in the samples to the reference tree is determined. This yields a mapping from sequences to positions of related species in the reference tree. This mapping can also be understood as a distribution of sequences on the tree: This interpretation allows for example to visualize which species (and their next of kin) are frequently present in the samples.
In this work, we developed novel methods for pre- and post-processing, analysis, and visualization of phylogenetic placement of sequences. Firstly, we present a method to automatically obtain a suitable reference tree to be used for placement. The method is called PhAT (Phylogenetic Automatic (Reference) Trees), and uses databases of known DNA sequences in order to determine suitable reference sequences. The trees produced by PhAT are for example useful when the expected species diversity in the samples is not yet known: In this case, a broad tree that covers many known species can help to discover novel, unknown species. In the same chapter, we also present two auxiliary methods that accelerate and enable the process and the computations needed for the placement of very large datasets. On the one hand, we present Multilevel-Placement, that uses a divide-and-conquer approach to split large reference trees into small, nested trees. It thereby improves speed and accuracy of the placement process compared to using one large reference tree. On the other hand, we describe a pipeline that maximizes load distribution and further accelerates the placement process by avoiding duplicate computations. This is particularly suited for large datasets, and was a necessary improvement to enable the computations needed for the tests of the further methods presented in this work.
Subsequently, we present two methods to compare the placement results of distinct samples with each other. The methods, Edge Dispersion and Edge Correlation, visualize the reference tree so that the interesting and relevant regions of the tree (with respect to the samples) become apparent. Edge Dispersion shows regions where the frequency of microbial species in the samples differs most in between samples. This can serve as a first exploration of a dataset, and indicates the variance of the occurrences of species. Edge Correlation on the other hand additionally takes meta-data into account that was collected per sample. It hence can for example show the dependencies between occurrences of species and environmental factors such as the pH-value of the soil, or the nitrate content of the water where each sample was taken from. This bears some similarity to an existing method called Edge PCA, which also highlights relevant regions of the reference tree, but can only indirectly incorporate meta-data features.
Another research question is that of grouping or clustering of samples based on similarities, for example a similar distribution of sequences on the reference tree. By using suitable distance measures such as the Kantorovich-Rubinstein distance (KR distance), similarities between samples can be quantized, and leveraged to cluster them. For large datasets with hundreds to thousands of distinct samples, existing methods for this purpose, such as the so called Squash Clustering, reach their scalability limits. We thus extended the $k$-means method to be applicable to placement data. To this end, we present two methods, Phylogenetic $k$-means and Imbalance $k$-means, that use two different distance measures between samples (KR distance, and another suitable measure) to cluster trees with similar distributions of placed sequences. These methods regard each sample as a distinct data item, and use the underlying structure of the reference tree for the computations. These methods can be applied to datasets with tens of thousands of samples, in order to find clusters and similarities between samples, and visualize these.
Furthermore, we adapted a concept called Balances to placement data, which was originally intended for so called OTU sequences (Operational Taxonomic Units). Balances allow for a description of the reference tree and the sequences placed on it in a way that summarizes groups of referece species, instead of taking each species into account individually. This description of the data offers several advantages for subsequent analysis steps; for example, it is robust in terms of the exact choice of reference sequences, and offers an intuitive way of visualizing results obtained from these analyses. Balances are in particular helpful from a mathematical standpoint, as they circumvent problematic artifacts due to the compositional nature of meta-genomic data. In this work, balances are mainly used as an intermediate step for data representation purposes.
One application of balances is the so called Phylofactorization. This relatively recent method splits a given tree into a set of sub-trees so that each sub-tree represents a group of species that are relevant with respect to the meta-data features of the given samples. This allows for example to identify groups whose evolutionary traits changed depending on meta-data such as pH-value in comparison to other groups. This is similar to the Edge Correlation method mentioned above, but further allows to incorporate several meta-data features at once and can find nested groups of species, by leveraging mathematical approaches such as Generalized Linear Models. The underlying concepts of Phylofactorization are versatile both for data analysis as well as for extension and adaptation to releated research questions. We have adapted the method to placement data, and present this variant, which we call Placement-Factorization. Additionally, we developed several auxiliary computations and visualizations of the results that are also useful for the original Phylofactorization.
All mentioned novel methods were extensively tested with respect to their suitability for discovering biological knowledge. To this end, we used several DNA sequence datasets from water and soil, as well as from the human body, and phylogenetically placed them on suitable reference trees. Based on this, we tested the plausibility of the results obtained from our analyses, and compared them to the results of simiar, established methods. All analyses, visualizations, and comparisons are described in detail in the respective chapters, along with the results and their interpretations. All tests show that our methods yield results on the datasets that are consistent with other types of analyses, and are suitable for discovering novel biological knowledge.
The methods presented here are implemented in our software library genesis, which we devloped alongside this work. The library is written in modern C++11, has a modular and function-oriented design, is optimized for memory consumption and computing speed, and leverages multi-core environments. It is hence suitable for rapid testing of prototype software, as well as for developing analysis software for end users. We already have successfully deployed genesis in several of our projects. In particular, all presented methods are incorporated into our command line tool gappa, which is internally based on genesis. The tool has a simple command line interface to our analysis methods that offers sufficient options for most end users.
In the final chapter, we dare an outlook into possible research directions for method development in meta-genetics in general, and placement-based methods in particular. We identify several challenges with respect to the usability of such methods for researchers, and their scalability to ever larger datasets. Furthermore, we suggest several further approaches, for instance based on neural networks and deep learning. With current datasets, such methods cannot robustly be trained; due to the expected growth of data in the near future however, such approaches are likely to become feasible. Finally, we identify some in-depth research questions from the fields of biology and medicine for which our methods might be useful in the future.
