memerna: Sparse RNA folding including coaxial stacking.

Area of Science:

• Computational Biology
• Bioinformatics
• Molecular Biology

Background:

• Accurate RNA secondary structure prediction is crucial in computational biology.
• Existing algorithms face challenges in efficiently handling complex RNA structures like coaxial stacking.

Purpose of the Study:

• To develop a faster and more accurate algorithm for RNA secondary structure prediction.
• To incorporate coaxial stacking and other structural features into RNA folding predictions.
• To introduce novel sparsification techniques for improved computational efficiency.

Main Methods:

• Modified Zuker-Stiegler algorithm incorporating coaxial stacking into the dynamic programming state.
• Introduction of 'replaceability' as a generalized sparsification condition, extending beyond the triangle inequality.
• Development of non-monotonic candidate lists for further algorithmic speedup.
• Implementation of the algorithm in the memerna software package.

Main Results:

• The memerna software demonstrates the fastest exact RNA folding performance among tested tools supporting coaxial stacking under the Turner 2004 model.
• The novel replaceability condition enables effective sparsification of coaxial stacking computations.
• A new notation for RNA secondary structures, including coaxial stacking, terminal mismatches, and dangles (CTDs), has been introduced.

Conclusions:

• The modified algorithm and sparsification techniques significantly enhance the speed of RNA secondary structure prediction.
• Memerna offers a state-of-the-art solution for accurate and efficient RNA folding, particularly for structures with coaxial stacking.
• The new CTD notation provides a more comprehensive representation of RNA secondary structures.