Schnellere Smith-Waterman-Datenbanksuchen mit inter-sequence SIMD-Parallelschaltung

HINTERGRUND: Der Smith-Waterman-Algorithmus für lokale Sequenzanpassung ist empfindlicher als heuristische Methoden zur Datenbanksuche, aber auch zeitaufwändiger. Der schnellste Ansatz zur Parallelisierung mit SIMD-Technologie wurde zuvor 2007 von Farrar beschrieben. Ziel dieser Studie war es, zu untersuchen, ob durch andere Ansätze zur Parallelisierung eine weitere Geschwindigkeitsverbesserung erzielt werden kann. ERGEBNISSE: Ein schnellerer Ansatz und dessen Implementierung werden beschrieben und bewertet. Im neuen Tool SWIPE werden Residuuen von sechzehn verschiedenen Datenbanksequenzen parallel zu einem Abfrage-Residuum verglichen. Mit einer Abfrage-Sequenz von 375 Residuuen wurde eine Geschwindigkeit von 106 Milliarden Zellaktualisierungen pro Sekunde (GCUPS) auf einem Dual-Intel-Xeon-X5650-Sechs-Kern-Prozessorsystem erreicht, was über sechsmal schneller ist als Software, die auf Farrars „gestreiftem“ Ansatz basiert. SWIPE war etwa 2,5-mal schneller, wenn die Programme nur einen einzelnen Thread verwendeten. Bei kürzeren Abfragen war der Geschwindigkeitszuwachs größer. SWIPE war etwa doppelt so schnell wie BLAST, als die BLOSUM50-Wertmatrix verwendet wurde, während BLAST etwa doppelt so schnell wie SWIPE für die BLOSUM62-Matrix war. Die Software ist für 64-Bit-Linux auf Prozessoren mit SSSE3 konzipiert. Der Quellcode ist verfügbar unter http://dna.uio.no/swipe/ unter der GNU Affero General Public License. SCHLUSSFOLGERUNGEN: Effiziente Parallelisierung mit SIMD auf Standardhardware ermöglicht es, Smith-Waterman-Datenbanksuchen über sechsmal schneller als zuvor durchzuführen. Der hier beschriebene Ansatz könnte die potenzielle Anwendung von Smith-Waterman-Suchen erheblich erweitern. Auch andere Anwendungen, die optimale lokale Anpassungswerte benötigen, könnten von einer verbesserten Leistung profitieren.