The SMEM Seeding Acceleration for DNA Sequence Alignment

Mau-Chung Chang, Yu Ting Chen, Jason Cong, Po-Tsang Huang, Chun Liang Kuo, Cody Hao Yu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

19 Scopus citations

Abstract

The advance of next-generation sequencing technology has dramatically reduced the cost of genome sequencing. However, processing and analyzing huge amounts of data collected from sequencers introduces significant computation challenges, these have become the bottleneck in many research and clinical applications. For such applications, read alignment is usually one of the most compute-intensive steps. Billions of reads generated from the sequencer need to be aligned to the long reference genome. Recent state-of-the-art software read aligners follow the seed-andextend model. In this paper we focus on accelerating the first seeding stage, which generates the seeds using the supermaximal exact match (SMEM) seeding algorithm. The two main challenges for accelerating this process are 1) how to process a huge number of short reads with high throughput, and 2) how to hide the frequent and long random memory access when we try to fetch the value of the reference genome. In this paper, we propose a scalable array-based architecture, which is composed by many processing engines (PEs) to process large amounts of data simultaneously for the demand of high throughput. Furthermore, we provide a tight software/hardware integration that realizes the proposed architecture on the Intel-Altera HARP system. With a 16-PE accelerator engine, we accelerate the SMEM algorithm by 4x, and the overall SMEM seeding stage by 26% when compared with 16-thread CPU execution. We further analyze the performance bottleneck of the design due to extensive DRAM accesses and discuss the possible improvements that are worthwhile to be explored in the future.

Original languageEnglish
Title of host publicationProceedings - 24th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages32-39
Number of pages8
ISBN (Electronic)9781509023561
DOIs
StatePublished - 16 Aug 2016
Event24th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2016 - Washington, United States
Duration: 1 May 20163 May 2016

Publication series

NameProceedings - 24th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2016

Conference

Conference24th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2016
CountryUnited States
CityWashington
Period1/05/163/05/16

Keywords

  • BWA-MEM
  • FPGA
  • Intel HARP
  • PE-array architecture
  • Supermaximal exact match
  • read alignment

Fingerprint Dive into the research topics of 'The SMEM Seeding Acceleration for DNA Sequence Alignment'. Together they form a unique fingerprint.

Cite this