SSW Library: An SIMD Smith-Waterman C/C++ Library for Use in Genomic Applications

By Mengyao Zhao, Wan-Ping Lee, Erik P. Garrison, Gabor T. Marth. 2012

246 citations recorded by the source corpus.

Background The Smith-Waterman algorithm, which produces the optimal pairwise alignment between two sequences, is frequently used as a key component of fast heuristic read mapping and variation detection tools for next-generation sequencing data. Though various fast Smith-Waterman implementations are developed, they are either designed as monolithic protein database searching tools, which do not return detailed alignment, or are embedded into other tools. These issues make reusing these efficient Smith-Waterman implementations impractical. Results To facilitate easy integration of the fast Single-Instruction-Multiple-Data Smith-Waterman algorithm into third-party software, we wrote a C/C++ library, which extends Farrar’s Striped Smith-Waterman (SSW) to return alignment information in addition to the optimal Smith-Waterman score. In this library we developed a new method to generate the full optimal alignment results and a suboptimal score in linear space at little cost of efficiency. This improvement makes the fast Single-Instruction-Multiple-Data Smith-Waterman become really useful in genomic applications. SSW is available both as a C/C++ software library, as well as a stand-alone alignment tool at: https://github.com/mengyao/Complete-Striped-Smith-Waterman-Library. Conclusions The SSW library has been used in the primary read mapping tool MOSAIK, the split-read mapping program SCISSORS, the MEI detector TANGRAM, and the read-overlap graph generation program RZMBLR. The speeds of the mentioned software are improved significantly by replacing their ordinary Smith-Waterman or banded Smith-Waterman module with the SSW Library.

Subfields: Genetics, Molecular Biology

How researchers see this paper

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

In Genetics

In Molecular Biology

Citations in the corpus

Clustering huge protein sequence sets in linear time (2017, background): “[10], which builds on code from the SSW library [32].”
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.”
Protein Representation Learning by Geometric Structure Pretraining (2022, unknown): “MMseqs2 (Steinegger & Söding, 2017) 0.001 0.082 0.542 0.208 3D-BLAST (Yang & Tung, 2006) 0.009 0.126 0.572 0.235 CLE-SW (Zhao et al., 2013) 0.021 0.293 0.763 0.359 CE (Shindyalov & Bourne, 1998) 0.131 0.529 0.885 0.515 TMalign-fast (Zhang & Skolnick, 2005) 0.188 0.618 0.906 0.571 TMalign (Zhang & Sk”
MOSAIK: A Hash-Based Algorithm for Accurate Next-Generation Sequencing Short-Read Mapping (2013, methodology): “Initial testing of the SIMD Smith-Waterman algorithm demonstrate a twofold speed up [65].”
An efficient and scalable analysis framework for variant extraction and refinement from population-scale DNA sequence data (2015, methodology): “GotCloud uses widely available alignment software, such as BWA (Li and Durbin 2009) and MOSAiK (Zhao et al. 2013), to generate”