LinearFold

LinearFold predicts RNA secondary structures using a linear-time approximate dynamic programming approach to enable efficient analysis of long RNA sequences.

Key Features:

• Linear-Time Complexity: Operates in O(n) time and space, reducing the runtime complexity of conventional cubic-time RNA-folding algorithms to linear scale.
• Left-to-right Dynamic Programming: Implements a left-to-right (5'-to-3') dynamic programming algorithm inspired by incremental parsing techniques from computational linguistics.
• Beam Search Heuristic: Employs a beam pruning heuristic to approximate optimal secondary structures while maintaining linear runtime and space requirements.
• High-Quality Approximations: Produces high-quality approximate RNA secondary structures and shows superior accuracy on datasets with known structures, particularly for long-range base pairs (500+ nucleotides apart).
• Improved Predictions for Long Sequences: Demonstrates enhanced performance on long sequence families such as 16S and 23S Ribosomal RNAs.

Scientific Applications:

• Genome-wide RNA Structure Analysis: Facilitates rapid analysis of large RNA sequences for genome-scale studies.
• Gene Expression and Regulatory Mechanisms: Supports studies linking predicted RNA secondary structures to gene expression, regulatory mechanisms, and functional implications.
• Long-range Base-Pairing and Folding Dynamics: Enables analysis of complex RNA interactions and folding dynamics, including prediction of long-range base pairs (500+ nucleotides apart).

Methodology:

Implements a left-to-right (5'-to-3') dynamic programming algorithm inspired by incremental parsing combined with a beam pruning heuristic to perform approximate RNA secondary structure prediction in O(n) time and space.