Shifted Hamming distance: a fast and accurate SIMD-friendly filter to accelerate alignment verification in read mapping
📜 Abstract
Motivation: Calculating the edit-distance (i.e. minimum number of insertions, deletions and substitutions) between short DNA sequences is the primary task performed by seed-and-extend based mappers, which compare billions of sequences. In practice, only sequence pairs with a small edit-distance provide useful scientific data. However, the majority of sequence pairs analyzed by seed-and-extend based mappers differ by significantly more errors than what is typically allowed. Such error-abundant sequence pairs needlessly waste resources and severely hinder the performance of read mappers. Therefore, it is crucial to develop a fast and accurate filter that can rapidly and efficiently detect error-abundant string pairs and remove them from consideration before more computationally expensive methods are used. Results: We present a simple and efficient algorithm, Shifted Hamming Distance (SHD), which accelerates the alignment verification procedure in read mapping, by quickly filtering out error-abundant sequence pairs using bit-parallel and SIMD-parallel operations. SHD only filters string pairs that contain more errors than a user-defined threshold, making it fully comprehensive. It also maintains high accuracy with moderate error threshold (up to 5% of the string length) while achieving a 3-fold speedup over the best previous algorithm (Gene Myers’s bit-vector algorithm). SHD is compatible with all mappers that perform sequence alignment for verification. Availability and implementation: We provide an implementation of SHD in C with Intel SSE instructions at: https://github.com/CMU-SAFARI/SHD. Contact: hxin@cmu.edu, calkan@cs.bilkent.edu.tr or onur@cmu.edu Supplementary information: Supplementary data are available at Bioinformatics online.
✨ Summary
The paper introduced Shifted Hamming Distance (SHD), a SIMD- and bit-parallel pre-alignment filter intended to remove high-error read–reference pairs before expensive edit-distance computation. The authors reported that SHD preserves correct mappings, achieves approximately threefold speedup over the compared bit-vector implementation, and is compatible with seed-and-extend mappers. The implementation was released as open-source software. (pmc.ncbi.nlm.nih.gov)
Subsequent research directly evaluated and extended the approach. MAGNET analyzed sources of SHD’s filtering inaccuracy and proposed a new pre-alignment filter designed to improve accuracy across edit-distance thresholds and datasets, reporting one- to two-order-of-magnitude improvements in filtering accuracy. (arxiv.org) GateKeeper further developed hardware-based pre-alignment filtering for short-read mapping and compared its performance with SHD, reporting substantially higher acceleration on FPGA hardware. (arxiv.org) Later work also explored specialized hardware using shifted Hamming distance, including ShiftCAM for genome analysis. (researchr.org) These citations indicate that SHD influenced subsequent algorithmic and hardware research on pre-alignment filtering, while the available evidence does not establish broad standalone industry adoption.