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

Maxime Crochemore; Costas S. Iliopoulos; Solon Pissis

doi:10.1007/978-3-642-12476-1_6

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

Maxime Crochemore, Costas S. Iliopoulos, Solon Pissis

Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

8 Citations (Scopus)

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 E, 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 inverted right perpendicularl/winverted left perpendicular/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 vertical bar Sigma vertical bar. The proposed parallel algorithm makes use of message-passing parallelism model, and word-level parallelism for efficient approximate string-matching.

Original language	English
Title of host publication	Algorithms and Applications
Subtitle of host publication	Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday
Editors	Tapio Elomaa, Heikki Mannila, Pekka Orponen
Place of Publication	Berlin
Publisher	Springer
Pages	92 - 101
Number of pages	10
Volume	N/A
Edition	N/A
ISBN (Print)	9783642124754
DOIs	https://doi.org/10.1007/978-3-642-12476-1_6
Publication status	Published - 2010
Event	Workshop on Algorithms and Applications Dedicated to Esko Ukkonen for his 60th Birthday - Helsinki, Finland Duration: 28 May 2010 → …

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg
Volume	6060
ISSN (Print)	0302-9743

Conference

Conference	Workshop on Algorithms and Applications Dedicated to Esko Ukkonen for his 60th Birthday
Country/Territory	Finland
City	Helsinki
Period	28/05/2010 → …

Access to Document

10.1007/978-3-642-12476-1_6

Cite this

Crochemore, M., Iliopoulos, C. S., & Pissis, S. (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 (N/A ed., Vol. N/A, pp. 92 - 101). (Lecture Notes in Computer Science; Vol. 6060). Springer. https://doi.org/10.1007/978-3-642-12476-1_6

Crochemore, Maxime ; Iliopoulos, Costas S. ; Pissis, Solon. / A Parallel Algorithm for Fixed-Length Approximate String-Matching with k-mismatches. Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday. editor / Tapio Elomaa ; Heikki Mannila ; Pekka Orponen. Vol. N/A N/A. ed. Berlin : Springer, 2010. pp. 92 - 101 (Lecture Notes in Computer Science).

@inbook{127dec6079a04a9f8cdb98ddd51d2e89,

title = "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 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 E, 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 inverted right perpendicularl/winverted left perpendicular/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 vertical bar Sigma vertical bar. The proposed parallel algorithm makes use of message-passing parallelism model, and word-level parallelism for efficient approximate string-matching.",

author = "Maxime Crochemore and Iliopoulos, {Costas S.} and Solon Pissis",

year = "2010",

doi = "10.1007/978-3-642-12476-1_6",

language = "English",

isbn = "9783642124754",

volume = "N/A",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "92 -- 101",

editor = "Tapio Elomaa and Heikki Mannila and Pekka Orponen",

booktitle = "Algorithms and Applications",

edition = "N/A",

note = "Workshop on Algorithms and Applications Dedicated to Esko Ukkonen for his 60th Birthday ; Conference date: 28-05-2010",

}

Crochemore, M , Iliopoulos, CS & Pissis, S 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. N/A edn, vol. N/A, Lecture Notes in Computer Science, vol. 6060, Springer, Berlin, pp. 92 - 101, Workshop on Algorithms and Applications Dedicated to Esko Ukkonen for his 60th Birthday, Helsinki, Finland, 28/05/2010. https://doi.org/10.1007/978-3-642-12476-1_6

A Parallel Algorithm for Fixed-Length Approximate String-Matching with k-mismatches. / Crochemore, Maxime ; Iliopoulos, Costas S.; Pissis, Solon.
Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday. ed. / Tapio Elomaa; Heikki Mannila; Pekka Orponen. Vol. N/A N/A. ed. Berlin: Springer, 2010. p. 92 - 101 (Lecture Notes in Computer Science; Vol. 6060).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

TY - CHAP

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

AU - Crochemore, Maxime

AU - Iliopoulos, Costas S.

AU - Pissis, Solon

PY - 2010

Y1 - 2010

N2 - 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 E, 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 inverted right perpendicularl/winverted left perpendicular/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 vertical bar Sigma vertical bar. The proposed parallel algorithm makes use of message-passing parallelism model, and word-level parallelism for efficient approximate string-matching.

AB - 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 E, 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 inverted right perpendicularl/winverted left perpendicular/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 vertical bar Sigma vertical bar. The proposed parallel algorithm makes use of message-passing parallelism model, and word-level parallelism for efficient approximate string-matching.

UR - http://www.scopus.com/inward/record.url?scp=78650438144&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-12476-1_6

DO - 10.1007/978-3-642-12476-1_6

M3 - Conference paper

SN - 9783642124754

VL - N/A

T3 - Lecture Notes in Computer Science

SP - 92

EP - 101

BT - Algorithms and Applications

A2 - Elomaa, Tapio

A2 - Mannila, Heikki

A2 - Orponen, Pekka

PB - Springer

CY - Berlin

T2 - Workshop on Algorithms and Applications Dedicated to Esko Ukkonen for his 60th Birthday

Y2 - 28 May 2010

ER -

Crochemore M , Iliopoulos CS , Pissis S. A Parallel Algorithm for Fixed-Length Approximate String-Matching with k-mismatches. In Elomaa T, Mannila H, Orponen P, editors, Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday. N/A ed. Vol. N/A. Berlin: Springer. 2010. p. 92 - 101. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-12476-1_6

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this