Related Experiment Video
Updated: Feb 21, 2026

Quantifying Intermembrane Distances with Serial Image Dilations
Published on: September 28, 2018
A parallel approximate string matching under Levenshtein distance on graphics processing units using warp-shuffle
ThienLuan Ho1, Seung-Rohk Oh1, HyunJin Kim1
1School of Electronics and Electrical Engineering, Dankook University, Yongin-si, Republic of Korea.
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.
Related Concept Videos
Parallel Processing
Sign Test for Matched Pairs
To conduct the sign test, we first calculate the differences in...
Linear Approximation in Time Domain
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length,...
Linear Approximation in Frequency Domain
In contrast, nonlinear systems do not inherently possess these properties. However, for small deviations around an operating point, a nonlinear system can often be approximated as linear....
Synthetic Disvision of Polynomials
Wilcoxon Signed-Ranks Test for Matched Pairs

