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

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Standard

CUDA-Sankoff : Using GPU to Accelerate the Pairwise Structural RNA Alignment. / Sundfeld, Daniel; Havgaard, Jakob H.; Gorodkin, Jan; De Melo, Alba C.M.A.

Proceedings: 2017 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017. IEEE, 2017. p. 295-302 7912663.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Harvard

Sundfeld, D, Havgaard, JH, Gorodkin, J & De Melo, ACMA 2017, CUDA-Sankoff: Using GPU to Accelerate the Pairwise Structural RNA Alignment. in Proceedings: 2017 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017., 7912663, IEEE, pp. 295-302, 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017, St. Petersburg, Russian Federation, 06/03/2017. https://doi.org/10.1109/PDP.2017.15

APA

Sundfeld, D., Havgaard, J. H., Gorodkin, J., & De Melo, A. C. M. A. (2017). CUDA-Sankoff: Using GPU to Accelerate the Pairwise Structural RNA Alignment. In Proceedings: 2017 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017 (pp. 295-302). [7912663] IEEE. https://doi.org/10.1109/PDP.2017.15

Vancouver

Sundfeld D, Havgaard JH, Gorodkin J, De Melo ACMA. CUDA-Sankoff: Using GPU to Accelerate the Pairwise Structural RNA Alignment. In Proceedings: 2017 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017. IEEE. 2017. p. 295-302. 7912663 https://doi.org/10.1109/PDP.2017.15

Author

Sundfeld, Daniel ; Havgaard, Jakob H. ; Gorodkin, Jan ; De Melo, Alba C.M.A. / CUDA-Sankoff : Using GPU to Accelerate the Pairwise Structural RNA Alignment. Proceedings: 2017 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017. IEEE, 2017. pp. 295-302

Bibtex

@inproceedings{985033dbab3c4eb9a23cab437354e975,
title = "CUDA-Sankoff: Using GPU to Accelerate the Pairwise Structural RNA Alignment",
abstract = "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.",
keywords = "CUDA, GPU, RNA, Sankoff Algorithm",
author = "Daniel Sundfeld and Havgaard, {Jakob H.} and Jan Gorodkin and {De Melo}, {Alba C.M.A.}",
year = "2017",
doi = "10.1109/PDP.2017.15",
language = "English",
pages = "295--302",
booktitle = "Proceedings",
publisher = "IEEE",
note = "25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017 ; Conference date: 06-03-2017 Through 08-03-2017",

}

RIS

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 -

ID: 184388992