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
Translated title of the contribution | Performant Calculation of DNA-Primers via GPGPUs |
---|---|
Original language | German |
Title of host publication | Tagungsband FFH 2011 (5. Forschungsforum der österreichischen Fachhochschulen) |
Publisher | FH Campus Wien |
Number of pages | 2 |
ISBN (Print) | 978-3-902614-16-2 |
Publication status | Published - 2011 |
Event | FFH 2011 - 5. Forschungsforum der österreichischen Fachhochschulen - Wien (Favoriten), Austria Duration: 27 Apr 2011 → 28 Apr 2011 http://www.fh-campuswien.ac.at/die_fh/veranstaltungen/forschungsforum_2011/ |
Conference
Conference | FFH 2011 - 5. Forschungsforum der österreichischen Fachhochschulen |
---|---|
Country/Territory | Austria |
City | Wien (Favoriten) |
Period | 27.04.2011 → 28.04.2011 |
Internet address |
Keywords
- Bioinformatik
- GPGPU
- High-Performance-Computing
- Polymerase Kettenreaktion