Nucleic acid sequence design via efficient ensemble defect optimization.

Area of Science:

• Computational Biology
• Bioinformatics
• Molecular Biology

Background:

• Designing nucleic acid sequences with specific secondary structures is crucial for synthetic biology and RNA-based therapeutics.
• Existing methods often face computational challenges in accurately predicting and designing sequences that achieve desired structures.
• The ensemble defect is a key metric for evaluating the accuracy of a designed nucleic acid sequence's structure.

Purpose of the Study:

• To present a novel algorithm for designing nucleic acid sequences that reliably fold into a target secondary structure at equilibrium.
• To formulate sequence design as an optimization problem focused on minimizing the ensemble defect.
• To achieve computational efficiency in the sequence design process.

Main Methods:

• The algorithm formulates sequence design as an optimization problem, aiming to reduce the ensemble defect below a user-defined threshold.
• A hierarchical approach using tree-decomposition evaluates candidate mutations at leaf nodes, employing defect-weighted mutation sampling.
• Reoptimization is performed on subtrees to eliminate structural defects arising from interactions between sequences.

Main Results:

• The algorithm successfully designs RNA sequences that satisfy a low ensemble defect (typically < N/100) for various target structures and sizes (N=100 to 3200).
• The hierarchical design approach demonstrates asymptotic optimality, with a time complexity of Ω(N^3), closely matching theoretical bounds.
• Empirical results confirm the algorithm's efficiency and the sharpness of its time complexity exponent.

Conclusions:

• The developed algorithm provides an efficient and accurate method for designing nucleic acid sequences with predictable secondary structures.
• The hierarchical optimization strategy effectively addresses computational complexity and design accuracy.
• This work advances the capabilities in *de novo* design of functional nucleic acid molecules.