Paper Info
Title
Parallel Position Weight Matrices algorithms
Abstract
Position Weight Matrices (PWMs) are broadly used in computational biology. The basic problems, Scan and MultipleScan, 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, MultipleScan and BucketScoreDistribution with the CUDA libraries, and report for the different problems speedups larger than 10x on several Nvidia cards.
Year
DOI
Venue
2009
10.1016/j.parco.2010.10.001
Parallel Computing
Keywords
Field
DocType
large set,basic problem,pwm task,new algorithm,nvidia card,position weight matrices,pattern matching,p -value estimation,existing algorithm,common np-hard subproblem,parallel position weight matrices,score distribution,bioinformatics,gpu,many-core architectures,cuda library,gpu prototype,computational biology
CUDA,Computer science,Matrix (mathematics),Enumeration,Parallel computing,Pulse-width modulation,Algorithm,Theoretical computer science,Pattern matching
Conference
Volume
Issue
ISSN
37
8
Parallel Computing
ISBN
Citations 
PageRank 
978-0-7695-3680-4
3
0.45
References 
Authors
33
2
Name
Order
Citations
PageRank
Mathieu Giraud112415.28
Jean-Stéphane Varré212518.73