A Memory-Efficient Accelerator for 128-Parallel Sequence-to-Graph Alignment in Variant-Enriched Regions

For decades, sequence-to-sequence alignment is a crucial tool in bioinformatics that identifies the similarity between a query and the reference genome sequence. Because one single reference sequence is insufficient to express the diversity of genes, the concept of the reference genome graph has been proposed, which utilizes a graph structure to represent genetic variations and has a better recording of biological information. As results, different sequence-to-graph alignment algorithms have been developed to address the new demand. Although there are several fast methods available, in the regions enriched with genetic variations, the non-heuristic Smith-Waterman method is still the main approach to guarantee finding the optimal solutions at the cost of lengthy processing time. To alleviate this issue, we design a memory-efficient hardware accelerator for variation-enriched sequence-to-graph alignment on an Intel Arria 10 FPGA. According to our experiment, the proposed 128-parallel accelerator operates at 200 MHz, and achieves more than 9X speed-ups when compared to the PaSGAL software for the MHC gene dataset in the human genome GRCh38.