LinearFold: linear-time approximate RNA folding by 5'-to-3' dynamic programming and beam search

Area of Science:

• Computational biology
• Bioinformatics
• Genomics

Background:

• Predicting ribonucleic acid (RNA) secondary structure is crucial for various biological applications.
• Current dynamic programming algorithms for RNA folding have cubic time complexity, limiting their scalability for genome-wide analyses.

Purpose of the Study:

• To develop a novel, efficient algorithm for RNA secondary structure prediction.
• To achieve linear time and space complexity for RNA folding while maintaining high accuracy.

Main Methods:

• Introduced an alternative dynamic programming algorithm for RNA folding.
• Adapted techniques from incremental parsing for context-free grammars.
• Implemented a beam pruning heuristic for linear time and space efficiency.

Main Results:

• Achieved O(n) time and O(n) space complexity for RNA folding, a significant improvement over existing O(n^3) methods.
• The algorithm produces high-quality approximations of optimal RNA structures without imposing output constraints.
• Demonstrated superior accuracy compared to existing models, particularly for long RNA sequences (e.g., 16S and 23S Ribosomal RNAs) and long-range base pairs.

Conclusions:

• The novel linear-time RNA folding algorithm offers a scalable and accurate solution for large-scale genomic applications.
• This approach overcomes the limitations of traditional dynamic programming methods, enabling more comprehensive RNA structure analysis.
• The developed algorithm and its implementation (LinearFold) are publicly available for research use.