inria-00637227, version 1
Bit-Parallel Multiple Pattern Matching
Tuan Tu Tran a, 1, 2Mathieu Giraud
b, 1, 2Jean-Stéphane Varré
c, 1, 2
Parallel Processing and Applied Mathematics / Parallel Biocomputing Conference (PPAM / PBC 11) (2011)
Résumé : 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.
- a – INRIA
- b – CNRS
- c – Université des Sciences et Technologies de Lille - Lille I
- 1 : Laboratoire d'Informatique Fondamentale de Lille (LIFL)
- CNRS : UMR8022 – INRIA – IRCICA – Université Lille 1 - Sciences et Technologies
- 2 : BONSAI (INRIA Lille - Nord Europe)
- CNRS : UMR8022 – Université Lille 1 - Sciences et Technologies – INRIA
- Domaine : Informatique/Bio-informatique
Sciences du Vivant/Bio-Informatique, Biologie Systémique - Mots-clés : bit parallelism – pattern matching – sequence comparison – neighborhood indexing – GPU – OpenCL
- inria-00637227, version 1
- http://hal.inria.fr/inria-00637227
- oai:hal.inria.fr:inria-00637227
- Contributeur : Mathieu Giraud
- Soumis le : Lundi 31 Octobre 2011, 13:10:19
- Dernière modification le : Mercredi 2 Novembre 2011, 09:17:30
Documents associés
Exporter