The closeness of a match is an important measure with a number of practical applications, including computational biology, signal processing and text retrieval. The approximate string matching (ASM) problem asks to find a substring of string Y of length n that is most similar to string X of length m. It is well-know that the ASM can be solved by dynamic programming technique by computing a table of size m×n. The main contribution of this work is to present a memory-access-efficient implementation for computing the ASM on a GPU. The proposed GPU implementation relies on warp shuffle instructions which are used to accelerate the communication between threads without resorting to shared memory access. Despite the fact that O(mn) memory access operations are necessary to access all elements of a table with size n×m, the proposed implementation performs only $O(rac{mn}{w})$ memory access operations, where w is the warp size. Experimental results carried out on a GeForce GTX 980 GPU show that the proposed implementation, called w-SCAN, provides speed-up of over two fold in computing the ASM as compared to another prominent alternative.

This paper proposes a circular bit-vector-mismatches (CBVM) algorithm for approximate circular string matching with k-mismatches. We develop the proposed CBVM algorithm based on the rotation feature of the circular pattern. By reusing the matching information of the previous substring, the next substring of the input string can be processed in parallel.

The Hierarchical Memory Machine (HMM) is a theoretical parallel computing model that captures the essence of computing on CUDA-enabled GPUs. The approximate string matching (ASM) for two strings X and Y of length m and n is a task to find a substring of Y most similar to X. The main contribution of this paper is to show an optimal parallel algorithm for the approximate string matching on the HMM and implement it on GeForce GTX 580 GPU. Our algorithm runs in $O({nover w}+{mnover dw}+{nLover p}+{mnlover p})$ time units on the HMM with p threads, d streaming processors, memory band width w, global memory access latency L, and shared memory access latency l. We also show that the lower bound of the computing time is $Omega({nover w}+{mnover dw}+{nLover p}+{mnlover p})$ time units. Thus, our algorithm for the approximate string matching is time optimal. Further, we implemented our algorithm on GeForce GTX 580 GPU and evaluated the performance. The experimental results show that the ASM of two strings of 1024 and 4M (=222) characters can be done in 419.6ms, while the sequential algorithm can compute it in 27720ms. Thus, our implementation on the GPU attains a speedup factor of 66.1 over the single CPU implementation.

Let {Xk}k=- be a stationary and ergodic information source, where each Xk takes values in a standard alphabet A with a distance function d: A A [0, ) defined on it. For each sample sequence X = (, x-1, x0, x1, ) and D > 0 let the approximate D-match recurrence time be defined by Rn (x, D) = min {m n: dn (Xn1, Xm+nm+1) D}, where Xji denotes the string xixi+1 xj and dn: An An [0, ) is a metric of An induced by d for each n. Let R (D) be the rate distortion function of the source {Xk}k=- relative to the fidelity criterion {dn}. Then it is shown that lim supn-1/n log Rn (X, D) R (D/2) a. s.

This paper presents an O(mn log n) time algorithm for an approximate string matching problem, in which a pattern string may contain variable length don't care characters. This problem is important for searching DNA sequences or amino acid sequences.