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

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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mn>3</mml:mn> <mml:mo>+</mml:mo></mml:msup> </mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mspace></mml:mspace> <mml:mi>m</mml:mi> <mml:mspace></mml:mspace> <mml:msup><mml:mn>2</mml:mn> <mml:mi>m</mml:mi></mml:msup> <mml:mo>)</mml:mo></mml:mrow> </mml:math> anytime such a sequence exists. Meanwhile, we show that any structure consisting of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mn>3</mml:mn> <mml:mo>+</mml:mo></mml:msup> </mml:math> 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.