Multicore and GPU Algorithms for Nussinov RNA Folding

Area of Science:

• Computational Biology
• Bioinformatics
• Algorithm Development

Background:

• RNA folding is crucial for understanding gene regulation and function.
• Efficient algorithms are needed to handle the computational complexity of RNA folding predictions.

Purpose of the Study:

• To develop optimized algorithms for RNA folding using Nussinov's equations.
• To improve computational efficiency on modern hardware architectures.

Main Methods:

• Implemented cache-efficient algorithms for single-core processors.
• Developed multicore algorithms leveraging parallel processing capabilities.
• Designed GPU-accelerated algorithms for NVIDIA C2050.

Main Results:

• Cache-efficient algorithm achieved 1.6-3.0x speedup over naive code.
• Multicore algorithm yielded 7.5-14.0x speedup on a 6-core CPU.
• GPU algorithm was up to 1582x faster than naive code and 5.1-11.2x faster than prior GPU methods.

Conclusions:

• Optimized algorithms significantly enhance RNA folding computation speed.
• Cache-efficient, multicore, and GPU approaches offer substantial performance gains.
• These advancements facilitate larger-scale RNA structure predictions.