Adaptively banded Smith-Waterman algorithm for long reads and its hardware accelerator
Journal
IEEE International Conference on Application-specific Systems, Architectures and Processors
Date Issued
2018
Author(s)
Abstract
In this paper, we propose hardware-compatible Adaptively Banded Smith-Waterman algorithm (ABSW) to align long genomic sequences. By utilizing banded Smith-Waterman algorithm to align subsequences of fixed lengths, ABSW finds alignment of a pair of arbitrarily long sequences with constant memory. In addition, a heuristic algorithm, dynamic overlapping, is proposed to make overlaps of bands of subsequences to improve accuracy. To enable hardware acceleration of ABSW, we further propose the hardware architecture of banded Smith-Waterman with traceback. Experiments show that ABSW produces near optimal alignment scores for sequences with up to 40% error rates. Our hardware implementation of ABSW demonstrates more than 200× sneedun over software imnlementation. © 2018 IEEE.
Subjects
Banded Smith-Waterman; FPGA; Hardware accelerator; Long read alignment; Traceback using hardware
Other Subjects
Alignment; Field programmable gate arrays (FPGA); Heuristic algorithms; Memory architecture; Hardware acceleration; Hardware accelerators; Hardware architecture; Hardware implementations; Near-optimal alignments; Smith-Waterman; Smith-Waterman algorithm; Traceback; Hardware
Type
conference paper