Skip to Main content Skip to Navigation
New interface
Conference papers

Parallel Position Weight Matrices Algorithms

Mathieu Giraud 1, 2, * Jean-Stéphane Varré 1, 2 
* Corresponding author
2 SEQUOIA - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : Position Weight Matrices (PWMs) are broadly used in computation biology. The basic problem, Scan, aims to find the occurrences of a given PWM in large sequences. A number of other PWMs tasks share a common subproblem, ScoreDistribution, that has been shown to be NP-hard. The existing algorithms rely on the enumeration on a large set of scores or words, and they are mostly not suitable for parallelization. We propose a new algorithm, BucketScoreDistribution, that is both very efficient and suitable for parallelization. We bound the error induced by this algorithm. We realized a GPU prototype for Scan and BucketScoreDistribution with the CUDA libraries, and report for the different problems speedups of 21x and 77x on a Nvidia GTX 280.
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : Mathieu Giraud Connect in order to contact the contributor
Submitted on : Thursday, December 3, 2009 - 7:53:20 AM
Last modification on : Friday, February 4, 2022 - 3:18:12 AM
Long-term archiving on: : Thursday, June 17, 2010 - 8:44:17 PM


Files produced by the author(s)




Mathieu Giraud, Jean-Stéphane Varré. Parallel Position Weight Matrices Algorithms. International Symposium on Parallel and Distributed Computing (ISPDC 2009), Jul 2009, Lisboa, Portugal. pp.65-69, ⟨10.1109/ISPDC.2009.31⟩. ⟨inria-00438215⟩



Record views


Files downloads