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

Saad Sheikh 1, 2 Rolf Backofen 3 Yann Ponty 1, 2, *
* 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$.
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-00670232
Contributor : Yann Ponty <>
Submitted on : Thursday, November 15, 2012 - 3:02:42 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:29 PM
Long-term archiving on : Saturday, February 16, 2013 - 3:43:21 AM

Files

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

Identifiers

Collections

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⟩

Share

Metrics

Record views

351

Files downloads

306