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.
|Title of host publication||DNA Computing and Molecular Programming - 24th International Conference, DNA 24, 2018, Proceedings|
|Editors||David Doty, Hendrik Dietz|
|Number of pages||16|
|Publication status||Published - 2018|
|Event||24th International Conference on DNA Computing and Molecular Programming, DNA 2018 - Jinan, China|
Duration: 2018 Oct 8 → 2018 Oct 12
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Other||24th International Conference on DNA Computing and Molecular Programming, DNA 2018|
|Period||18/10/8 → 18/10/12|
Bibliographical notePublisher Copyright:
© Springer Nature Switzerland AG 2018.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)