On realizing shapes in the theory of RNA neutral networks

Peter Clote, Leszek Ga̧sieniec, Roman Kolpakov, Evangelos Kranakis, Danny Krizanc

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


It is known (Reidys et al., 1997b. Bull. Math. Biol. 59(2), 339-397) that for any two secondary structures S,S′ there exists an RNA sequence compatible with both, and that this result does not extend to more than two secondary structures. Indeed, a simple formula for the number of RNA sequences compatible with secondary structures S,S′ plays a role in the algorithms of Flamm et al. (2001. RNA 7, 254-265) and of Abfalter et al. (2003. Proceedings of the German Conference on Bioinformatics, http://www.tbi.univie.ac.at/papers/ Abstracts/03-018.pdf) to design an RNA switch. Here we show that a natural extension of this problem is NP-complete. Unless P=NP, there is no polynomial time algorithm, which when given secondary structures S1,...,Sk, for k≥4, determines the least number of positions, such that after removal of all base pairs incident to these positions there exists an RNA nucleotide sequence compatible with the given secondary structures. We also consider a restricted version of this problem with a "fixed maximum" number of possible stars and show that it has a simple polynomial time solution.

Original languageEnglish (US)
Pages (from-to)216-227
Number of pages12
JournalJournal of Theoretical Biology
Issue number2
StatePublished - Sep 21 2005
Externally publishedYes


  • NP-completeness
  • Neutral network
  • Nussinov-Jacobson energy model
  • RNA conformational switch

ASJC Scopus subject areas

  • Statistics and Probability
  • Modeling and Simulation
  • Biochemistry, Genetics and Molecular Biology(all)
  • Immunology and Microbiology(all)
  • Agricultural and Biological Sciences(all)
  • Applied Mathematics


Dive into the research topics of 'On realizing shapes in the theory of RNA neutral networks'. Together they form a unique fingerprint.

Cite this