支援仿射間隙罰分之基因序列對圖比對硬體加速器設計

Abstract

序列比對一直是生物資訊領域中的基礎工具，用於找出讀段與線性參考基因組之間的相似性。然而，單一的參考序列無法完整涵蓋不同族群間的遺傳多樣性。為了解決這個限制，參考基因組圖的概念應運而生，透過圖結構來表現遺傳變異，進而促成了序列對圖比對演算法的發展。 本研究提出一個用於種子與延伸啟發式序列對圖比對的硬體加速器，實作於現場可程式化邏輯閘陣列(FPGA)上並以160MHz運行。我們採用軟硬體協同設計的流程，包含基因組圖索引建構、讀段種子尋找、種子分群與序列對圖史密斯-沃特曼比對等步驟。我們提出一種創新的向前更新技巧，將仿射間隙罰分模型整合至現有的序列對圖史密斯-沃特曼演算法中，使本研究成為首個支援仿射間隙罰分的序列對圖比對硬體加速器。實驗結果顯示，我們的設計在真實的人類基因組圖上，相較於VG可達到最高19.60倍的加速效果，對GraphAligner則可達到最高24.53倍的加速，展現出其在長讀段序列對圖比對任務中的高效能與實用性。

Sequence alignment has long been a fundamental tool in bioinformatics for identifying similarities between read 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 alignment algorithms. This work presents a hardware accelerator for seed-and-extend sequence-to-graph 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 sequence-to-graph Smith-Waterman algorithm, making this work the first sequence-to-graph hardware accelerator to support affine gap penalties. Experiment results show that our design achieves up to 19.60× speedup over VG and 24.53× over GraphAligner on real human genome graphs, demonstrating its efficiency and suitability for long-read sequence-to-graph alignment.