Publikation

Performante Berechnung von DNA-Primern mittels GPGPUs im Hochdurchsatzverfahren

Outline:

B. Parsapour, H. Brandstaetter-Mueller, A. Hoelzlwimmer, G. Lirk, P. Kulczycki - Performante Berechnung von DNA-Primern mittels GPGPUs im Hochdurchsatzverfahren - Tagungsband FFH 2011 (5. Forschungsforum der österreichischen Fachhochschulen), Wien (Favoriten), Österreich, 2011, pp. 2

Abstract:

In der Molekularbiologie wird zur Vervielfältigung von DNA-Sequenzen im Hochdurchsatzverfahren hauptsächlich die Polymerase Kettenreaktion (PCR) eingesetzt. Für die Vervielfältigung einer gegebenen DNA-Sequenz werden mehrere kurze synthetisierte DNA-Fragmente, so genannte Primer, benötigt. Ein DNA-Fragment ist typischerweise 18 bis 30 Basenpaare lang. Eine PCR durchläuft die drei Phasen Denaturierung, Primerhybridisierung und Elongation. Diese drei Phasen werden mehrmals zyklisch abgearbeitet, um zahlreiche Kopien der ursprünglich gegebenen DNASequenz zu erhalten. Die Wahl geeigneter Primerkandidaten spielt eine wichtige Rolle in der Anwendung der PCR und heutzutage wird mit Hilfe von leistungsfähigen Computern berechnet, wie ein guter Primer aussehen muss. Die Berechnung von potentiellen Primerkandidaten erfolgt mit einem von uns speziell für diese bioinformatische Problemstellung entwickelten Algorithmus, der aufgrund der großen Datenmengen extrem rechenintensiv ist. Besonders rechenaufwändig wird unser Algorithmus auch dadurch, da er sich auf die Suche nach einem "Konsensusprimer" macht, der optimal auf sehr viele unterschiedliche DNA-Sequenzen passt. Dieser Algorithmus gliedert sich in die folgenden vier Schritte: 1. Erzeugung von kurzen DNA-Fragmenten aus der gegebenen DNA-Sequenz mittels Sliding-Window-Ansatz. Dabei wird mit einer zuvor festgelegten Fenstergröße (Länge des Primers) über die DNA-Sequenz iteriert. 2. Mutation der aus Schritt 1 resultierenden Primerkandidaten. Die Anzahl der Mutationen kann dabei variieren. 3. Filterung der Primerkandidaten nach diversen biologischen Merkmalen, z.B. nach ihrem GC-Gehalt. 4. Berechnung von Sequenzausrichtungen der Primerkandidaten gegen die gegebene DNA-Sequenz. Unser Algorithmus arbeitet hier nach einem modifizierten und hocheffizienten Hammingdistanz- Algorithmus. Aufgrund (1) der durch den technischen Fortschritt preisgünstig verfügbaren GPGPUs und (2) der besonders guten Eignung der beschriebenen biologischen Problemstellung für diese spezifische Prozessorarchitektur implementierten und optimierten wir obigen hochparallelen Algorithmus auf einer NVIDIA Tesla S1070. Ein besonders sensitives Kriterium für die Erreichung einer möglichst hohen Gesamtperformance des Algorithmus ist, neben dem Grad der Nebenläufigkeit, die Art der Verwendung der unterschiedlich schnellen Speicher der GPU. Um diesbezüglich aussagekräftige Performancewerte zu erhalten, haben wir obigen Algorithmus auf mehrere Varianten implementiert. Dazu zählen verschiedenste Techniken wie z.B. die Wahl des passenden GPU-Speichers (Global-Memory (GM), Shared-Memory (SM) etc.) sowie dessen Ausführungskonfiguration. Abbildung 1 zeigt die spezifische Rechenleistung der NVIDIA Tesla S1070 (in GFlops) aufgetragen über der Problemgröße (Länge der DNA-Sequenz in Basenpaaren). Parametrisiert wurde nach der Art des GPU-Speichers sowie nach dessen Konfiguration. Aus diesem Diagramm ist abzulesen, dass das größte Potential für eine Minimierung der Rechenzeit zur Lösung obigen Problems in einer Verwendung des Shared-Memory in der Konfiguration "no bank conflicts" liegt. Weitere Experimente in der zusätzlichen Dimension "Grad der Nebenläufigkeit" ergaben, dass, wider Erwarten, nicht die Maximalanzahl an Threads (512 pro Block) die beste Performance bringt. Viel mehr konnten wir feststellen, dass das Rechenleistungsmaximum für unser Problem bei einer Verwendung von 256 Threads pro Block liegt. 5. Forschungsforum der österreichischen Fachhochschulen - ConfTool Pro Printout 1

2011

Personen:

Forschungseinheiten:

Wissenschaftsgebiete: