← All papers
First page of Designability of RNA Targets with Up to Two Length-2 Helices

Designability of RNA Targets with Up to Two Length-2 Helices

Ashutosh S. Jogalekar

q-bio.QM Aug 25, 2026 · v1 q-bio.BM
The main coloring and design theorems for RNA inverse-folding designability are formalized in Lean 4 against pinned Mathlib.
RNA inverse folding asks for an RNA sequence whose prescribed secondary structure is the unique maximum-base-pair compatible fold. In the four-letter Watson-Crick model (A-U and C-G pairs only, no pseudoknots, and zero minimum base-pair span), Hales et al. introduced a separated-coloring certificate and an even-odd device, while Boury et al. generalized this to modulo-$m$ separability, gave an $O(n 2^m)$ decision algorithm, and guaranteed designability when every helix has length at least 3. We prove that the guarantee still holds when a motif-free target has at most two maximal helices of length 2, no maximal helix of length 1, and all remaining helices of length at least 3. The proof builds on Boury et al.'s local helix-coloring transfers and adds a global counting argument showing that the demands created by at most two short helices can always be coordinated. This is a structural success guarantee for the existing modulo-2 algorithm, not a new general decision capability. The resulting coloring yields an explicit sequence whose every distinct compatible noncrossing fold has fewer pairs. No claim is made for nearest-neighbor thermodynamic energy models. The theorem and supporting lemmas are formalized in Lean 4 against pinned Mathlib and reproduced from a frozen public artifact; the kernel-reported axiom set is $\{\mathrm{propext},\mathrm{Classical.choice},\mathrm{Quot.sound}\}$. The work was developed with foundational generative-AI assistance under the author's direction and has not yet received independent human expert review.

RNA inverse folding seeks a nucleotide sequence whose target secondary structure is its unique maximum-base-pair compatible fold. Prior work guaranteed designability when all helices have length at least 3, leaving short-helix cases open in the four-letter Watson-Crick model.

The work extends Boury et al.'s modulo-2 separated-coloring framework to motif-free targets with at most two maximal helices of length 2. It combines local helix-coloring transfer lemmas with a global counting argument bounding demands from short helices, then constructs an explicit sequence and proves fold uniqueness. The main theorems and supporting lemmas are formalized in Lean 4 against pinned Mathlib, reproduced from a frozen public artifact.

Every target in the class K_{<=2} admits a proper modulo-2 separated coloring and is designable in the four-letter Watson-Crick model with theta=0. The Lean kernel reports the axiom set {propext, Classical.choice, Quot.sound}. A counterexample shows three isolated stacks can prevent modulo-2 separation.

entryexitvalid words
ξξBB, WW
ξηBG, WG
ηξGB, GW
ηηBB, WW, GG
Valid two-pair color words for a length-2 helix by entry/exit residue