Combinatorial RNA Design: Designability and Structure-Approximating Algorithm

Jozef Haleš 1 Ján Maňuch 2, 1 Yann Ponty 3, 4, 1 Ladislav Stacho 1
4 AMIB - Algorithms and Models for Integrative Biology
CNRS - Centre National de la Recherche Scientifique : UMR8623, Polytechnique - X, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : In this work, we consider the Combinatorial RNA Design problem, a minimal instance of the RNA design problem which aims at finding a sequence that admits a given target as its unique base pair maximizing structure. We provide complete characterizations for the structures that can be designed using restricted alphabets. Under a classic four-letter alphabet, we provide a complete characterization of designable structures without unpaired bases. When unpaired bases are allowed, we provide partial characterizations for classes of designable/undesignable structures, and show that the class of designable structures is closed under the stutter operation. Membership of a given structure to any of the classes can be tested in linear time and, for positive instances, a solution can be found in linear time. Finally, we consider a structure-approximating version of the problem that allows to extend bands (helices) and, assuming that the input structure avoids two motifs, we provide a linear-time algorithm that produces a designable structure with at most twice more base pairs than the input structure.
Type de document :
Communication dans un congrès
Ferdinando Cicalese; Ely Porat. CPM - 26th Annual Symposium on Combinatorial Pattern Matching, Jun 2015, Ischia Island, Italy. LNCS, 2015, 〈http://www.cpm2015.di.unisa.it〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01115349
Contributeur : Yann Ponty <>
Soumis le : mardi 14 avril 2015 - 20:25:41
Dernière modification le : jeudi 11 janvier 2018 - 06:23:08
Document(s) archivé(s) le : mardi 18 avril 2017 - 19:42:27

Fichiers

RNADesign-CPM2015-Final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01115349, version 2
  • ARXIV : 1502.03201

Citation

Jozef Haleš, Ján Maňuch, Yann Ponty, Ladislav Stacho. Combinatorial RNA Design: Designability and Structure-Approximating Algorithm. Ferdinando Cicalese; Ely Porat. CPM - 26th Annual Symposium on Combinatorial Pattern Matching, Jun 2015, Ischia Island, Italy. LNCS, 2015, 〈http://www.cpm2015.di.unisa.it〉. 〈hal-01115349v2〉

Partager

Métriques

Consultations de la notice

416

Téléchargements de fichiers

132