Self-attraction Removal from Oritatami Systems

Abstract : RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized (transcribed). Oritatami is a computational model of this phenomenon, which lets its transcript, a sequence of beads (abstract molecules) fold cotranscriptionally via interactions between beads according to its ruleset. In this paper, we study the problem of removing self-attractions, which lets a bead interact with another bead of the same kind, from a given oritatami system without changing its behavior. We provide an algorithm for that with overhead linear in the delay parameter, which should be considerably smaller than the length of its transcript. We also show that this overhead is tight.
Type de document :
Communication dans un congrès
Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.164-176, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_13〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01657016
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 décembre 2017 - 11:44:44
Dernière modification le : mercredi 6 décembre 2017 - 13:46:15

Fichier

 Accès restreint
Fichier visible le : 2020-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Yo-Sub Han, Hwee Kim, Trent Rogers, Shinnosuke Seki. Self-attraction Removal from Oritatami Systems. Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.164-176, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_13〉. 〈hal-01657016〉

Partager

Métriques

Consultations de la notice

25