Rapid RNA folding: Analysis and acceleration of the Zuker recurrence

RNA folding is a compute-intensive task that lies at the core of search applications in bioinformatics such as RNAfold and UNAFold. In this work, we analyze the Zuker RNA folding algorithm, which is challenging to accelerate because it is resource intensive and has a large number of variable-length dependencies. We use a technique of Lyngsø to rewrite the recurrence in a form that makes polyhedral analysis more effective and use data pipelining and tiling to generate a hardware-friendly implementation. Compared to earlier work, processors in our array are more efficient and use fewer logic and memory resources. We implemented our array on a Xilinx Virtex 4 LX100- 12 FPGA and experimentally verified a 103× speedup over a single core of a 3 GHz Intel Core 2 Duo CPU. The accelerator is also 17× faster than a recent Zuker implementation on a Virtex 4 LX200-11 FPGA and 12× and 6× faster respectively than an Nvidia Tesla C870 and GTX280 GPU. We conclude with a number of lessons in using FPGAs to implement arrays after polyhedral analysis. We advocate using polyhedral analysis to accelerate other dynamic programming recurrences in computational biology.