Yi-Lun LiaoYu-Cheng LiNae-Chyun ChenYi-Chang LuYI-CHANG LU2019-10-312019-10-31201810636862https://scholars.lib.ntu.edu.tw/handle/123456789/429949https://www.scopus.com/inward/record.uri?eid=2-s2.0-85053476265&doi=10.1109%2fASAP.2018.8445105&partnerID=40&md5=616e92755add4d01dcc86b925fdce10dIn 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.Banded Smith-Waterman; FPGA; Hardware accelerator; Long read alignment; Traceback using hardwareAlignment; 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; Hardwareconference paper10.1109/asap.2018.84451052-s2.0-85053476265