Chapter 14 – GPU Accelerated RNA Folding Algorithm*

Publisher Summary This chapter presents an implementation of the main kernel in the widely used RNA folding package Unafold. Its key computation is a dynamic programming algorithm with complex dependency patterns, making it an a priori bad match for GPU computing. This study shows that reordering computations in such a way to enable tiled computations and good data reuse can significantly improve GPU performance and yields good speedup compared with optimized CPU implementation that also uses the same approach to tile and vectorize the code. RNA, or ribonucleic acid, is a single-stranded chain of nucleotide units. Because RNA is single stranded, it does not have the double-helix structure of DNA. Rather, all the base pairs of a sequence force the nucleotide chain to fold in “on itself” into a system of different recognizable domains like hairpin loops, bulges, interior loops, or stacked regions. This 2D space conformation of RNA sequences is called the secondary structure, and many bioinformatics studies require detailed knowledge of this. Algorithms computing this 2D folding runs in O(n3) complexity, which means computation time quickly becomes prohibitive when dealing with large datasets of long sequences. The goal is to write a GPU efficient algorithm with the same usage and results as the one in the Unafold implementation.