Parallel Position Weight Matrices Algorithms
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)
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.
November 22, 2010 by hgpu
Your response
You must be logged in to post a comment.
