Computing the probability of RNA hairpin and multiloop formation

Area of Science:

• Computational Biology
• Bioinformatics
• Structural Biology

Background:

• Predicting RNA secondary structures is crucial for understanding RNA function.
• Existing methods often rely on minimum free energy, which may not capture the full diversity of biologically relevant structures.
• Accurate computation of structural ensembles and their properties is needed.

Purpose of the Study:

• To introduce novel algorithms (RNAhairpin, RNAmloopNum, RNAmloopOrder, RNAmloopHP) for computing Boltzmann partition functions under global structural constraints.
• To enable sampling from low-energy RNA structural ensembles based on specific numbers of hairpins and multiloops.
• To apply these algorithms for improved RNA structure prediction and feature extraction for gene finding.

Main Methods:

• Development of four novel algorithms: RNAhairpin, RNAmloopNum, RNAmloopOrder, and RNAmloopHP.
• Computation of partition functions for specified numbers of hairpins and multiloops.
• Utilizing Fast Fourier Transform (FFT) to optimize computation time for certain algorithms.
• Application of algorithms to Rfam database families and development of machine learning classifiers.

Main Results:

• RNAhairpin and RNAmloopNum achieve improved time complexity using FFT (O(n^4)).
• Structures sampled using RNAmloopHP show higher accuracy than minimum free energy structures for Rfam families (e.g., 24% sensitivity improvement for tRNA).
• Probabilities of forming k hairpins or multiloops serve as effective features for RNA gene classification.
• Multiloop order provides less discriminatory power compared to hairpin and multiloop counts.

Conclusions:

• The developed algorithms provide efficient and accurate methods for analyzing RNA structural ensembles.
• Sampling-based structure prediction can outperform minimum free energy approaches for certain RNA families.
• Hairpin and multiloop formation probabilities are valuable features for noncoding RNA gene finders, especially when computed efficiently via FFT.