# Designing RNA Secondary Structures is Hard

arXiv: https://arxiv.org/abs/1710.11513 · HTML: https://mlsanity.com/paper/1710.11513/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Oct 2017.

## Built on by (most cited first, 15 of 15)

- [gRNAde: Geometric Deep Learning for 3D RNA inverse design](https://mlsanity.com/paper/2305.14749/) (2023)
- [Learning a Prior for Monte Carlo Search by Replaying Solutions to Combinatorial Problems](https://mlsanity.com/paper/2401.10431/) (2024)
- [End-to-End Simultaneous Learning of Single-particle Orientation and 3D Map Reconstruction from Cryo-electron Microscopy Data](https://mlsanity.com/paper/2107.02958/) (2021)
- [Scalable Deep Learning for RNA Secondary Structure Prediction](https://mlsanity.com/paper/2307.10073/) (2023)
- [Generalized Nested Rollout Policy Adaptation with Limited Repetitions](https://mlsanity.com/paper/2401.10420/) (2024)
- [Comprehensive benchmarking of large language models for RNA secondary structure prediction](https://mlsanity.com/paper/2410.16212/) (2024)
- [Orthogonal Matrix Retrieval with Spatial Consensus for 3D Unknown-View Tomography](https://mlsanity.com/paper/2207.02985/) (2022)
- [Messenger RNA Design via Expected Partition Function and Continuous Optimization](https://mlsanity.com/paper/2401.00037/) (2023)
- [Rethinking Performance Measures of RNA Secondary Structure Problems](https://mlsanity.com/paper/2401.05351/) (2023)
- [Designing RNAs with Language Models](https://mlsanity.com/paper/2602.12470/) (2026)
- [Factorization Machine with Quadratic-Optimization Annealing for RNA Inverse Folding and Evaluation of Binary-Integer Encoding and Nucleotide Assignment](https://mlsanity.com/paper/2602.16643/) (2026)
- [The Generation-Recognition Asymmetry: Six Dimensions of a Fundamental Divide in Formal Language Theory](https://mlsanity.com/paper/2603.10139/) (2026)
- [The Montparnasse Algorithm for RNA Design](https://mlsanity.com/paper/2606.07562/) (2026)
- [Sampling-based Continuous Optimization with Coupled Variables for RNA Design](https://mlsanity.com/paper/2412.08751/) (2024)
- [Eterna is Solved](https://mlsanity.com/paper/2505.02110/) (2025)

## Abstract (arXiv)

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.