Speaker: Professor Nicolas Schabanel, CNRS, ENS de Lyon, France
Title: "Simple Intrinsic Cellular Automata simulation in the Oritatami Co-Transcriptional Molecular Folding Model"
Abstract: The Oritatami model was proposed to study the computational potential of RNA cotranscriptional
folding as first shown in wet-lab experiments by Geary et al (Science 2014). In Oritatami models, a
molecule grows component by component (named beads) into the triangular and folds as it grows. More
precisely, the δ last nascent beads are free to move and adopt the positions that maximizes the
number of bonds with the current structure. This dynamics captures the essence of cotranscriptional
folding to a considerable extent, where an RNA sequence folds upon itself into complex shapes and
functions while being synthesized (transcribed) out of its template DNA sequence.
The Oritatami model was proven that it is capable of efficient Turing universal computation by
Meunier et al (2016) thanks to a quite complicated construction that simulates Turing machines via
tag systems. We propose here a simple oritatami system which intrinsically simulates arbitrary 1D
cellular automaton. Being intrinsic, our simulation emulates the behavior of the cellular automata
in a precise way. Furthermore, the number of beads needed is quite modest (182). This construction
relies on the development of new tools such as glider-flattening-based unary I/O interface, sliding
lookup table, and speedbumps which absorb even an exponential offset created by the interface and
utilized in referring to the table. We believe that some of these theoretical designs are simple
enough to hope that simplified versions of them could be implemented in the wet lab. This would open
new possibilities in reconfigurable computing molecular design.
By D. Pchelina (ENS Paris), N. Schabanel (CNRS, ENS de Lyon), S. Seki (UEC, Tokyo), and Y. Ubukata
(NTT Data Corp, Japan).