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

Daniel Sundfeld; Jakob H. Havgaard; Jan Gorodkin; Alba C.M.A. De Melo

doi:10.1109/PDP.2017.15

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

Daniel Sundfeld, Jakob H. Havgaard, Jan Gorodkin, Alba C.M.A. De Melo

2 Citations (Scopus)

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.

Original language	English
Title of host publication	Proceedings : 2017 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017
Number of pages	8
Publisher	IEEE
Publication date	2017
Pages	295-302
Article number	7912663
ISBN (Electronic)	9781509060580
DOIs	https://doi.org/10.1109/PDP.2017.15
Publication status	Published - 2017
Event	25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017 - St. Petersburg, Russian Federation Duration: 6 Mar 2017 → 8 Mar 2017

Conference

Conference	25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017
Country/Territory	Russian Federation
City	St. Petersburg
Period	06/03/2017 → 08/03/2017

Keywords

CUDA
GPU
RNA
Sankoff Algorithm

Access to Document

10.1109/PDP.2017.15

Cite this

CUDA-Sankoff: Using GPU to Accelerate the Pairwise Structural RNA Alignment. / Sundfeld, Daniel; Havgaard, Jakob H.; Gorodkin, Jan et al.
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

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

@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",

}

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 -

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

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this