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...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: