AP 2

Skalierung, Optimierung alignment-basiertes Assembly

Alignment-basierte Assembly Algorithmen erzielen in der Regel eine höhere Qualität des finalen Assemblies. Vor allem, wenn Reads unterschiedlicher Sequenziertechnologien wie 454, Sanger und Illumina zusammengeführt werden müssen, ist es von Vorteil, auf klassische Alignment Algorithmen zurückzugreifen. Rein Graphen-basierte Algorithmen mit einfachen Stringvergleichen können bei längeren Sequenzen nur ein mäßig gutes Ergebnis erzielen und werden von Alignment-basierten Algorithmen um ein vielfaches qualitativ übertroffen. Die Programme MiraEST (Chevreux, et al., 2010) und SSAHA2 (Ning, et al., 2001) wurden bereits erfolgreich für die de novo Assemblierung unterschiedlicher Sequenztypen verwendet und werden auch in diesem Arbeitspaket zum Einsatz kommen. Beide Programme benutzen eine schrittweise Vorgehensweise, in dem sie einen schnellen Graphen-basierten Suchalgorithmus verwenden, um einen Überblick über mögliche identische Sequenzen zu erhalten und anschließend einen klassischen Alignmentschritt durchführen, um ein hoch qualitatives Alignment des Assemblies zu erzielen. Diese Programme sind jedoch bislang nicht parallelisiert worden. Ziel dieses Arbeitspaketes ist es, den Workflow der Alignment-basierten Assembly Algorithmen auf ihr Potential zur Parallelisierung und Optimierung zu untersuchen. Weiterhin soll der hohe Bedarf an Hauptspeicher, der bei de novo Assemblierung bisher unumgänglich anfällt, verringert werden.

Neben den Alignment-basierten Assemblierungsmethoden werden in diesem Arbeitspaket auch die Möglichkeiten der de novo Assemblierung mithilfe eines verwandten – jedoch nicht artgleichen – Genoms, die so genannte vergleichende Assemblierung untersucht. Einerseits haben derlei Ansätze um ein Vielfaches verbesserte Resultate bei der de novo Assemblierung von Genomen erzielt (Nijkamp, et al, 2010). Andererseits ist dies für Studien im Zebrafisch interessant, da dieser Organismus eine unerwartet hohe Anzahl von Einzelmutationen pro Individuum hat und daher mit herkömmlichen Methoden des Genome Mappings schwer zu assemblieren ist. Aus denselben Gründen wäre dieser Ansatz auch für die Behandlung von stark veränderten Chromosomenstrukturen bei Patienten anwendbar. Ein weiterer Ansatz dieser Art wurde von Palmer, et al. (2010) und Pop, et al. (2004) vorgestellt, die neue Module für das Open Source Projekt AMOS entwickelt haben und mit dem vergleichenden Assembly gegen mehrere Referenzgenome zumindest für Bakterien ein bedeutend besseres Ergebnis erzielen konnten. In beiden Fällen wird ein klassischer Alignmentschritt gegen ein Referenzgenom mit der de novo Assemblierung kombiniert, um Contigübergänge und die Anordnung von Contigs zu verbessern.

Neben den bereits beschriebene Programmen zur de novo Assemblierung werden in diesem Arbeitspaket auch Programme die explizit zur denovo Assemblierung von Transkripten und sukzessiven Analyse der Genexpression verwendet werden (Cufflinks (Trapnell, 2010), Tophat (Trapnell, 2009), Cufflinks (Guttman, 2010)) auf Möglichkeiten der Optimierung untersucht.

Die verschiedenen Paralleliserungsansätze für Alignment-basierte Assemblierungsverfahren werden auf ihr Potential zur Parallelisierung auf Multi- und Many-Core-Architekturen, massiv parallelen Systemen sowie Hardware-Beschleunigern hin untersucht. Basierend darauf werden parallele Algorithmen prototypisch implementiert. Dabei wird besonders auf die Lokalität der Datenzugriffe, die Gleichverteilung der Rechenlast sowie die optimale Ausnutzung der Speicherhierarchie geachtet. Detaillierte Performanceanalysen mit Tools wie Vampir werden schon während der Implementierung der Prototypen auf etwaige Bottlenecks hinweisen und das Tuning der Algorithmen unterstützen. Analog zu AP1 sollen auch hier die Kernalgorithmen in die Bibliothek, welche in AP3 entwickelt wird, einfließen. Um eine gesamt höhere Leistung der Programme zu erzielen, können auch die Resultate von AP1 auf die Graphen-basierten Algorithmen der verwendeten Programme übertragen werden, sowie Möglichkeiten zur Optimierung des klassischen Alignmentschrittes mittels existierender Lösungen wie etwa MPI-BLAST implementiert werden.

Bundesministerium für Bildung und Forschung

Förderkennzeichen
01IH11003A;
01.06.2011 - 31.05.2014