Source-linked AI summary
Designing RNA Secondary Structures is Hard
Édouard Bonnet, Paweł Rzążewski, Florian Sikora
TL;DR
RNA Design asks whether sequences can be constructed to fold uniquely into target secondary structures, a central problem whose complexity remained open despite practical importance. The paper studies position-constrained design in the Watson-Crick model and proves RNA Design Extension NP-hard, suggesting comparable hardness for more realistic models. Its reduction uses structured gadgets and fixed four-base pairing rules.
Problem
The computational complexity of designing sequences that uniquely fold into target RNA secondary structures remained unknown despite the problem's importance in biology and software practice.
Method
The paper reduces E3-SAT to RNA Design Extension using variable and clause gadgets with nested arches and counting arguments to control rematchings.
Results
RNA Design Extension is NP-hard in the fixed Watson-Crick model, using the natural four-letter alphabet and pseudoknot-free structures.
Takeaways & Limitations
Position-specific nucleotide constraints are biologically coherent, and the result suggests hardness may extend to more realistic energy models.
Abstract
from arXiv · showhide
An RNA sequence is a word over an alphabet on four elements $\{A,C,G,U\}$ called bases. RNA sequences fold into secondary structures where some bases match one another while others remain unpaired. Pseudoknot-free secondary structures can be represented as well-parenthesized expressions with additional dots, where pairs of matching parentheses symbolize paired bases and dots, unpaired bases. The two fundamental problems in RNA algorithmic are to predict how sequences fold within some model of energy and to design sequences of bases which will fold into targeted secondary structures. Predicting how a given RNA sequence folds into a pseudoknot-free secondary structure is known to be solvable in cubic time since the eighties and in truly subcubic time by a recent result of Bringmann et al. (FOCS 2016). As a stark contrast, it is unknown whether or not designing a given RNA secondary structure is a tractable task; this has been raised as a challenging open question by Anne Condon (ICALP 2003). Because of its crucial importance in a number of fields such as pharmaceutical research and biochemistry, there are dozens of heuristics and software libraries dedicated to RNA secondary structure design. It is therefore rather surprising that the computational complexity of this central problem in bioinformatics has been unsettled for decades. In this paper we show that, in the simplest model of energy which is the Watson-Crick model the design of secondary structures is NP-complete if one adds natural constraints of the form: index $i$ of the sequence has to be labeled by base $b$. This negative result suggests that the same lower bound holds for more realistic models of energy. It is noteworthy that the additional constraints are by no means artificial: they are provided by all the RNA design pieces of software and they do correspond to the actual practice.
1 Introduction
RNA secondary-structure design seeks sequences that fold into a target structure, but unlike folding prediction, its computational complexity had remained unresolved. This paper proves hardness for a constrained version under the simple Watson-Crick energy model.
- RNA folding: RNA folds through base pairing into secondary structures that influence biological function.Pseudoknot-free structures use matched parentheses for pairs and dots for unpaired bases.
- RNA folding: RNA Folding is solvable in O(n^3) time and has deterministic and randomized truly subcubic algorithms.The reported runtimes are O(n^2.861) deterministic and O(n^2.825) randomized.
- RNA design: RNA Design asks whether a sequence can uniquely fold into a specified secondary structure, a problem whose complexity remained unknown for decades.The motivation includes applications in pharmaceutical research and biochemistry.
- RNA design: Position-specific nucleotide constraints are biologically coherent and supported by existing RNA-design methods.Such constraints can force key positions to contain specified bases associated with molecular function.
- Main result: RNA Design Extension is NP-hard in the Watson-Crick model, suggesting hardness for more realistic energy models.The reduction uses E3-SAT, variable and clause gadgets, and increasing-width arches to control undesired rematchings.
- Main result: The hardness result uses the natural four-letter alphabet, fixed pair-counting energy, and pseudoknot-free structures that resemble stem-loops.The authors suggest the reduction may adapt to other energy models and unconstrained design.
2 Preliminaries
The preliminaries formalize RNA sequences, secondary structures, compatibility, designs, and extensions using finite alphabets and well-parenthesized representations. They also introduce tree representations for structural analysis.
- Sequences and extensions: RNA bases are encoded as 1, 2, 3, and 4 for A, C, G, and U, with complementary pairs summing to 5.Partial sequences additionally use ? to denote unspecified positions.
- Secondary structures: A pseudoknot-free secondary structure is a word over (, ), and . whose parentheses form a well-parenthesized expression after dots are removed.Dots represent unpaired letters.
- Designs: A sequence is compatible with a structure when every matched structural pair contains complementary bases.Complementarity is defined by the pairs {1,4} and {2,3}.
- Designs: A design is a compatible sequence for which every other compatible structure has strictly more unpaired letters.Thus the target structure maximizes the number of base pairs under the Watson-Crick model.
- Designs: RNA Design Extension asks whether a partially labeled sequence can be completed into a design for a given structure.RNA Design is the special case with every position unspecified.
- Tree representation: A structure can be represented by a rooted tree whose nodes are matched pairs or unmatched letters, with nesting defining parent-child relations.The structure's degree is the maximum node degree after excluding unpaired neighbors from degree counts.
3 Hardness of RNA Design Extension
The paper proves that RNA Design Extension is NP-complete in the Watson-Crick model by reducing bounded-occurrence E3-SAT to gadget-based RNA design. The construction encodes assignments in variable gadgets and ensures unsatisfied clauses admit better structures, while satisfiable assignments yield designs.
- Hardness result: RNA Design Extension is NP-complete.Membership in NP follows by guessing an extension and checking design uniqueness with adapted dynamic programming.
- Reduction: The reduction starts from E3-SAT with each variable appearing at most four times and constructs an equivalent instance of length N = Θ(n^6).The source has n variables and m = Θ(n) clauses.
- Variable gadgets: Variable gadgets encode truth assignments by labeling all their unpaired dots with 2 for true or 3 for false.Mixing labels 2 and 3 would allow the dots to pair with each other and produce a better structure, so potential solutions must assign one label consistently.
- Clause gadgets: Clause gadgets use nested arches and literal gadgets so that a clause with three false literals can be improved by rematching previously unpaired bases.The construction interleaves variable and clause gadgets in a binary tree whose labeling itself is designed.
- Correctness: If the source formula is unsatisfiable, any corresponding assignment leaves an unsatisfied clause whose rematching creates more pairs than the target structure.The gain is 10(n+m) − 6(⌈log(n+m)⌉+1) > 0, so no design extension exists.
- Correctness: If the source formula is satisfiable, the corresponding extension is shown to be a design, and the reduction establishes satisfiability exactly when the RNA instance has a design extension.The proof also uses that a design induces designs in all subtrees.
4 Algorithmic results
The paper develops two exact algorithms for RNA Design Extension, pruning labelings that cannot yield a design and exploiting the structure's tree representation. Their running times are O*(1.7321^n) generally and 2^s · nO(1) when s elements are unlabeled, using polynomial space.
- First algorithm: The first algorithm improves the trivial O*(4^n)-time search by analyzing the input structure's tree representation.It discards labelings that cannot appear in any design before the final checking step.
- First algorithm: The pruning rules distinguish three child configurations: all paired, one paired with unpaired children, or only unpaired children.The corresponding cases constrain possible labels and remove branches that cannot extend to a design.
- Second algorithm: The second algorithm branches only over labelings of unlabeled elements, using the fact that a labeled matching pair determines the other endpoint's label.Its complexity is measured by s, the number of unlabeled elements, rather than the full structure length.
- Second algorithm: 2^s · nO(1) is the second algorithm's complexity using polynomial space, and Theorem 10 gives both bounds for RNA Design Extension.The procedure first labels the root's unlabeled children, then checks completed labelings in polynomial time and prunes nonextendable branches.