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 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.