Faster algorithms for RNA-folding using the Four-Russians method.

Area of Science:

• Computational Biology
• Bioinformatics
• Algorithm Analysis

Background:

• The Nussinov algorithm computes RNA secondary structure in O(n3) time.
• The Four-Russians method optimizes dynamic programming algorithms.
• Previous Four-Russians RNA folding algorithms had O(n3logn) complexity with interleaved preprocessing.

Purpose of the Study:

• To simplify and accelerate RNA folding algorithms.
• To improve upon existing Four-Russians RNA folding techniques.
• To develop efficient serial and parallel algorithms for RNA secondary structure prediction.

Main Methods:

• Introduced a "two-vector method" for RNA folding, performing preprocessing once before computation.
• Developed memoized variants solving subproblems on demand.
• Designed a parallel algorithm utilizing the two-vector approach for improved time complexity.
• Implemented the parallel algorithm on Graphics Processing Units (GPUs) using CUDA.

Main Results:

• The two-vector serial method is up to 20x faster than Nussinov and 3x faster than Frid-Gusfield.
• The parallel algorithm achieves O(n2logn) time complexity.
• GPU implementation shows significant speedups: 2.5 seconds for sequences up to 6000 bases.
• Optimized data structures for coalesced memory access on GPUs.

Conclusions:

• The simplified Four-Russians approach (two-vector method) offers substantial performance gains for RNA folding.
• The parallel GPU implementation provides a highly efficient solution for large RNA sequences.
• The developed algorithms and source code are valuable resources for RNA structure prediction research.