CUDA-Sankoff: Using GPU to Accelerate the Pairwise Structural RNA Alignment

TY - GEN

T1 - CUDA-Sankoff

T2 - 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017

AU - Sundfeld, Daniel

AU - Havgaard, Jakob H.

AU - Gorodkin, Jan

AU - De Melo, Alba C.M.A.

PY - 2017

Y1 - 2017

N2 - In this paper, we propose and evaluate CUDASankoff, a solution to the RNA structural alignment problem based on the Sankoff algorithm in Graphics Processing Units (GPUS). To our knowledge, this is the first time the Sankoff algorithm is implemented in GPU. In our solution, we show how to linearize the Sankoff 4-dimensional dynamic programming (4D DP) matrix and we propose a two-level wavefront approach to exploit the parallelism. The results were obtained with two different NVidia GPUS, comparing sets of real RNA sequences with lengths from 46 to 281 nucleotides. We show that our GPU approach is up to 24 times faster than a 16-core CPU solution in the 281 nucleotide Sankoff execution.

AB - In this paper, we propose and evaluate CUDASankoff, a solution to the RNA structural alignment problem based on the Sankoff algorithm in Graphics Processing Units (GPUS). To our knowledge, this is the first time the Sankoff algorithm is implemented in GPU. In our solution, we show how to linearize the Sankoff 4-dimensional dynamic programming (4D DP) matrix and we propose a two-level wavefront approach to exploit the parallelism. The results were obtained with two different NVidia GPUS, comparing sets of real RNA sequences with lengths from 46 to 281 nucleotides. We show that our GPU approach is up to 24 times faster than a 16-core CPU solution in the 281 nucleotide Sankoff execution.

KW - CUDA

KW - GPU

KW - RNA

KW - Sankoff Algorithm

U2 - 10.1109/PDP.2017.15

DO - 10.1109/PDP.2017.15

M3 - Article in proceedings

AN - SCOPUS:85019629536

SP - 295

EP - 302

BT - Proceedings

PB - IEEE

Y2 - 6 March 2017 through 8 March 2017

ER -