Parallel Position Weight Matrices Algorithms

Mathieu Giraud, Jean-Stephane Varre
LIFL, UMR CNRS 8022, Universite Lille 1, INRIA Lille-Nord Europe, Lille, France
International Symposium on Parallel and Distributed Computing (ISPDC 2009) (2009) 65-69, Parallel Computing (26 October 2010)


   title={Parallel position weight matrices algorithms},

   author={Giraud, M. and Varre, J.S.},

   booktitle={Parallel and Distributed Computing, 2009. ISPDC’09. Eighth International Symposium on},





Position Weight Matrices (PWMs) are broadly used in computational biology. The basic problems, Scan and Multiscan, aim to find all the occurrences of a given PWM or a set of PWMs in long sequences. Some other PWM tasks share a common NP-hard subproblem, ScoreDistribution 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, multiscan and BucketScoreDistribution with the CUDA libraries, and report for the different problems speedups larger than 10x on several Nvidia cards.
No votes yet.
Please wait...

Recent source codes

* * *

* * *

HGPU group © 2010-2018 hgpu.org

All rights belong to the respective authors

Contact us: