Rule set design problems for oritatami systems

A single-stranded RNA is transcribed from its DNA template by an RNA polymerase enzyme. The RNA transcript begins to fold upon itself while it is still being transcribed. This ubiquitous phenomenon is called cotranscriptional folding and was recently used as an engineering tool to self-assemble “RNA...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2017-04, Vol.671, p.26-35
Main Authors: Ota, Makoto, Seki, Shinnosuke
Format: Article
Language:English
Subjects:
Algorithmic self-assembly
Co-transcriptional folding
Linear-time 2SAT solver
Oritatami system
Time complexity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A single-stranded RNA is transcribed from its DNA template by an RNA polymerase enzyme. The RNA transcript begins to fold upon itself while it is still being transcribed. This ubiquitous phenomenon is called cotranscriptional folding and was recently used as an engineering tool to self-assemble “RNA origami” tile by Geary, Rothemund, and Andersen (2014) [8]. The oritatami system (OS) is a new mathematical model of algorithmic self-assembly by cotranscriptional folding, proposed by Geary, Meunier, Schabanel, and Seki (2016). A problem of designing OSs is studied in this paper. We provide a sharp boundary between the NP-hardness and polynomial-time computability of this problem with respect to the relative speed of transcription to folding and valence of molecules.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2016.09.010