DNA/RNA Helix Selection Laboratory

StatusReady

Runs completed0 / 0

Evaluations—

Best primary—

Benchmark

Results appear after an experiment.

Current: —

Introduction and problem context

A nucleic-acid strand may form many candidate helices, but two candidates can reuse a nucleotide or create crossing pairs that a nested dot-bracket structure cannot represent. The core problem is therefore to select a mutually compatible subset of helices.

The lab now connects ViennaRNA as a physical evaluator: COIN, ROSE and the comparison algorithms still construct each structure, while ViennaRNA scores its dot-bracket phenotype using Turner nearest-neighbor free energy. The original pairing-energy proxy remains available for inexpensive screening and convergence comparisons. Turner evaluation is RNA-only and cached by dot-bracket so duplicate phenotypes are not rescored.

Representation

π = (h₇,h₂,h₉,…,h₁)
selected ← ∅
for h in π: accept h when conflict(h,selected)=0

Each candidate helix is a conflict-graph node; an edge denotes nucleotide overlap or a crossing interaction. The permutation is a priority order. Greedy decoding maps every permutation to a feasible subset without a binary chromosome or repair.

DNA permits AT/TA and GC/CG. RNA permits AU/UA, GC/CG and GU/UG wobble pairs. The selected pair table is exported as dot-bracket notation.

Problem formulation, objectives and fitness calculation

Let H be candidate helices, xₕ indicate selection, E contain conflict edges, and Pₕ denote the base pairs of helix h.

xₕ+xₖ ≤ 1 ∀(h,k)∈E
min fproxy = Σₕ xₕ proxyScore(h)
min fTurner = ΔGTurner(dot-bracket(x)) [kcal/mol] — RNA only
min funpaired = 1 − 2Σₕxₕ|Pₕ| / n
min fcount = Σₕxₕ
min fspan = (1/Σxₕ)Σₕxₕ(endₕ−startₕ)/n

Turner energy calls ViennaRNA fold_compound.eval_structure to score a structure proposed by the search algorithm; it does not ask ViennaRNA dynamic programming to construct the answer. The pairing proxy remains faster, while unpaired fraction rewards coverage, helix count discourages fragmentation, and span penalty favors local interactions. Selecting several axes exposes the multi-objectivization trade-offs.

Benchmark provenance and literature review

Permutation-based helix selection has a direct precedent in work by Wiese, Hendriks, Deschênes and colleagues, which decomposes RNA folding into selecting a subset of feasible helices using a permutation GA. Chen, Le and Maizel likewise build a master stem list and add compatible stems stepwise. bpRNA uses a maximum-weight independent subset to separate a nested structure from pseudoknot segments.

Relevant approaches include dynamic programming for nested RNA, maximum-weight independent set on conflict graphs, integer programming, branch-and-bound, GA/SA, ant colony, EDAs and Boltzmann-ensemble sampling. This lab does not replace ViennaRNA; it is a controlled test bed for studying how permutation-learning models learn priority relations among competing helices.

References

Wiese, K.C. et al. (2003). A permutation-based genetic algorithm for the RNA folding problem. Biosystems, 72, 29–41. DOI.

Chen, J.-H., Le, S.-Y. & Maizel, J.V. (2000). Prediction of common secondary structures of RNAs: a genetic algorithm approach. Nucleic Acids Research, 28(4), 991–999. DOI.

Danaee, P. et al. (2018). bpRNA: large-scale automated annotation and analysis of RNA secondary structure. NAR, 46(11), 5381–5394.

SantaLucia, J. (1998). A unified view of polymer, dumbbell, and oligonucleotide DNA nearest-neighbor thermodynamics. PNAS, 95, 1460–1465.