Computational Sciences Center

Vortrag vom Do., d. 19.11.2015

Algorithmen für Big Data Probleme bei der Genom-Rekonstruktion

 
Prof. Dr. Anand Srivastav (CAU Kiel, Institut für Informatik)
 

Das Genom-Assembly ist ein zentrales Problem in der Biologie und Medizin zur Aufklärung der genetischen Funktionalitäten. Heutzutage wird das Genom mit Hilfe von sogenannten Sequenzierern, der shotgun Methode, die auf den Nobelpreisträger Fredrick Sanger zurückgeht, in kleine Teile zerlegt und die Aufgabe besteht darin, das Genom wieder zu rekonstruieren. Dieser Umweg ist leider notwendig, da es keine Technologie gibt, die aus dem Zellmaterial Genome direkt herauslesen könnte.

Die Rekonstruktion selbst ist dann ein Problem der Diskreten Mathematik, genauer der Diskreten Optimierung und Graphentheorie, wobei aus dem Assembly-Graphen, der die Sequenzierstücke ( reads) als Knoten hat, möglichst lange Pfade gewonnen werden sollen. Dieses Problem selbst ist schon komplexitätstheoretisch äußerst schwierig, es ist NP-schwer. Das Rekonstruktionsproblem wird noch weiter dadurch verschärft, dass der Assembly-Graph in vielen Anwendungen zu groß ist, als dass er in den Hauptspeicher eines Rechners (RAM) passen würde (Big Data Problem).

Wir stellen neue mathematische Methoden vor, mit deren Hilfe es gelingt, den Assembly-Graphen auf einem externen Speicher zu halten, und das längste Pfadeproblem unter Zugriff auf kleine Teile des Graphen, die gerade in die RAM des Rechners passen, zu lösen. Die Technik, die hier verwendet wird, ist das Semistreaming-Modell, in dem die Kanten des Graphen als ein Datenstrom kommen und quasi sofort eine Entscheidung getroffen werden muss, ob diese verwendet werden oder nicht. Die Kunst besteht nun darin, aus dieser sehr eingeschränkten Information längste Pfade zu konstruieren, d.h. mit unvollständiger Information ein komplexes kombinatorisches Problem zu lösen.

Dies ist eine Arbeit im DFG SPP 1736 Algorithms for Big Data und im Excellenzcluster The Future Ocean gemeinsam mit Prof. Thorsten Reusch (Geomar) und Prof. Philip Rosenstiel (IKMB).

 

Zeit und Ort:  Do., 19.11.2015, 18.00 Uhr, Audimax - Hörsaal D, Christian-Albrechts-Platz 2

Bemerkung:  Der Vortrag ist Bestandteil der Ringvorlesung Numerische Simulation;; vgl. Pressemitteilung Nr. 371/2015 vom 16.10.2015 . Dank einer finanziellen Unterstützung des Alumni Kiel e.V. können die Vorträge aufgezeichnet werden und stehen im Netz zur Verfügung.

Vortrags-Video: