Self-attraction removal from oritatami systems

Yo Sub Han, Hwee Kim, Trent A. Rogers, Shinnosuke Seki

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationDescriptional Complexity of Formal Systems - 19th IFIP WG 1.02 International Conference, DCFS 2017, Proceedings
EditorsGiovanni Pighizzini, Cezar Campeanu
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783319602516
Publication statusPublished - 2017
Event19th International Conference of Descriptional Complexity of Formal Systems, DCFS 2017 - Milano, Italy
Duration: 2017 Jul 32017 Jul 5

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10316 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other19th International Conference of Descriptional Complexity of Formal Systems, DCFS 2017

Bibliographical note

Funding Information:
S. Seki—In part supported by JST Program to Disseminate Tenure Tracking System No. 6F36 and JSPS KAKENHI Grant-in-Aid for Young Scientists (A) No. 16H05854.

Funding Information:
Y.-S. Han—Supported by International Cooperation Program (2017K2A9A2A08000270) and Basic Science Research Program (2015R1D1A1A01060097) by NRF of Korea.

Funding Information:
Kim was supported by NRF (National Research Foundation of Korea) Grant funded by the Korean Government (NRF-2013-Global Ph.D. Fellowship Program).

Funding Information:
T.A. Rogers—This author’s research was supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1450079, and National Science Foundation grants CAREER-1553166 and CCF-1422152.

Publisher Copyright:
© IFIP International Federation for Information Processing 2017.

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Self-attraction removal from oritatami systems'. Together they form a unique fingerprint.

Cite this