Skip to Main content Skip to Navigation
Book sections

A Parallel Algorithm for Fixed-Length Approximate String-Matching with k-mismatches

Abstract : This paper deals with the approximate string-matching problem with Hamming distance. The approximate string-matching with kmismatches problem is to find all locations at which a query of length m matches a factor of a text of length n with k or fewer mismatches. The approximate string-matching algorithms have both pleasing theoretical features, as well as direct applications, especially in computational biology. We consider a generalisation of this problem, the fixed-length approximate string-matching with k-mismatches problem: given a text t, a pattern x and an integer l, search for all the occurrences in t of all factors of x of length l with k or fewer mismatches with a factor of t. We present a practical parallel algorithm of comparable simplicity that requires only O(nm(l/w)/p) time, where w is the word size of the machine (e.g. 32 or 64 in practice) and p the number of processors. Thus the algorithm's performance is independent of k and the alphabet size |Σ|. The proposed parallel algorithm makes use of message-passing parallelism model, and word-level parallelism for efficient approximate string-matching.
Document type :
Book sections
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00741966
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 11:24:01 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Tuesday, May 14, 2013 - 4:00:05 AM

File

A_Parallel_Algorithm_for_Fixed...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00741966, version 1

Citation

Maxime Crochemore, Costas S. Iliopoulos, Solon P. Pissis. A Parallel Algorithm for Fixed-Length Approximate String-Matching with k-mismatches. Tapio Elomaa, Heikki Mannila, Pekka Orponen. Algorithms and Applications, Springer, pp.92-101, 2010, LNCS, 978-3-642-12475-4. ⟨hal-00741966⟩

Share

Metrics

Record views

296

Files downloads

475