Conférence
Notice
Langue :
Anglais
Crédits
CNRS - Centre National de la Recherche Scientifique (Publication), INRIA (Institut national de recherche en informatique et automatique) (Production), INRIA (Institut national de recherche en informatique et automatique) (Publication), Région PACA (Publication), UNS (Publication), Nicolas Schabanel (Intervention)
Conditions d'utilisation
Droit commun de la propriété intellectuelle
DOI : 10.60527/b1ky-dx21
Citer cette ressource :
Nicolas Schabanel. Inria. (2018, 6 février). Folding Turing is hard but feasible. [Vidéo]. Canal-U. https://doi.org/10.60527/b1ky-dx21. (Consultée le 19 juillet 2025)
RF-Inria-logo-RVB
Inria - Institut national de recherche en sciences et technologies du numérique
S'abonner
Contacter

Folding Turing is hard but feasible

Réalisation : 6 février 2018 - Mise en ligne : 9 février 2018
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

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)

Intervention
Thème
Disciplines :
Documentation

Références:

 

  • [1] P Armitage and Doll. The age distribution of cancer and a multi-stage theory of carcinogenesis. Br J Cancer, 8(1) :1–12, 1954.
  • [2] S H Moolgavkar, N E Day, and R G Stevens. Two-stage model for carcinogenesis : Epidemiology of breast cancer in females. Journal of the National Cancer Institute, 65 :559–569, 1980.
  • [3] M. C. Pike, M. D. Krailo, B. E. Henderson, J. T. Casagrande, and D. G. Hoel. ’hormonal’ risk factors, ’breast tissue age’ and the age-incidence of breast cancer. Nature, 303(5920) :767–770, 1983.
  • [4] E B Claus, N Risch, and W D Thompson. The calculation of breast cancer risk for women with a first degree family history of ovarian cancer. Breast cancer research and treatment, 28 :115–120, Nov 1993.
  • [5] M H Gail and J Benichou. Validation studies on a model for breast cancer risk. Journal of the National Cancer Institute, 86 :573–575, Apr 1994.
  • [6] G Plu-Bureau, M G Lê, R Sitruk-Ware, J C Thalabard, and P Mauvais-Jarvis. Progestogen use and decreased risk of breast cancer in a cohort study of premenopausal women with benign breast disease. British journal of cancer, 70 :270–277, 1994.
  • [7] Eiliv Lund and Vanessa Dumeaux. Systems epidemiology in cancer. Cancer epidemiology, biomarkers & prevention, 17 :2954–2957, 2008.
  • [8] Eiliv Lund, Vanessa Dumeaux, Tonje Braaten, Anette Hjartåker, Dagrun Engeset, Guri Skeie, and Merethe Kumle. Cohort profile : The norwegian women and cancer study–nowac–kvinner og kreft. International journal of epidemiology, 37 :36–41, 2008.
  • [9] Marco Gerlinger, Andrew J Rowan, Stuart Horswell, James Larkin, David Endesfelder, Eva Gronroos, Pierre Martinez, Nicholas Matthews, Aengus Stewart, Patrick Tarpey, Ignacio Varela, Benjamin Phillimore, Sharmin Begum, Neil Q McDonald, Adam Butler, David Jones, Keiran Raine, Calli Latimer, Claudio R Santos, Mahrokh Nohadani, Aron C Eklund, Bradley Spencer-Dene, Graham Clark, Lisa Pickering, Gordon Stamp, Martin Gore, Zoltan Szallasi, Julian Downward, P Andrew Futreal, and Charles Swanton. Intratumor heterogeneity and branched evolution revealed by multiregion sequencing. The New England journal of medicine, 366 :883–892, Mar 2012.
  • [10] Eiliv Lund, Nicolle Mode, Marit Waaseth, and Jean-Christophe Thalabard. Overdiagnosis of breast cancer in the norwegian breast cancer screening program estimated by the norwegian women and cancer cohort study. BMC cancer, 13 :614, 2013.
  • [11] Mary-Claire King. « the race » to clone brca1. Science, 343 :1462–1465, 2014.
  • [12] Vanessa Dumeaux, Josie Ursini-Siegel, Arnar Flatberg, Hans E Fjosne, Jan-Ole Frantzen, Marit Muri Holmen, Enno Rodegerdts, Ellen Schlichting, and Eiliv Lund. Peripheral blood cells inform on the presence of breast cancer : a population-based case-control study. International journal of cancer, 136 :656–667, 2015.
  • [13] Eiliv Lund, Lars Holden, Hege Bøvelstad, Sandra Plancade, Nicolle Mode, Clara-Cecilie Günther, Gregory Nuel, Jean-Christophe Thalabard, and Marit Holden. A new statistical method for curve group analysis of longitudinal gene expression data illustrated for breast cancer in the nowac postgenome cohort as a proof of principle. BMC medical research methodology, 16 :28, 2016.
  • [14] NE Breslow and NE Day. Statistical Methods in Cancer Research Volume II – The Design and Analysis of Cohort Studies, volume II of IARC Scientific Publications No 82. IARC, 1987.
  • [15] NE Breslow and NE Day. Statistical Methods in Cancer Research. Volume I :The analysis of case- control studies, volume I of IARC Scientific Publications No. 32. IARC, 1980.

Sur le même thème