Colloquium J. Morgenstern
Colloquium J. Morgenstern : Nicolas Schabanel (CNRS)
Nicolas Schabanel (CNRS) will give a talk on 6, february, 2018 (at 11 am): "Folding Turing is hard but feasible"
- Date : 6/02/2018
- Place : Amphithéâtre, Bâtiment Kahn, Inria, Sophia Antipolis
- Guest(s) : Nicolas Schabanel
- Organiser(s) : Comité Colloquium
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.
The presentation will be in english
Book the next dates :
- 20 march : A l’écoute du bruit – L’imagerie par corrélations croisées, by Josselin Garnier (Ecole Polytechnique)
- 24 may : Biological Networks Entropies: examples in neural, genetic and social networks, by Jacques Demongeot (honorary member of the Institut Universitaire de France)
To follow the conference news on Twitter