Tiling Nussinov's RNA folding loop nest with a space-time approach.

Area of Science:

• Bioinformatics
• Computational Biology
• Computer Science

Background:

• RNA primary structure is a nucleotide sequence (AUGC).
• RNA secondary structure forms when segments fold and pair, minimizing energy.
• Predicting RNA secondary structure is computationally intensive and crucial for bioinformatics.

Purpose of the Study:

• To develop an efficient parallel algorithm for RNA secondary structure prediction.
• To enhance the performance of RNA folding using a space-time tiling approach.

Main Methods:

• Applied a space-time tiling strategy to Nussinov's algorithm for RNA folding.
• Generated parallel, cache-effective tiled code.

Main Results:

• The parallel tiled code significantly outperforms automatically generated and manually coded alternatives.
• The approach successfully tiles all three loops of Nussinov's recurrence, a feat not possible with standard techniques.
• Achieved super-linear speedup (up to 32 threads) and scalability (up to 8 threads).

Conclusions:

• The space-time tiling approach offers a scalable and efficient method for RNA folding.
• This technique surpasses traditional compiler optimizations and manual coding for RNA structure prediction.
• The generated code demonstrates excellent performance and scalability on parallel architectures.