Parallelization of Dynamic Programming in Nussinov RNA Folding Algorithm on the CUDA GPU
Date Issued
2012
Author(s)
Stojanovski, Marina Zaharieva
DOI
10.1007/978-3-642-28664-3_26
Abstract
When an RNA primary sequence is folded back on itself, forming
complementary base-pairs, a form called RNA secondary structure is created.
The first solution for the RNA secondary structure prediction problem was the
Nussinov dynamic programming algorithm developed in 1978 which is still an
irreplaceable base that all other approaches rely on. In this work, the Nussinov
algorithm is analyzed but from the CUDA GPU programming perspective. The
algorithm is radically redesigned in order to utilize the highly parallel NUMA
architecture of the GPU. The implementation of the Nussinov algorithm on
CUDA architecture for NVidia GeForce 8500 GT graphic card results with sub-
stantial acceleration compared with the sequential executed algorithm.
complementary base-pairs, a form called RNA secondary structure is created.
The first solution for the RNA secondary structure prediction problem was the
Nussinov dynamic programming algorithm developed in 1978 which is still an
irreplaceable base that all other approaches rely on. In this work, the Nussinov
algorithm is analyzed but from the CUDA GPU programming perspective. The
algorithm is radically redesigned in order to utilize the highly parallel NUMA
architecture of the GPU. The implementation of the Nussinov algorithm on
CUDA architecture for NVidia GeForce 8500 GT graphic card results with sub-
stantial acceleration compared with the sequential executed algorithm.
File(s)![Thumbnail Image]()
Loading...
Name
RNA CameraReady.pdf
Size
815.35 KB
Format
Adobe PDF
Checksum
(MD5):63cc17bc3dd461abaa5de9f36211090d