Parasail: SIMD C library for global, semi-global, and local pairwise sequence alignments

BMC Bioinformatics

Software

Jeff Daily¹ 

[1] Pacific Northwest National Laboratory, High Performance Computing Group, 902 Battelle Boulevard, P.O. Box 999, MSIN J4-30, 99352, Richland, WA, USA;

关键词: Smith-Waterman;    Needleman-Wunsch;    Semi-global alignment;    Sequence alignment;    SIMD;    Database search;   

DOI  :  10.1186/s12859-016-0930-z

 received in 2015-11-18, accepted in 2016-02-03,  发布年份 2016

来源: Springer

【 摘 要 】

BackgroundSequence alignment algorithms are a key component of many bioinformatics applications.Though various fast Smith-Waterman local sequence alignment implementations have been developed for x86 CPUs, most are embedded into larger database search tools. In addition, fast implementations of Needleman-Wunsch global sequence alignment and its semi-global variants are not as widespread. This article presents the first software library for local, global, and semi-global pairwise intra-sequence alignments and improves the performance of previous intra-sequence implementations.ResultsA faster intra-sequence local pairwise alignment implementation is described and benchmarked, including new global and semi-global variants. Using a 375 residue query sequence a speed of 136 billion cell updates per second (GCUPS) was achieved on a dual Intel Xeon E5-2670 24-core processor system, the highest reported for an implementation based on Farrar’s ‘striped’ approach. Rognes’s SWIPE optimal database search application is still generally the fastest available at 1.2 to at best 2.4 times faster than Parasail for sequences shorter than 500 amino acids. However, Parasail was faster for longer sequences. For global alignments, Parasail’s prefix scan implementation is generally the fastest, faster even than Farrar’s ‘striped’ approach, however the opal library is faster for single-threaded applications. The software library is designed for 64 bit Linux, OS X, or Windows on processors with SSE2, SSE41, or AVX2. Source code is available from https://github.com/jeffdaily/parasailunder the Battelle BSD-style license.ConclusionsApplications that require optimal alignment scores could benefit from the improved performance. For the first time, SIMD global, semi-global, and local alignments are available in a stand-alone C library.

【 授权许可】

CC BY   
© Daily. 2016

【 图 表 】

12951_2017_255_Article_IEq54.gif

12951_2017_255_Article_IEq53.gif

12888_2023_5292_Article_IEq1.gif