Folding shapes with oritatami systems
1 : Laboratoire de l'Informatique du Parallélisme
(LIP)
-
Site web
École Normale Supérieure - Lyon, Centre National de la Recherche Scientifique, CNRS : UMR5668
46 Allée d'Italie 69364 LYON CEDEX 07 -
France
Joint work with Erik D. Demaine, Jacob Hendricks, Meagan Olsen, Matthew J. Patitz, Trent A. Rogers, Shinnosuke Seki and Hadley Thomas.
An oritatami system (OS) is a theoretical model of self-assembly via co-transcriptional folding. It consists of a growing chain of beads which can form bonds with each other as they are transcribed. During the transcription process, the $\delta$ most recently produced beads dynamically fold so as to maximize the number of bonds formed, self-assemblying into a shape incrementally. The parameter $\delta$ is called the \emph{delay} and is related to the transcription rate in nature.
This article initiates the study of shape self-assembly using oritatami. A shape is a connected set of points in the triangular lattice. We first show that oritatami systems differ fundamentally from tile-assembly systems by exhibiting a family of infinite shapes that can be tile-assembled but cannot be folded by any OS. As it is NP-hard in general to determine whether there is an OS that folds into (self-assembles) a given finite shape, we explore the folding of upscaled versions of finite shapes. We show that any shape can be folded from a constant size seed, at any scale $n\geq 3$, by an OS with delay $1$. We also show that any shape can be folded at the smaller scale $2$ by an OS with \emph{unbounded} delay. This leads us to investigate the influence of delay and to prove that there are shapes that can be folded (at scale~$1$) with delay $\delta$ but not with delay $\delta'<\delta$, for all $\delta > 2$.
These results serve as a foundation for the study of shape-building in this new model of self-assembly, and have the potential to provide better understanding of cotranscriptional folding in biology, as well as improved abilities of experimentalists to design artificial systems that self-assemble via this complex dynamical process.