Ruleset Optimization on Isomorphic Oritatami Systems

Area of Science:

• Computational biology
• Biophysics
• Bioinformatics

Background:

• RNA cotranscriptional folding is a key process where RNA folds during synthesis.
• The oritatami model (OM) simulates this phenomenon using abstract molecules and rules.
• Optimizing the ruleset size is crucial for efficient simulation.

Purpose of the Study:

• To investigate the optimization problem of reducing ruleset size in the oritatami model.
• To determine the computational complexity of finding the minimal ruleset.
• To develop efficient heuristic algorithms for ruleset reduction.

Main Methods:

• Proving the hardness of the minimal ruleset problem using theoretical computer science techniques.
• Developing and implementing two heuristic algorithms for ruleset size reduction.
• Analyzing the geometric and conformational stability of the resulting folded structures.

Main Results:

• The problem of finding the smallest ruleset for the oritatami model is computationally hard.
• Two novel heuristic algorithms were proposed and evaluated.
• These algorithms demonstrate efficient reduction in ruleset size while preserving terminal conformations.

Conclusions:

• The hardness of ruleset optimization is established, necessitating heuristic approaches.
• The proposed algorithms offer practical solutions for efficient RNA folding simulations.
• This work contributes to a better understanding and modeling of cotranscriptional RNA folding.