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

This article 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 64 MB 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 200 MHz. 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.