-
- 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
Folding Turing is hard but feasible
Dans la même collection
The Legacy of Rudolph Kalman
Reasoning over large-scale biological systems with heterogeneous and incomplete data
Majority judgment: a new voting method
Les premiers photons : les saisir, les faire parler
Knowledge transfer and human-machine collaboration for training object class detector
Biological Networks Entropies: examples in neural, genetic and social networks
Copier le code pour partager la vidéo :
The Legacy of Rudolph Kalman
Reasoning over large-scale biological systems with heterogeneous and ...
Majority judgment: a new voting method
Les premiers photons : les saisir, les faire parler
Knowledge transfer and human-machine collaboration for training ...
Biological Networks Entropies: examples in neural, genetic and social ...
A l’écoute du bruit – L’imagerie par corrélations croisées
An extensionalist analysis of computer simulations
Safety Verification of Deep Neural Networks
Proofs assistants : from symbolic logic to real mathematics
Mathématiques, Statistiques et Médecine: des collaborations plus ...
Visual Reconstruction and Image-Based Rendering
Coccinelle: synergy between programming language research and the ...
CoNeCo: Concurrency, Networks and Coinduction
Semantics in the Time of Computing
On Artificial Olfaction, and How to Test For It
Le Bitcoin et les monnaies cryptographiques
Number-theoretic methods in quantum computing
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