Bit-Parallel Multiple Pattern Matching

Tuan Tu Tran (1, 2) , Mathieu Giraud (1, 2) , Jean-Stéphane Varré (1, 2)

1 LIFL - Laboratoire d'Informatique Fondamentale de Lille
2 BONSAI - Bioinformatics and Sequence Analysis

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.

Mots clés: bit parallelism; pattern matching; sequence comparison; neighborhood indexing; GPU; OpenCL

Domaines: Bio-informatique [q-bio.QM]; Bio-Informatique, Biologie Systémique [q-bio.QM]

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⟩