Designing RNA Secondary Structures Is Hard
Authors:
Open Access
- 1 March 2020
- journal article
- research article
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 27 (3) , 302-316
Abstract
A ribonucleic acid (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 pair with one another, while others remain unpaired. The two fundamental problems in RNA algorithmic are to predict how sequences fold within some models of energy and to design sequences of bases that 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), whereas Lyngsø has shown it is computationally hard if pseudoknots are allowed (ICALP, 2004). 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 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 the 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 article, we show that in the simplest model of energy, which is the Watson–Crick model, the design of secondary structures is computationally hard 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 (e.g., the instances of the EteRNA project).Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- RNAiFold: a web server for RNA inverse folding and molecular designNucleic Acids Research, 2013
- De novo automated design of small RNA circuits for engineering synthetic riboregulation in living cellsProceedings of the National Academy of Sciences, 2012
- An O ( n 5 ) Algorithm for MFE Prediction of Kissing Hairpins and 4-Chains in Nucleic AcidsJournal of Computational Biology, 2009
- Novel and Efficient RNA Secondary Structure Prediction Using Hierarchical FoldingJournal of Computational Biology, 2008
- COMPUTER-BASED DESIGN OF NOVEL PROTEIN STRUCTURESAnnual Review of Biophysics, 2006
- A New Algorithm for RNA Secondary Structure DesignJournal of Molecular Biology, 2004
- Predicting RNA Secondary Structures with Arbitrary Pseudoknots by Maximizing the Number of Stacking PairsJournal of Computational Biology, 2003
- RNA Pseudoknot Prediction in Energy-Based ModelsJournal of Computational Biology, 2000
- A dynamic programming algorithm for RNA structure prediction including pseudoknots 1 1Edited by I. TinocoJournal of Molecular Biology, 1999
- Principles that Govern the Folding of Protein ChainsScience, 1973