Sensitive Protein Alignments at Tree-of-Life Scale Using DIAMOND

Abstract

Pairwise alignment of protein sequences is a fundamental method of bioinformatics. Since the advent of Next Generation Sequencing, the arising quantities of sequence data have grown exponentially. In the context of metagenomics studies, DNA in the order of terabases is sequenced from the environment or host organisms, and sensitive protein alignment is a key method to investigate the enormous diversity of microbial life. In the context of evolutionary studies, pairwise protein alignment enables the detection of distantly related sequences that have diverged over billions of years. The standard software for protein alignment is NCBI BLAST, whose computational performance is not sufficient to process currently existing quantities of data, requiring decades to analyse large datasets. This is due to the fundamental algorithmic hardness of the alignment problem on proteins down to 20% sequence identity, for which no efficient solutions are known. In this work I present the protein aligner DIAMOND, whose first version was up to 20,000-fold faster than BLAST for short read alignment, and 650 to 2,500- fold faster in its sensitive mode that was already suitable for a broad range of applications. Furthermore, I present the enhanced version DIAMOND v2 which achieves a speedup of 80 to 360 vs BLAST at comparable sensitivity, a speedup of 12 to 15 vs the competitor tool MMseqs2, and a speedup of 6 to 8 vs the first version of DIAMOND. Central algorithmic aspects are multiple spaced seeds that drastically improve the specificity of seeding, and furthermore the double indexing of query and target sequences allowing the efficient processing of seed hits with improved use of the CPU caches. Lastly, the consequent optimisation of the processing pipeline using SIMD instructions and suitable heuristics is important to increase the performance substantially beyond the level of elementary approaches.

Paarweises Alignment von Proteinsequenzen ist eine grundlegende Analysemethode der Bioinformatik. Seit dem Aufkommen von Next-Generation- Sequencing haben die anfallenden Sequenzdatenmengen einem exponentiellen Wachstum unterlegen. Insbesondere im Rahmen von Metagenomik-Studien wird DNA in der Größenordnung von Terabasen aus der Umwelt oder Wirtsorganismen sequenziert, und sensitives Sequenzalignment auf Proteinebene ist eine Schlüsselmethode, um die enorme Vielfalt mikrobiellen Lebens zu erforschen. Im Rahmen evolutionärer Studien ermöglicht es das paarweise Proteinalignment, entfernt verwandte Sequenzen zu erkennen, die über Milliarden von Jahren voneinander divergiert sind. Als Standardsoftware für Proteinalignment gilt NCBI BLAST, dessen rechnerische Leistungsfähigkeit nicht ausreichend ist, um gegenwärtig existierenden Datenmengen gerecht zu werden, und eine Rechenzeit von Jahrzehnten zur Auswertung großer Datensätze benötigen würde. Dies hängt mit der grundsätzlichen algorithmischen Schwere des Alignmentproblems auf Proteinen mit bis zu 20% Sequenzidentität hinunter ab, für das keine effizienten Lösungen bekannt sind. In dieser Arbeit wird der Proteinaligner DIAMOND vorgestellt, dessen erste Version bis zu 20.000-fach schneller als BLAST für das Alignment von Short Reads ist, sowie 650 bis 2.500-fach schneller in seinem sensitiven Modus, der bereits für ein breites Anwendungsspektrum geeignet ist. Darüber hinaus wird die Weiterentwicklung DIAMOND v2 vorgestellt, die einen Speedup von 80 bis 360 gegenüber BLAST bei vergleichbarer Sensitivität erreicht, sowie von 12 bis 15 gegenüber der Konkurrenzsoftware MMseqs2 und 6 bis 8 gegenüber der ersten Version von DIAMOND. Algorithmisch zentrale Aspekte sind zum einen mehrfache spaced Seeds, mit denen die Spezifität des Seedings entscheidend verbessert wird. Zum anderen ist dies die doppelte Indexierung von Query- und Targetsequenzen, die eine effiziente Verarbeitung der Seedtreffer unter verbesserter Ausnutzung der CPU-Caches ermöglicht. Zuletzt ist die konsequente Optimierung der Verabeitungspipeline durch SIMD-Instruktionen und geeignete Heuristiken wichtig, um die Performance wesentlich über das Niveau elementarer Ansätze hinaus zu steigern.