06104417

a

06104417 Tran, Tuan Tu Giraud, Mathieu Varr\'e, Jean-St\'ephane Bit-parallel multiple pattern matching. Wyrzykowski, Roman (ed.) et al., Parallel processing and applied mathematics. 9th international conference, PPAM 2011, Torun, Poland, September 11--14, 2011. Revised selected papers, Part II. Berlin: Springer (ISBN 978-3-642-31499-5/pbk). Lecture Notes in Computer Science 7204, 292-301 (2012). 2012 Berlin: Springer EN bit parallelism pattern matching sequence comparison neighborhood indexing GPU OpenCL

doi:10.1007/978-3-642-31500-8_30

Summary: Text matching with errors is a regular task in computational biology. We present an extension of the bit-parallel Wu-Manber algorithm [16] 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 $60\times $.