An FPGA Accelerator for Sequence-to-Graph Alignment with Affine Gap Penalties
Journal
Proceedings - 21st IEEE Biomedical Circuits and Systems, BioCAS 2025
Start Page
591
End Page
595
ISBN (of the container)
979-833157336-2
Date Issued
2026-01-14
Author(s)
Abstract
Sequence-to-sequence (S2S) alignment has long been a fundamental tool in bioinformatics for identifying similarities between query sequences and a linear reference genome. However, a single reference sequence cannot fully capture the genetic diversity across populations. To address this limitation, the concept of the reference genome graph has emerged, which represents genetic variations through a graph structure. This has led to the development of sequence-to-graph (S2G) alignment algorithms. This work presents a hardware accelerator for seed-and-extend S2G alignment, implemented on a Terasic FPGA running at 160 MHz. Our design adopts a software-hardware co-designed flow that includes graph indexing, read seeding, seed clustering, and alignment. We propose a novel forward update technique and incorporate the affine gap penalty model into the existing S2G Smith-Waterman algorithm, making this work the first S2G hardware accelerator to support affine gap penalties. Experiment results show that our design achieves up to 19.61 × speedup over VG and 24.53 × over GraphAligner on real human genome graphs, demonstrating its efficiency and suitability for long-read S2G alignment.
Event(s)
21st IEEE Biomedical Circuits and Systems, BioCAS 2025
Subjects
affine gap penalty
FPGA
hardware accelerator
sequence-to-graph alignment
Publisher
IEEE
Type
conference paper