Transcript design problem of oritatami systems

Yo Sub Han, Hwee Kim, Shinnosuke Seki

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

1 Citation (Scopus)


RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized out of a gene. Oritatami model is a computation model of this phenomenon, which lets its sequence (transcript) of beads (abstract molecules) fold cotranscriptionally by the interactions between beads according to its ruleset. We study the problem of designing a transcript that folds into the given conformation using the given ruleset, which is called the transcript design problem. We prove that the problem is computationally difficult to solve (NP-hard). Then we design efficient poly-time algorithms with additional restrictions on the oritatami system.

Original languageEnglish
Title of host publicationDNA Computing and Molecular Programming - 24th International Conference, DNA 24, 2018, Proceedings
EditorsDavid Doty, Hendrik Dietz
PublisherSpringer Verlag
Number of pages16
ISBN (Print)9783030000295
Publication statusPublished - 2018
Event24th International Conference on DNA Computing and Molecular Programming, DNA 2018 - Jinan, China
Duration: 2018 Oct 82018 Oct 12

Publication series

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


Other24th International Conference on DNA Computing and Molecular Programming, DNA 2018

Bibliographical note

Publisher Copyright:
© Springer Nature Switzerland AG 2018.

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Transcript design problem of oritatami systems'. Together they form a unique fingerprint.

Cite this