Skip to Main content Skip to Navigation
New interface
Conference papers

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.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Mathieu Giraud Connect in order to contact the contributor
Submitted on : Monday, October 31, 2011 - 1:10:19 PM
Last modification on : Thursday, January 20, 2022 - 4:13:05 PM
Long-term archiving on: : Monday, December 5, 2016 - 3:26:34 AM


Files produced by the author(s)


  • HAL Id : inria-00637227, version 1


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. ⟨inria-00637227⟩



Record views


Files downloads