Striped Smith-Waterman speeds database searches six times over other SIMD implementations

By Michael Farrar. Bioinform., 2007

298 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Hardware and Architecture, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/1c15f69566af6198f336b961aecf418b5ccd07d3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Hardware and Architecture

In Molecular Biology

Citations in the corpus

SWPS3 – fast multi-threaded vectorized Smith-Waterman for IBM Cell/B.E. and ×86/SSE2 (2008, methodology): “swps3 is largely based on previous implementations of the striped Smith-Waterman algorithm by [5].”
Variation graph toolkit improves read mapping by representing genetic variation in the reference (2018, unknown): “Finally, to further demonstrate the ability of vg to map to arbitrary sequence graphs, we constructed a vg graph from a metagenomic assembly of a polar freshwater viral DNA community23 that was constructed with the minia324 assembler.”
Minimap2: pairwise alignment for nucleotide sequences (2017, background): “low gaps longer than several hundred base pairs, nucleotide-level alignment is much slower than chaining. SSE acceleration is critical to the performance of minimap2. Traditional SSE implementations (Farrar, 2007) based on Eq. (4) can achieve 16-way parallelization for short sequences, but only 4-wa”
HHblits: lightning-fast iterative protein sequence searching by HMM-HMM alignment (2011, methodology): “A very fast gap-less local alignment between the extended query profile and the extended database sequences is followed by a gapped local alignment, for which we modified code by Michael Farrar[9].”
A survey of sequence alignment algorithms for next-generation sequencing (2010, methodology): “Using the SSE2 CPU instructions implemented in most latest x86 CPUs, [34] derived a revised Smith–Waterman algorithm that is over 10 times faster than the standard algorithm.”
160-fold acceleration of the Smith-Waterman algorithm using a field programmable gate array (FPGA) (2007, methodology): “Rognes and Seeberg's software implementation running on a Pentium III 500 MHz processor (2000) showed a performance of 150 million cells per second [8], while recently Farrar's software implementation running on a Xeon Core Duo 2 GHz processor (2007) showed a performance of 3,000 million cells per s”
Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM (2013, methodology): “s the mean and the variance ˙2 of the insert size distribution from reliable single-end hits. For the top 100 hits (by default) of each end, BWA-MEM performs SSE2-based Smith-Waterman alignment (SW; Farrar 2007) for the mate within a window [ 4˙;+4˙] from each hit. The second best SW score is record”
Aligning short reads to reference alignments and trees (2011, methodology): “However, as (Farrar, 2007) demonstrated for the Smith–Waterman algorithm (Smith and Waterman, 1981 ), dynamic programming algorithms can be significantly accelerated by means of vectorization.”
CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment (2008, background): “• the results of the SIMD implementation by Farrar as reported in his paper [3].”
Fast and accurate protein structure search with Foldseek (2022, methodology): “The seven features cos ϕ 12 , cos ϕ 34 , cos ϕ 15 , cos ϕ 35 , cos ϕ 14 , cos ϕ 23 , cos ϕ 13 and the distance ∣ C α , i − C α , j ∣ describe the conformation between the backbone fragments.”
MOSAIK: A Hash-Based Algorithm for Accurate Next-Generation Sequencing Short-Read Mapping (2013, methodology): “Improvements in the computational performance can be achieved at the expense of decreased sensitivity, but ongoing development (including replacing the traditional Smith-Waterman algorithm with a single-instruction-multiple-data (SIMD) SmithWaterman algorithm [65,66]) provides significant performanc”
GR-Align: fast and flexible alignment of protein 3D structures using graphlet degree similarity (2014, methodology): “In particular, the Single Instruction on Multiple Data implementation proposed in Farrar (2007) is shown to be up to 16 times faster than the linear implementation, and the Graphics Processing Unit (GPU) implementation proposed in Liu et al. (2009) is shown to be up to 30 times faster the linear…”