Inverse folding is a classic instance of negative RNA design which consists in finding a sequence that uniquely folds into a target secondary structure with respect to energy minimization. A breakthrough result of Bonnet et al. shows that, even in simple base pairs-based (BP) models, the decision version of a mildly constrained version of inverse folding is NP-hard. In this work, we show that inverse folding can be solved in linear time for a large collection of targets, including every structure that contains no isolated BP and no isolated stack (or, equivalently, when all helices consist of <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13015_2025_278_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">$3^{+}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>3</mn> <mo>+</mo> </msup> </math></EquationSource> </InlineEquation> base pairs). For structures featuring shorter helices, our linear algorithm is no longer guaranteed to produce a solution, but still does so for a large proportion of instances. Our approach introduces a notion of modulo m-separability, generalizing a property pioneered by Hales et al. Separability is a sufficient condition for the existence of a solution to the inverse folding problem. We show that, for any input secondary structure of length n, a modulo m-separated sequence can be produced in time <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13015_2025_278_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="77" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal {O}(n\,m\, 2^m)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mspace width="0.166667em" /> <mi>m</mi> <mspace width="0.166667em" /> <msup> <mn>2</mn> <mi>m</mi> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> anytime such a sequence exists. Meanwhile, we show that any structure consisting of <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13015_2025_278_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">$3^{+}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>3</mn> <mo>+</mo> </msup> </math></EquationSource> </InlineEquation> base pairs is either trivially non-designable, or always admits a modulo-2 separated solution. Solution sequences can thus be produced in linear time, and even be uniformly generated within the set of modulo-2 separable sequences.

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

期刊论文
出版模式：

开放获取
发表日期：

2025年10月24日

查看全文

Théo Boury,
Samuel Gardelle,
Laurent Bulteau,
Yann Ponty

摘要

Inverse folding is a classic instance of negative RNA design which consists in finding a sequence that uniquely folds into a target secondary structure with respect to energy minimization. A breakthrough result of Bonnet et al. shows that, even in simple base pairs-based (BP) models, the decision version of a mildly constrained version of inverse folding is NP-hard. In this work, we show that inverse folding can be solved in linear time for a large collection of targets, including every structure that contains no isolated BP and no isolated stack (or, equivalently, when all helices consist of $3^{+}$ $3^{+}$ base pairs). For structures featuring shorter helices, our linear algorithm is no longer guaranteed to produce a solution, but still does so for a large proportion of instances. Our approach introduces a notion of modulo m-separability, generalizing a property pioneered by Hales et al. Separability is a sufficient condition for the existence of a solution to the inverse folding problem. We show that, for any input secondary structure of length n, a modulo m-separated sequence can be produced in time $\mathcal {O}(n\,m\, 2^m)$ $O (n m 2^{m})$ anytime such a sequence exists. Meanwhile, we show that any structure consisting of $3^{+}$ $3^{+}$ base pairs is either trivially non-designable, or always admits a modulo-2 separated solution. Solution sequences can thus be produced in linear time, and even be uniformly generated within the set of modulo-2 separable sequences.