A Hardware Accelerator for Long Sequence Alignment with the Bit-Vector Scoring Scheme and Divide-and-Conquer Traceback
Journal
BioCAS 2022 - IEEE Biomedical Circuits and Systems Conference: Intelligent Biomedical Systems for a Better Future, Proceedings
ISBN
9781665469173
Date Issued
2022-01-01
Author(s)
Abstract
Sequence alignment plays an important role in bioinformatics. In this paper, we propose an application-specific integrated circuit (ASIC) design for the pairwise sequence alignment using Levenshtein distance based on the Myers bit-vector algorithm. We also design an accelerator for the divide-and-conquer-based Hirschberg's algorithm to reduce memory usage, so that the on-chip traceback function can be supported. The hardware is implemented with TSMC 40 nm technology and the maximum input sequence size of the aligner is 10,240 × 5,242,880 bps. Our hardware accelerator can achieve 3,992 GCUPS, which speeds up the pairwise alignment by 147× when compared with the software counterpart for the sequences of 90% similarity.
Subjects
divide and conquer | dynamic programming | hardware acceleration | pair-wise alignment | traceback
Type
conference paper