Sparse RNA folding revisited: space-efficient minimum free energy structure prediction.

Area of Science:

• Computational Biology
• Bioinformatics
• Molecular Biology

Background:

• RNA secondary structure prediction is crucial for analyzing non-coding RNAs.
• Existing methods prioritize time efficiency, but space efficiency is critical for long RNA sequences.
• Previous space-efficient methods lacked fold reconstruction capabilities for complex energy models.

Purpose of the Study:

• To develop a space-efficient algorithm for RNA secondary structure prediction with fold reconstruction.
• To address the limitations of existing sparsification techniques in terms of memory usage.
• To enable accurate Minimum Free Energy (MFE) structure prediction for extended RNA molecules.

Main Methods:

• Developed SparseMFEFold, a time- and space-efficient sparsified free energy minimization algorithm.
• Implemented dynamic garbage collection for trace arrows to facilitate efficient fold reconstruction.
• Analyzed algorithmic complexity in relation to candidate (Z) and trace arrow (T) counts.

Main Results:

• SparseMFEFold achieves MFE structure prediction with efficient fold reconstruction.
• Demonstrated significant space complexity reduction from O(n^2) to O(n log n).
• Empirical results show over 80% space savings on long RNAs (≥2500 bases) compared to RNAfold.

Conclusions:

• The SparseMFEFold technique is generalizable to more complex RNA prediction algorithms, including pseudoknot and RNA-RNA interaction prediction.
• The algorithm offers substantial memory savings, particularly beneficial for computationally intensive tasks.
• SparseMFEFold is available as free software, promoting wider adoption in RNA research.