Title :

Bit-Parallel Multiple Pattern Matching

Author(s) :

Tran, Tuan Tu [Auteur]
Bioinformatics and Sequence Analysis [BONSAI]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Giraud, Mathieu [Auteur correspondant]
Bioinformatics and Sequence Analysis [BONSAI]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Varré, Jean-Stéphane [Auteur]
Bioinformatics and Sequence Analysis [BONSAI]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]

Conference title :

Parallel Processing and Applied Mathematics / Parallel Biocomputing Conference (PPAM / PBC 11)

City :

Torun

Country :

Pologne

Start date of the conference :

2011

Publication date :

2011

English keyword(s) :

bit parallelism
pattern matching
sequence comparison
neighborhood indexing
GPU
OpenCL

HAL domain(s) :

Informatique [cs]/Bio-informatique [q-bio.QM]
Sciences du Vivant [q-bio]/Bio-Informatique, Biologie Systémique [q-bio.QM]

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL