Combinatorial RNA Design: Designability and Structure-Approximating Algorithm in Watson-Crick and Nussinov-Jacobson Energy Models

Jozef Haleš 1 Alice Héliou 2, 3 Ján Maňuch 4, 1 Yann Ponty 2 Ladislav Stacho 1
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, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : We consider the Combinatorial RNA Design problem, a minimal instance of RNA design where one must produce an RNA sequence that adopts a given secondary structure as its minimal free-energy structure. We consider two free-energy models where the contributions of base pairs are additive and independent: the purely combinatorial Watson-Crick model, which only allows equally-contributing A − U and C − G base pairs, and the real-valued Nussinov-Jacobson model, which associates arbitrary energies to A − U, C − G and G − U base pairs. We first provide a complete characterization of designable structures using restricted alphabets and, in the four-letter alphabet, provide a complete characterization for designable structures without unpaired bases. When unpaired bases are allowed, we characterize extensive classes of (non-)designable structures, and prove the closure of the set of designable structures under the stutter operation. Membership of a given structure to any of the classes can be tested in Θ(n) time, including the generation of a solution sequence for positive instances. Finally, we consider a structure-approximating relaxation of the design, and provide a Θ(n) algorithm which, given a structure S that avoids two trivially non-designable motifs, transforms S into a designable structure constructively by adding at most one base-pair to each of its stems.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2017, 79 (3), pp.835--856. 〈10.1007/s00453-016-0196-x〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01285499
Contributeur : Yann Ponty <>
Soumis le : lundi 1 août 2016 - 10:18:09
Dernière modification le : jeudi 10 mai 2018 - 02:06:58

Fichiers

CombinatorialRNADesign-Hales-M...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Jozef Haleš, Alice Héliou, Ján Maňuch, Yann Ponty, Ladislav Stacho. Combinatorial RNA Design: Designability and Structure-Approximating Algorithm in Watson-Crick and Nussinov-Jacobson Energy Models. Algorithmica, Springer Verlag, 2017, 79 (3), pp.835--856. 〈10.1007/s00453-016-0196-x〉. 〈hal-01285499v2〉

Partager

Métriques

Consultations de la notice

463

Téléchargements de fichiers

134