Parallelization of Dynamic Programming in Nussinov RNA Folding Algorithm on the CUDA GPU

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.