Self-attraction Removal from Oritatami Systems - Descriptional Complexity of Formal Systems (DCFS 2017)
Conference Papers Year : 2017

Self-attraction Removal from Oritatami Systems

Yo-Sub Han
  • Function : Author
  • PersonId : 1024595
Hwee Kim
  • Function : Author
  • PersonId : 1024596
Trent A. Rogers
  • Function : Author
  • PersonId : 1024597
Shinnosuke Seki
  • Function : Author
  • PersonId : 1024598

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.
Fichier principal
Vignette du fichier
440206_1_En_13_Chapter.pdf (605.93 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-01657016 , version 1 (06-12-2017)

Licence

Identifiers

Cite

Yo-Sub Han, Hwee Kim, Trent A. Rogers, Shinnosuke Seki. Self-attraction Removal from Oritatami Systems. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. pp.164-176, ⟨10.1007/978-3-319-60252-3_13⟩. ⟨hal-01657016⟩
54 View
137 Download

Altmetric

Share

More