A parallel approximate string matching under Levenshtein distance on graphics processing units using warp-shuffle operations

PLoS One. 2017 Oct 10;12(10):e0186251. doi: 10.1371/journal.pone.0186251. eCollection 2017.

Abstract

Approximate string matching with k-differences has a number of practical applications, ranging from pattern recognition to computational biology. This paper proposes an efficient memory-access algorithm for parallel approximate string matching with k-differences on Graphics Processing Units (GPUs). In the proposed algorithm, all threads in the same GPUs warp share data using warp-shuffle operation instead of accessing the shared memory. Moreover, we implement the proposed algorithm by exploiting the memory structure of GPUs to optimize its performance. Experiment results for real DNA packages revealed that the performance of the proposed algorithm and its implementation archived up to 122.64 and 1.53 times compared to that of sequential algorithm on CPU and previous parallel approximate string matching algorithm on GPUs, respectively.

MeSH terms

  • Algorithms*
  • Base Sequence
  • Computational Biology / methods*
  • Computer Graphics
  • DNA / analysis*
  • Software*

Substances

  • DNA

Grants and funding

This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education. (2017R1D1A1B03030348). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.