Bit-Parallel Multiple Pattern Matching

Tuan Tu Tran 1, 2 Mathieu Giraud 1, 2, * Jean-Stéphane Varré 1, 2
* Auteur correspondant
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.
Type de document :
Communication dans un congrès
Parallel Processing and Applied Mathematics / Parallel Biocomputing Conference (PPAM / PBC 11), 2011, Torun, Poland. 2011
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00637227
Contributeur : Mathieu Giraud <>
Soumis le : lundi 31 octobre 2011 - 13:10:19
Dernière modification le : jeudi 11 janvier 2018 - 06:23:37
Document(s) archivé(s) le : lundi 5 décembre 2016 - 03:26:34

Fichier

pbc11-tran.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

489

Téléchargements de fichiers

683