Efficient GPU Acceleration for Computing Maximal Exact Matches in Long DNA Reads

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

3 Downloads (Pure)

Abstract

The seeding heuristic is widely used in many DNA analysis applications to speed up the analysis time. In many applications, seeding takes a substantial amount of the total execution time. In this paper, we present an efficient GPU implementation for computing maximal exact matching (MEM) seeds in long DNA reads. We applied various optimizations to reduce the number of GPU global memory accesses and to avoid redundant computation. Our implementation also extracts maximum parallelism from the MEM computation tasks. We tested our implementation using data from the state-of-the-art third generation Pacbio DNA sequencers, which produces DNA reads that are tens of kilobases long. Our implementation is up to 9x faster for computing MEM seeds as compared to the fastest CPU implementation running on a server-grade machine with 24 threads. Computing suffix array intervals (first part of MEM computation) is up to 3x faster whereas calculating the location of the match (second part) is up to 9x faster. The implementation is publicly available at https://github.com/nahmedraja/GPUseed.

Original languageEnglish
Title of host publicationICBBB 2020
Subtitle of host publicationProceedings of 2020 10th International Conference on Bioscience, Biochemistry and Bioinformatics
Place of PublicationNew York
PublisherAssociation for Computing Machinery (ACM)
Pages28-34
Number of pages7
ISBN (Electronic)978-1-4503-7676-1
DOIs
Publication statusPublished - 2020
Event10th International Conference on Bioscience, Biochemistry and Bioinformatics, ICBBB 2020 - Kyoto, Japan
Duration: 19 Jan 202022 Jan 2020

Conference

Conference10th International Conference on Bioscience, Biochemistry and Bioinformatics, ICBBB 2020
CountryJapan
CityKyoto
Period19/01/2022/01/20

Keywords

  • DNA analysis
  • GPU
  • maximal exact matches
  • seeding

Fingerprint Dive into the research topics of 'Efficient GPU Acceleration for Computing Maximal Exact Matches in Long DNA Reads'. Together they form a unique fingerprint.

  • Cite this

    Ahmed, N., Bertels, K., & Al-Ars, Z. (2020). Efficient GPU Acceleration for Computing Maximal Exact Matches in Long DNA Reads. In ICBBB 2020 : Proceedings of 2020 10th International Conference on Bioscience, Biochemistry and Bioinformatics (pp. 28-34). Association for Computing Machinery (ACM). https://doi.org/10.1145/3386052.3386066