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

Saad Sheikh 1, 2 Rolf Backofen 3 Yann Ponty 1, 2, *
* Auteur correspondant
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
Résumé : La prédiction du repliement, avec pseudonoeuds généraux, d'une séquence d'ARN de taille $n$ est équivalent à la recherche d'un couplage d'énergie libre minimale. Dans un modèle d'énergie simple, où chaque paire de base contribue indépendamment à l'énergie, ce problème peut être résolu en temps $\Theta(n^3)$ grâce à une variante d'un algorithme de couplage pondéré maximal. Cependant, le même problème a été démontré NP-difficile dans le modèle d'énergie dit des plus proches voisins. Dans ce travail, nous étudions les propriétés du problème sous un modèle d'empilements, constituant un modèle intermédiaire entre ceux d'appariement et des plus proches voisins. Nous démontrons tout d'abord que le repliement avec pseudo-noeuds de l'ARN reste NP-difficile dans de nombreuses valuations du modèle d'énergie. . Par ailleurs, nous montrons que ce problème est approximable, en proposant un algorithme polynomial garantissant une $1/5$-approximation. Ce résultat illustre une différence essentielle entre ce modèle et celui des plus proches voisins, pour lequel nous montrons qu'il ne peut être approché à aucun ratio positif par un algorithme en temps polynomial sauf si $N=NP$.
Type de document :
Communication dans un congrès
Juha Kärkkäinen and Jens Stoye. CPM - 23rd Annual Symposium on Combinatorial Pattern Matching - 2012, Jul 2012, Helsinki, Finland. Springer, 7354, pp.321--333, 2012, Combinatorial Pattern Matching. 〈10.1007/978-3-642-31265-6_26〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00670232
Contributeur : Yann Ponty <>
Soumis le : jeudi 15 novembre 2012 - 15:02:42
Dernière modification le : mercredi 14 novembre 2018 - 16:08:06
Document(s) archivé(s) le : samedi 16 février 2013 - 03:43:21

Fichiers

NPCompleteness-Stacking.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

323

Téléchargements de fichiers

175