Parallel Position Weight Matrices Algorithms

Mathieu Giraud 1, 2, * Jean-Stéphane Varré 1, 2
* Auteur correspondant
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.
Type de document :
Communication dans un congrès
International Symposium on Parallel and Distributed Computing (ISPDC 2009), Jul 2009, Lisboa, Portugal. pp.65-69, 2009, 〈10.1109/ISPDC.2009.31〉
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00438215
Contributeur : Mathieu Giraud <>
Soumis le : jeudi 3 décembre 2009 - 07:53:20
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 17 juin 2010 - 20:44:17

Fichier

ispdc09-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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, 2009, 〈10.1109/ISPDC.2009.31〉. 〈inria-00438215〉

Partager

Métriques

Consultations de la notice

229

Téléchargements de fichiers

150