LinearPartition

LinearPartition approximates the RNA secondary structure partition function and computes base-pairing probabilities in linear time to enable analysis of long RNA sequences.

Key Features:

• Linear-time heuristic algorithm: Implements a linear-time heuristic to reduce runtime compared with cubic-time partition function algorithms.
• Partition function and base-pairing probabilities: Approximates the partition function and computes base-pairing probabilities for RNA secondary structures.
• LinearFold-inspired approach: Adopts ideas from the LinearFold algorithm that approximates minimum free energy (MFE) structure prediction in linear time.
• Performance versus existing tools: Reports substantial speedups relative to ViennaRNAfold and CONTRAfold, with an example of processing a 32,753-nt sequence in about 1.3 minutes (approximately 2.5 days faster than predecessors reported).
• Improved accuracy: Shows improved correlation of predicted base-pairing probabilities with ground-truth structures and improved downstream structure prediction for long RNAs.
• Long-distance base-pair prediction: Enhances prediction accuracy for long-distance base pairs separated by more than 500 nucleotides.
• Scalability to long RNAs: Demonstrated applicability to long RNA families such as 16S and 23S ribosomal RNAs.

Scientific Applications:

• Folding ensemble estimation: Estimating folding ensembles and structural probability distributions for RNA sequences.
• Secondary structure prediction for large RNAs: Enabling secondary-structure analyses for long RNAs including 16S and 23S rRNAs.
• Long-range interaction analysis: Improving detection and quantification of long-distance base pairs (>500 nt) within RNA molecules.
• Computational genomics and RNA research: Supporting computational biology and genomics studies that require rapid partition function and base-pairing probability approximations.

Methodology:

Uses a LinearFold-inspired linear-time heuristic to approximate the RNA secondary structure partition function and compute base-pairing probabilities.