A Hardware Accelerator for Long Sequence Alignment with the Bit-Vector Scoring Scheme and Divide-and-Conquer Traceback

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.