Ruleset optimization on isomorphic oritatami systems

Yo Sub Han, Hwee Kim

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


We study an optimization problem of a computational folding model, proving its hardness and proposing heuristic algorithms. RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized out of a gene. An oritatami model (OM) is a computational model of this phenomenon that lets its sequence of beads (abstract molecules) fold cotranscriptionally by the interactions between beads, according to its ruleset. We study the problem of reducing the ruleset size, while keeping the terminal conformations geometrically the same. We first prove the hardness of finding the smallest ruleset, and then suggest two approaches that reduce the ruleset size efficiently.

Original languageEnglish
Pages (from-to)128-139
Number of pages12
JournalTheoretical Computer Science
Publication statusPublished - 2019 Sept 20

Bibliographical note

Publisher Copyright:
© 2019 Elsevier B.V.

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Ruleset optimization on isomorphic oritatami systems'. Together they form a unique fingerprint.

Cite this