Rapid RNA Folding: Analysis and Acceleration of the Zuker Recurrence

Arpith C. Jacob, Jeremy D. Buhler, Roger D. Chamberlain
Dept. of Comput. Sci. & Eng., Washington Univ. in St. Louis, St. Louis, MO, USA
18th IEEE Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), 2010


   title={Rapid rna folding: Analysis and acceleration of the zuker recurrence},

   author={Jacob, A.C. and Buhler, J.D. and Chamberlain, R.D.},

   booktitle={2010 18th IEEE Annual International Symposium on Field-Programmable Custom Computing Machines},





Download Download (PDF)   View View   Source Source   



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 Lyngso 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 103x speedup over a single core of a 3 GHz Intel Core 2 Duo CPU. The accelerator is also 17x faster than a recent Zuker implementation on a Virtex 4 LX200-11 FPGA and 12x and 6x 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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: