Algorithmische Fundierung des Genom-Assembly: Streaming und External-Memory-Techniken

• Antragsteller: Professor Thorsten Reusch, Ph.D.; Professor Philip Caspar Rosenstiel, Ph.D.; Professor Dr. Anand Srivastav
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2014 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 255256381

De novo Genom-Assembly ist eine grundlegende Aufgabe in den Lebenswissenschaften. Es erfordert die Lösung von kombinatorischen Optimierungsproblemen in sehr großen Graphen, die Speicher im Terabyte-Bereich beanspruchen. Der wissenschaftliche Fortschritt wird dadurch behindert, dass bestehende Algorithmen für solche Probleme nicht mit der Big-Data-Herausforderung in einer speicher- und zeiteffizienten Weise umgehen können. In den ersten zwei Jahren des Projektes wurde Grundlagenarbeit für eine innovative Algorithmik für Genom-Assembly durchgeführt, in enger Zusammenarbeit mit den Kieler Gruppen in mariner Ökologie und molekularer Biologie. Ein Schlüsselresultat sind neue Algorithmen für das Finden von Substrukturen in großen Graphen, wie lange Pfade oder Eulertouren, die durch Streaming-Techniken besonders speicher-effizient arbeiten. Zudem liefern wir einen Algorithmus, dereine drastische Reduktion von Assembly-Graphen bewirkt. Dennoch bleiben diese Graphen groß, und man steht weiterhin vor einer Big-Data-Herausforderung. In der zweiten Phase des Projektes sollen Algorithmen für Graphenprobleme mit Bezug zum Genom-Assembly unter Einsatz von External-Memory-Techniken und mächtigeren Streaming-Modellen entworfen werden. Diese algorithmische Forschung wird durch den Aufbau einer External-Memory-Bibliothek von Assembly-Graphen fundiert, die in Kooperation mit der SPP-Gruppe in Frankfurt bereits erfolgt. Für External-Memory, Streaming, und Algorithmen zum Zeichnen von Graphen erwarten wir wissenschaftlichen Fortschritt und Synergien in Kooperation mit anderenGruppen im SPP, die in diesen Bereichen ausgewiesen sind. Unsere speicher-effizienten Algorithmen sollen implementiert und auf Assembly-Graphen für Genome und Transcriptome, die durch Shotgun-Sequenzierung in den biowissenschaftlichen Gruppen in Kiel gewonnen werden, z.B. in der Marinen Ökologie oder der Klinischen Molekularbiologie, angewendet werden.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1736: Algorithmen für große Datenmengen