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 metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/inria-00438215
Contributor : Mathieu Giraud <>
Submitted on : Thursday, December 3, 2009 - 7:53:20 AM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Thursday, June 17, 2010 - 8:44:17 PM

File

ispdc09-final.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

692

Files downloads

260