A parallel algorithm for fixed-length approximate string-matching with k-mismatches

Maxime Crochemore*, Costas S. Iliopoulos, Solon P. Pissis

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

This paper deals with the approximate string-matching problem with Hamming distance. The approximate string-matching with k-mismatches 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 ℓ, search for all the occurrences in t of all factors of x of length ℓ with k or fewer mismatches with a factor of t. We present a practical parallel algorithm of comparable simplicity that requires only O(nm[ℓ/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 ofmessage-passing parallelism model, and word-level parallelism for efficient approximate string-matching.

Original languageEnglish
Title of host publicationAlgorithms and Applications - Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday
EditorsTapio Elomaa, Heikki Mannila, Pekka Orponen
Pages92-101
Number of pages10
DOIs
Publication statusPublished - 28 Dec 2010
Externally publishedYes

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6060 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Approximate stringmatching
  • Parallel algorithms
  • String algorithms

Fingerprint Dive into the research topics of 'A parallel algorithm for fixed-length approximate string-matching with k-mismatches'. Together they form a unique fingerprint.

  • Cite this

    Crochemore, M., Iliopoulos, C. S., & Pissis, S. P. (2010). A parallel algorithm for fixed-length approximate string-matching with k-mismatches. In T. Elomaa, H. Mannila, & P. Orponen (Eds.), Algorithms and Applications - Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday (pp. 92-101). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6060 LNCS). https://doi.org/10.1007/978-3-642-12476-1_6