Chen Y.-LChang B.-YCHIA-HSIANG YANGTZI-DAR CHIUEH2021-09-022021-09-02202110459219https://www.scopus.com/inward/record.uri?eid=2-s2.0-85099592935&doi=10.1109%2fTPDS.2021.3051011&partnerID=40&md5=e13e25e73e1a669de3e95d4fe022e7edhttps://scholars.lib.ntu.edu.tw/handle/123456789/580657The mapping of DNA subsequences to a known reference genome, referred to as 'short-read mapping', is essential for next-generation sequencing. Hundreds of millions of short reads need to be aligned to a tremendously long reference sequence, making short-read mapping very time consuming. In this article, a high-throughput hardware accelerator is proposed so as to accelerate this task. A Bloom filter-based candidate mapping location (CML) generator and a folded processing element (PE) array are proposed to address CML selection and the Smith-Waterman (SW) alignment algorithm, respectively. It is shown that the proposed CML generator reduces the required memory access by 40 percent by employing a down-sampling scheme when compared to the Ferragina-Manzini index (FM-index) solution. The proposed hierarchical Bloom filter (HBF) that includes optimized parameters achieves a 1.5×104 times acceleration over the conventional Bloom filter. The proposed memory re-allocation scheme further reduces the memory access time for the HBF by a factor of 256. The proposed folded PE array delivers a 1.2-to-3.2 times higher giga cell updates per second (GCUPS). The processing time can be further reduced by 53-to-72 percent by employing a fully pipelined PE array that allows for a tailored shift amount for seeding. The accelerator is realized on a Stratix V GX FPGA with 16GB external SDRAM. Operated at 200MHz, the proposed FPGA accelerator delivers a 2.1-to-11 times higher throughput with the highest 99 percent accuracy and 98 percent sensitivity compared to the state-of-the-art FPGA-based solutions. ? 1990-2012 IEEE.Acceleration; Data structures; Dynamic random access storage; Field programmable gate arrays (FPGA); Gene encoding; Mapping; Alignment algorithms; Conventional design; Hardware accelerators; Hierarchical bloom filters; Next-generation sequencing; Optimized parameter; Processing elements; Short-read mappings; Pipeline processing systemsjournal article10.1109/TPDS.2021.30510112-s2.0-85099592935