AP 1

Skalierung, Optimierung nicht alignment-basiertes Assembly

Der Beitrag dieses Arbeitspakets zu der im Gesamtprojekt entwickelten Bibliothek ist die Entwicklung eines parallelen Verfahrens zur de novo Assemblierung. In diesem Schritt werden einzelne kurze DNA-Sequenzen aus den NGS-Sequenziergeräten zu größeren zusammenhängenden Genomabschnitten, sogenannten Contigs, zusammen geführt, ohne dabei von einem Bezug zu einem Referenzgenom zu profitieren. Anwendungen wie Velvet und ALLPATHS erzeugen Resultate von sehr hoher Güte, jedoch sind die Anwendungen nicht auf effiziente Hardwarenutzung von Großrechnerarchitekturen ausgelegt. In diesem Zusammenhang hat das RRZK in Vorarbeiten bereits erste Schritte unternommen. So wurden im Rahmen einer Marktanalyse die Programme ABySS sowie Ray identifiziert, welche auf der gleichen Methode aufsetzen und diese Aufgabe zwar MPI-parallel, jedoch nicht optimal umsetzen. Erste Untersuchungen zeigen, dass eine Adaptierung dieser Ansätze für Velvet und ALLPATHS erfolgversprechend sind. Zusätzlich zu den genannten Verfahren werden neu entstandene Codes und einige weitere sinnvolle Ansätze untersucht. So ist z.B. der im Programm IMAGE verwendete und teilweise auf Velvet aufbauende Ansatz für das iterative Schließen verbleibender Scaffold Gaps eine erfolgversprechende Strategie für die praktische Durchführung von de novo Assemblies.

Aufsetzend auf den Vorarbeiten wird eine tiefergehende Analyse durchgeführt. In dieser werden die Kernalgorithmen untersucht und auf Parallelisierungs- und Beschleuniger-Eignung, beispielsweise GPGPUs überprüft. Insbesondere werden die Speicherverteilungskonzepte mit Hinblick auf eine Gleichmäßigkeit der Verteilung der Daten und Datenlokalität verfeinert und angepasst, um die höchstmögliche Skalierung zu gewährleisten. Nach der Analyse wird die Implementierung im Vordergrund der Aktivitäten des Arbeitspaketes stehen. Diese wird kontinuierlich durch Prototyping und Leistungsmessungen auf Ihre Effektivität hin untersucht. Ziel ist es, Probleme von erheblich größerem Umfang in geringerer Zeit zu lösen und eine Implementierung zu erreichen, die moderne Rechner sowie kommende Architekturen und Rechnerklassen optimal ausnutzt. Anschließend wird eine Optimierung der parallelen Kommunikation und der Hotspots, z. B. mittels Vektorisierung, durchgeführt. In der nächsten Phase werden die Kernalgorithmen in das Arbeitspaket AP3 überführt, um sie in Form einer skalierenden Bibliothek einer breiteren Nutzung zuführen zu können. Eine anschließende Testphase soll die Zielerreichung bezüglich Anwendbarkeit, Korrektheit sowie Skalierbarkeit und Performance auf simulierten und realen Genomdaten überprüfen.

Bundesministerium für Bildung und Forschung

Förderkennzeichen
01IH11003A;
01.06.2011 - 31.05.2014