Fine-grained parallelism accelerating for RNA secondary structure prediction with pseudoknots based on FPGA

Area of Science:

• Bioinformatics
• Computational Biology
• Hardware Acceleration

Background:

• RNA secondary structure prediction is crucial for understanding gene function.
• The PKNOTS program, using 4D dynamic programming, is a standard but computationally intensive tool.
• Large gene databases exacerbate the computational and memory limitations of existing methods.

Purpose of the Study:

• To develop a fine-grained parallel PKNOTS package accelerated by FPGA.
• To overcome the computational and memory bottlenecks of traditional RNA folding algorithms.
• To present the first FPGA implementation for accelerating the 4D dynamic programming problem in RNA folding with pseudoknots.

Main Methods:

• Implementation of a fine-grained parallel PKNOTS package on an FPGA.
• Application of storage optimization strategies to address the 'Memory Wall' problem.
• Exploitation of parallel computing strategies and on-chip memory reduction techniques.

Main Results:

• Achieved an average speedup factor of over 50x compared to the software version on a multi-core CPU.
• Demonstrated significantly reduced power consumption, approximately 50% of general-purpose microprocessors.
• Successfully implemented the first FPGA acceleration for 4D dynamic programming in RNA folding, including pseudoknots.

Conclusions:

• FPGA acceleration offers a viable and efficient solution for computationally demanding RNA folding predictions.
• The developed system significantly enhances the performance and reduces the energy footprint of RNA structure analysis.
• This work paves the way for faster and more energy-efficient analysis of large-scale genomic data.