Accelerating the Nussinov RNA folding algorithm with CUDA/GPU
Computer Engineering and Computer Science Department, University of Louisville, Louisville, KY 40292, USA
IEEE International Symposium on Signal Processing and Information Technology (ISSPIT), 2010
Graphics processing units (GPU) on commodity video cards have evolved into powerful computational devices. The RNA secondary structure arises from the primary structure and a backbone of canonical, Watson-Crick base pairings (A-U, C-G), and to a lesser extent, the G-U pairing. Early computational work by Nussinov formulated the problem of RNA secondary structure prediction as a maximization of the number of paired bases, which led to a simplified problem amenable to a dynamic programming solution for O(n^3) serial time. This article describes a GPU implementation of the Nussinov dynamic programming. Computation results show that the GPU implementation is up to 290 times faster than the CPU.
July 12, 2011 by hgpu
