-
- Date de réalisation : 6 Février 2018
- Durée du programme : 71 min
- Classification Dewey : Géométrie, Biochimie, Algorithmes, Computer Science
-
- Catégorie : Conférences
- Niveau : niveau Master (LMD), niveau Doctorat (LMD), Recherche
- Disciplines : Mathématiques, Informatique, Biochimie
- Collections : Colloquium Jacques Morgenstern : recherches en STIC - nouveaux thèmes scientifiques, nouveaux domaines d’application, et enjeux
- ficheLom : Voir la fiche LOM
-
- Auteur(s) : Schabanel Nicolas
- producteur : INRIA (Institut national de recherche en informatique et automatique)
- Editeur : INRIA (Institut national de recherche en informatique et automatique) , CNRS - Centre National de la Recherche Scientifique , Région PACA , UNS
Dans la même collection
























Folding Turing is hard but feasible
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)
commentaires
Ajouter un commentaire Lire les commentaires