Exact learning of RNA energy parameters from structure.

Area of Science:

• Computational biology
• Bioinformatics
• Machine learning

Background:

• Accurate RNA energy models are crucial for predicting RNA secondary structures.
• Learning these parameters from experimental data is a key challenge in bioinformatics.
• Existing methods may struggle with large datasets or complex energy models.

Purpose of the Study:

• To derive a necessary and sufficient condition for the exact learnability of parameters in a linear RNA energy model.
• To develop practical methods for selecting training data that satisfies this learnability condition.
• To validate the learned parameters against experimental data and established models.

Main Methods:

• Derivation of a learnability condition based on convex hulls of translated Newton polytopes.
• Characterization of learned parameters as a convex cone of normal vectors.
• Demonstration of the NP-hard nature of finding maximal data subsets satisfying the condition.
• Application of a randomized greedy algorithm to select a suitable training subset from the RNA STRAND v2.0 database.

Main Results:

• A precise mathematical condition for parameter learnability was established.
• The problem of selecting a maximal learnable subset was shown to be NP-hard.
• A practical algorithm successfully identified a subset of RNA STRAND v2.0 data.
• Learned energy parameters for A-U, C-G, and G-U base pairs were obtained.

Conclusions:

• The derived condition provides a theoretical foundation for RNA energy parameter learning.
• The randomized greedy algorithm offers a practical approach to data selection for learnability.
• The learned parameters align with experimentally measured values and Turner parameters, validating the approach.