February 6th, 2018
We introduce and study the computational power of Oritatami, a theoretical model to explore greedy molecular folding, by which the molecule begins to fold before waiting the end of its production. This model is inspired by our recent experimental work demonstrating the construction of shapes at the nanoscale by folding an RNA molecule during its transcription from an engineered sequence of synthetic DNA. While predicting the most likely conformation is known to be NP-complete in other models, Oritatami sequences fold optimally in linear time. Although our model uses only a small subset of the mechanisms known to be involved in molecular folding, we show that it is capable of efficient universal computation, implying that any extension of this model will have this property as well.
This result is the first principled construction in this research direction, and motivated the development of a generic toolbox, easily reusable in future work. One major challenge addressed by our design is that choosing the interactions to get the folding to react to its environment is NP-complete. Our techniques bypass this issue by allowing some flexibility in the shapes, which allows to encode different « functions » in different parts of the sequence (instead of using the same part of the sequence). However, the number of possible interactions between these functions remains quite large, and each interaction also involves a small combinatorial optimisation problem. One of the major challenges we faced was to decompose our programming into various levels of abstraction, allowing to prove their correctness thoroughly in a human readable/checkable form.
We hope this framework can be generalised to other discrete dynamical systems, where proofs of such large objects are often difficult to get.
Joint work with Cody Geary (Caltech), Pierre-Étienne Meunier (Tapdance, Inria Paris), et Shinnosuke Seki (U. Electro-Communications, Tokyo)
Nicolas Schabanel is a Research Director at CNRS and Resident member of the Rhône-Alpes Complex Systems Institute (IXXI) École normale supérieure de Lyon
