Accelerating the Nussinov RNA folding algorithm with CUDA/GPU

Dar-Jen Chang, C. J. Kimmer, Ming Ouyang

2010 · 31 citations · 5 references

Concepts

Abstract

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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> ) 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.

References

5