# Impact Of The Energy Model On The Complexity Of RNA Folding With Pseudoknots

* Corresponding author
2 AMIB - Algorithms and Models for Integrative Biology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
Abstract : Predicting the folding of an RNA sequence, while allowing general pseudoknots (PK), consists in finding a minimal free-energy matching of its $n$ positions. Assuming independently contributing base-pairs, the problem can be solved in $\Theta(n^3)$-time using a variant of the maximal weighted matching. By contrast, the problem was previously proven NP-Hard in the more realistic nearest-neighbor energy model. In this work, we consider an intermediate model, called the stacking-pairs energy model. We extend a result by Lyngs\o, showing that RNA folding with PK is NP-Hard within a large class of parametrization for the model. We also show the approximability of the problem, by giving a practical $\Theta(n^3)$ algorithm that achieves at least a $5$-approximation for any parametrization of the stacking model. This contrasts nicely with the nearest-neighbor version of the problem, which we prove cannot be approximated within any positive ratio, unless $P=NP$.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [20 references]

https://hal.inria.fr/hal-00670232
Contributor : Yann Ponty Connect in order to contact the contributor
Submitted on : Thursday, November 15, 2012 - 3:02:42 PM
Last modification on : Thursday, July 8, 2021 - 3:49:26 AM
Long-term archiving on: : Saturday, February 16, 2013 - 3:43:21 AM

### Files

NPCompleteness-Stacking.pdf
Files produced by the author(s)

### Citation

Saad Sheikh, Rolf Backofen, Yann Ponty. Impact Of The Energy Model On The Complexity Of RNA Folding With Pseudoknots. CPM - 23rd Annual Symposium on Combinatorial Pattern Matching - 2012, Juha Kärkkäinen, Jul 2012, Helsinki, Finland. pp.321--333, ⟨10.1007/978-3-642-31265-6_26⟩. ⟨hal-00670232v3⟩

Record views