Automated design of dynamic programming schemes for RNA folding with pseudoknots

Area of Science:

• Computational Biology
• Bioinformatics
• RNA Structure Analysis

Background:

• RNA secondary structure prediction is typically solved using dynamic programming (DP).
• Predicting RNA structures with pseudoknots is computationally challenging (NP-hard) and often requires specialized, hand-crafted DP algorithms for specific structures.
• Existing methods for pseudoknot prediction are limited to restricted classes of RNA conformations.

Purpose of the Study:

• To generalize and automate the design of DP algorithms for RNA pseudoknot prediction.
• To develop a framework for automatically generating DP schemes that minimize algorithmic complexity for RNA folding.
• To handle a broader range of RNA conformations beyond context-free grammars.

Main Methods:

• Formalizing the problem of DP algorithm design for conformation classes using fatgraphs.
• Developing an algorithm based on tree-decomposition of representative structures to generate DP schemes.
• Demonstrating fixed-parameter tractability for pseudoknot prediction based on the treewidth of the fatgraph.

Main Results:

• The proposed method automatically generates DP algorithms with complexities comparable to hand-crafted algorithms for common pseudoknot classes.
• The framework achieves a time complexity of O(n^3) (or O(n^2) for simpler models), where n is the RNA length.
• The generated algorithms support general energy models, partition function computations, and partial folding.

Conclusions:

• Automated design of DP algorithms offers a powerful and flexible approach to RNA pseudoknot prediction.
• This method generalizes and simplifies the creation of efficient algorithms for complex RNA structures.
• The framework has the potential to advance algebraic dynamic programming beyond context-free structures.