An FM-index Based High-Throughput Memory-Efficient FPGA Accelerator for Paired-end Short-read Mapping

Chung Hsuan Yang, Yi Chung Wu, Yen Lung Chen, Chao Hsi Lee, Jui Hung Hung, Chia Hsiang Yang

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

This paper presents an Ferragina-Manzini index (FM-index) based paired-end short-read mapping hardware accelerator. Four techniques are proposed to significantly reduce the number of memory accesses and operations to improve the throughput. First, an interleaved data structure is proposed to reduce the processing time by 51.8% by leveraging the data locality. Second, the boundaries of possible mapping location candidates can be retrieved within only one memory access by constructing a lookup table along with the FM-index. This reduces the number of DRAM accesses by 60% with only a 64MB memory overhead. Third, an additional step is added to skip the time-consuming repetitive location candidates filtering conditionally, avoiding unnecessary operations. Lastly, an early termination method is proposed to terminate the mapping process if any location candidate with a high enough alignment score is detected, greatly decreasing the execution time. Overall, the computation time is reduced by 92.6% with only a 2% memory overhead in DRAM. The proposed methods are realized on a Xilinx Alveo U250 FPGA. The proposed FPGA accelerator processes 1,085,812,766 short-reads from the U.S. Food and Drug Administration (FDA) dataset within 35.4 minutes at 200MHz. It achieves a 1.7-to-18.6× higher throughput and the highest 99.3% accuracy by exploiting the paired-end short-read mapping, compared to state-of-the-art FPGA-based designs.

Original languageEnglish
Pages (from-to)1-11
Number of pages11
JournalIEEE Transactions on Biomedical Circuits and Systems
DOIs
StateAccepted/In press - 2023

Keywords

  • Bioinformatics
  • Field programmable gate arrays
  • FM-index
  • FPGA accelerator
  • Genomics
  • Heuristic algorithms
  • Indexes
  • memory-efficient architecture
  • Next-generation sequencing (NGS)
  • Sequential analysis
  • short-read mapping
  • Throughput

Fingerprint

Dive into the research topics of 'An FM-index Based High-Throughput Memory-Efficient FPGA Accelerator for Paired-end Short-read Mapping'. Together they form a unique fingerprint.

Cite this