Folding Turing is hard but feasible - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2017

Folding Turing is hard but feasible

Résumé

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.

Dates et versions

hal-01659777 , version 1 (08-12-2017)

Identifiants

Citer

Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki. Folding Turing is hard but feasible. 2017. ⟨hal-01659777⟩
75 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More