RNA inverse folding can be solved in linear time for structures without isolated stacks or base pairs

Area of Science:

• Computational Biology
• Bioinformatics
• RNA Structure Prediction

Background:

• RNA inverse folding is a critical problem in negative RNA design, aiming to find sequences that fold into a specific structure.
• Previous research established the NP-hard nature of constrained inverse folding problems, posing significant computational challenges.
• Efficient algorithms are crucial for designing RNA molecules with desired functions.

Purpose of the Study:

• To develop a linear-time algorithm for solving the RNA inverse folding problem for a broad range of target structures.
• To introduce and generalize the concept of modulo m-separability for RNA secondary structures.
• To demonstrate that structures with helices of three or more base pairs can be efficiently designed.

Main Methods:

• Development of a novel algorithm based on the concept of modulo m-separability.
• Generalization of separability properties for RNA secondary structures.
• Analysis of algorithmic complexity for generating separable sequences.

Main Results:

• A linear-time algorithm is presented that solves inverse folding for structures without isolated base pairs or stacks (helices >= 3 base pairs).
• The algorithm efficiently produces modulo m-separated sequences in O(nm*2^m) time.
• Structures with helices of three or more base pairs are shown to admit a modulo-2 separated solution, solvable in linear time.

Conclusions:

• RNA inverse folding can be solved efficiently in linear time for many practical targets, particularly those with longer helices.
• The modulo m-separability framework provides a powerful tool for RNA design and analysis.
• This work significantly advances the capabilities of computational RNA design.