Source-linked AI summary
SSW Library: An SIMD Smith-Waterman C/C++ Library for Use in Genomic Applications
Mengyao Zhao, Wan-Ping Lee, Erik Garrison, Gabor T. Marth
TL;DR
SW is central to genomic alignment, but fast striped implementations often lack detailed alignment output or are difficult to reuse. This paper presents SSW, a SIMD-accelerated C/C++ library extending Farrar’s striped SW with alignment and suboptimal-score information; it matches Farrar’s speed, doubles MOSAIK’s speed, and supports four genomic applications.
Problem
Fast striped SW implementations lack detailed alignment information or standalone, reusable interfaces, despite SW’s extensive use in genomic analysis.
Method
SSW extends Farrar’s striped SW with SIMD acceleration, optimal traceback, and secondary alignment scoring through recorded maxima, reversed SIMD SW, and banded SW.
Results
SSW is as fast as Farrar’s accelerated SW while returning detailed alignment information, achieves a two-fold MOSAIK speedup, and halves RZMBLR runtime from 1795.66 to 973.02 seconds.
Takeaways & Limitations
The reusable SSW library has been adopted in MOSAIK, SCISSORS, TANGRAM, and RZMBLR for genomic alignment and variation-analysis workflows.
Abstract
from arXiv · showhide
Summary: The Smith Waterman (SW) 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, but current implementations are either designed as monolithic protein database searching tools or are embedded into other tools. To facilitate easy integration of the fast Single Instruction Multiple Data (SIMD) SW algorithm into third party software, we wrote a C/C++ library, which extends Farrars Striped SW (SSW) to return alignment information in addition to the optimal SW score. Availability: SSW is available both as a C/C++ software library, as well as a stand alone alignment tool wrapping the librarys functionality at https://github.com/mengyao/Complete- Striped-Smith-Waterman-Library Contact: marth@bc.edu
1 INTRODUCTION
SW is widely used for sequence alignment within read-mapping and variation-detection tools, but existing implementations are difficult to integrate as standalone components. SSW addresses this gap with a fast, versatile C/C++ striped-SW library.
- SW is extensively used for seed extension and final alignment because it provides pairwise sequence alignment.
- SIMD-based acceleration is attractive because it is compatible with most modern x86 CPUs.
- Striped SW is much faster than standard SW, but its original implementation reports only the optimal score.
- Existing implementations also require specialized SSE2 and algorithmic expertise or are tightly embedded in larger projects.
- SSW was developed as a fast, versatile, standalone C/C++ library for pairwise alignment with striped SW.
2 ALGORITHM AND IMPLEMENTATION
SSW extends Farrar’s striped SW to recover alignment information while retaining SIMD efficiency. It records column maxima, identifies alignment positions, and uses reversed and banded SW for detailed traceback and suboptimal scoring.
- SSW accelerates Farrar’s implementation with the lazy F loop and adds access to optimal and secondary alignment information.
- The SIMD calculation records each column’s maximum score and the complete column containing the matrix-wide maximum.
- A reversed SIMD SW and a banded SW recover the detailed optimal alignment without substantially slowing the original calculation.
- In the illustrated matrix, the optimal alignment ends at score 9 and traces back to a start cell with score 2.
- An additional SSE2 command in the inner loop and another in the outer loop limit the time cost of generating the max array.
3 RESULTS
SSW provides a C/C++ API and executable for protein or genome alignment, returning optimal and suboptimal alignment information. Across benchmark settings, it remains as fast as Farrar’s accelerated implementation while supporting detailed alignments.
- 3.1 Usage: The SSW API returns the optimal SW score, alignment location, traceback, and the score and location of a suboptimal alignment.
- 3.1 Usage: SSW includes an executable tool for protein or DNA alignment and validation of alignments against very large reference genomes.
- 3.2 Performance: The benchmark compared SSW variants, Farrar’s accelerated SW, and SSEARCH using single-threaded runs on a 2GHz x86 64 AMD system.
- 3.2 Performance: The tests covered simulated 100 bp reads aligned to human reference regions from 1 Kb to 10 Mb and real reads aligned to four reference genomes.
- 3.2 Performance: SSW remained just as fast as Farrar’s accelerated version while returning a full optimal alignment and one suboptimal score.
4 APPLICATIONS
The library was evaluated as a component of four genomic applications, spanning primary mapping, split-read structural-variation analysis, and read-overlap graph generation. These applications use SSW where fast, detailed local alignment is needed.
- 4 APPLICATIONS: The authors demonstrate SSW as a component in four biologically meaningful applications.
- 4.1 Primary short read mapper: In MOSAIK’s final polishing step, SSW achieved a two-fold speedup over the existing banded SW implementation.
- 4.2 Secondary short-read mapper: Primary read mappers can fail to map or properly align reads in structural-variation regions such as deletions, insertions, inversions, and translocations.
- 4.2 Secondary short-read mapper: SCISSORS and TANGRAM use SSW to align orphaned or severely clipped mates across structural-variation breakpoints.
- 4.3 Read-overlap graph generation: For 22,543 reads, RZMBLR took 973.02 seconds with SSW versus 1795.66 seconds with ordinary SW.
5 CONCLUSION
SSW provides a fast SIMD-accelerated Smith-Waterman library that returns alignment results and integrates readily into C/C++ genomic software. Its adoption in four programs demonstrates practical utility.
- SSW returns optimal and secondary alignment information while accelerating SIMD Smith-Waterman integration into C/C++ genomic software.The library has been adopted in MOSAIK, SCISSORS, TANGRAM, and RZMBLR.