@inproceedings{sheikh12:_impac_energ_model_compl_rna_foldin_pseud,
  author    = {Saad Sheikh and
               Rolf Backofen and
               Yann Ponty},
  title     = {Impact of the Energy Model on the Complexity of {RNA} Folding with
               Pseudoknots},
  booktitle = {Combinatorial Pattern Matching - 23rd Annual Symposium, {CPM} 2012,
               Helsinki, Finland, July 3-5, 2012. Proceedings},
  pages     = {321--333},
  year      = 2012,
  doi       = {10.1007/978-3-642-31265-6_26},
  timestamp = {Fri, 15 Jun 2012 12:22:52 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/cpm/SheikhBP12},
  bibsource = {dblp computer science bibliography, http://dblp.org},
  abstract={Predicting the folding of an RNA sequence, while allow-
ing 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 Θ(n3)-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ø, 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 Θ(n3) 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. },
  user =	 {backofen}
}