A Parallel Tiled and Sparsified Four-Russians Algorithm for Nussinov's RNA Folding

Area of Science:

• Computational Biology
• Bioinformatics
• Structural Biology

Background:

• Predicting ribonucleic acid (RNA) spatial structure is crucial for extensive research.
• The Nussinov-Jacobson algorithm provides a cubic-time solution for RNA secondary structure prediction.
• Existing research focuses on improving the efficiency of RNA structure prediction algorithms.

Purpose of the Study:

• To improve the computational efficiency of RNA secondary structure prediction.
• To leverage and combine existing speedup techniques for enhanced performance.
• To evaluate the performance gains of a novel approach in both sequential and parallel environments.

Main Methods:

• Building upon Frid and Gusfield's sparsification and Four-Russians paradigm.
• Incorporating Palkowski and Bielecki's tiling technique to restructure the Nussinov loop nest.
• Applying loop transformations to promote cache reuse and variable-grained parallelism.
• Empirical evaluation on multicore processors and graphics cards.

Main Results:

• Achieved significant speedups by applying tiling techniques to a doubly sped-up algorithm.
• Sequential speedups up to x3.26 relative to Palkowski's baseline.
• Parallel speedups up to x28.50 on 32 threads for a 30,000-nucleotide sequence.
• Massive parallel speedups reaching x44.37 on graphics cards.

Conclusions:

• The combined approach of loop restructuring and sparsification significantly outperforms existing methods.
• The proposed method offers substantial improvements in both sequential and parallel RNA structure prediction.
• This work demonstrates the potential of advanced computational techniques for accelerating biological structure prediction.