An FM-Index Based High-Throughput Memory-Efficient FPGA Accelerator for Paired-End Short-Read Mapping.

Area of Science:

• Bioinformatics
• Computer Engineering
• Genomics

Background:

• Accurate and efficient short-read mapping is crucial for genomic analysis.
• Existing methods often face computational bottlenecks, limiting throughput and increasing processing time.

Purpose of the Study:

• To develop a hardware accelerator for fast and efficient paired-end short-read mapping.
• To significantly reduce memory accesses and computational operations for improved performance.

Main Methods:

• Implementation of a Ferragina-Manzini index (FM-index) based hardware accelerator.
• Utilizing an interleaved data structure for enhanced data locality.
• Developing a lookup table for rapid retrieval of mapping location candidates.
• Incorporating conditional filtering and early termination strategies to optimize processing.

Main Results:

• Achieved a 92.6% reduction in computation time with only a 2% DRAM memory overhead.
• Demonstrated a 1.7-to-18.6× higher throughput compared to state-of-the-art FPGA designs.
• Processed over 1 billion short-reads with 99.3% accuracy on a Xilinx Alveo U250 FPGA.

Conclusions:

• The proposed FM-index based hardware accelerator offers a significant advancement in short-read mapping efficiency.
• The implemented techniques effectively reduce memory accesses and computational load.
• This accelerator provides a high-throughput and accurate solution for large-scale genomic data analysis.