Bit-Parallel Multiple Pattern Matching

Tuan Tu Tran 1, 2 Mathieu Giraud 1, 2, * Jean-Stéphane Varré 1, 2
* Corresponding author
2 BONSAI - Bioinformatics and Sequence Analysis
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : Text matching with errors is a regular task in computational biology. We present an extension of the bit-parallel Wu-Manber algorithm to combine several searches for a pattern into a collection of fixed-length words. We further present an OpenCL parallelization of a redundant index on massively parallel multicore processors, within a framework of searching for similarities with seed-based heuristics. We successfully implemented and ran our algorithms on GPU and multicore CPU. Some speedups obtained are more than 60x.
Document type :
Conference papers
Parallel Processing and Applied Mathematics / Parallel Biocomputing Conference (PPAM / PBC 11), 2011, Torun, Poland. 2011
Liste complète des métadonnées


https://hal.inria.fr/inria-00637227
Contributor : Mathieu Giraud <>
Submitted on : Monday, October 31, 2011 - 1:10:19 PM
Last modification on : Friday, January 8, 2016 - 1:07:18 AM
Document(s) archivé(s) le : Monday, December 5, 2016 - 3:26:34 AM

File

pbc11-tran.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00637227, version 1

Citation

Tuan Tu Tran, Mathieu Giraud, Jean-Stéphane Varré. Bit-Parallel Multiple Pattern Matching. Parallel Processing and Applied Mathematics / Parallel Biocomputing Conference (PPAM / PBC 11), 2011, Torun, Poland. 2011. <inria-00637227>

Share

Metrics

Record views

443

Document downloads

539