Oct 18, 2011: Marina Zaharieva-Stojanovski: Parallelization of Dynamic Programming in Nussinov RNA Folding Algorithm on the CUDA GPU

October 18, 2011Parallelization of Dynamic Programming in Nussinov RNA Folding Algorithm on the CUDA GPU
Room: Zi 5126Marina Zaharieva-Stojanovski
12:30-13:30

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 substantial acceleration compared with the sequential executed algorithm.