Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Folding Turing is hard but feasible

Abstract : 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. We introduce general design techniques for programming these molecules. Our main result in this direction is an algorithm in time linear in the sequence length, that finds a rule for folding the sequence deterministically into a prescribed set of shapes depending of its environment. This shows the corresponding problem is fixed-parameter tractable although we proved it is NP-complete in the number of possible environments. This algorithm was used effectively to design several key steps of our constructions.
Complete list of metadata
Contributor : Pierre-Étienne Meunier Connect in order to contact the contributor
Submitted on : Friday, December 8, 2017 - 5:44:19 PM
Last modification on : Friday, March 27, 2020 - 3:34:36 AM

Links full text


  • HAL Id : hal-01659777, version 1
  • ARXIV : 1508.00510



Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki. Folding Turing is hard but feasible. 2017. ⟨hal-01659777⟩



Record views