CaltechAUTHORS
  A Caltech Library Service

Oritatami: A Computational Model for Molecular Co-Transcriptional Folding

Geary, Cody and Meunier, Pierre-Étienne and Schabanel, Nicolas and Seki, Shinnosuke (2019) Oritatami: A Computational Model for Molecular Co-Transcriptional Folding. International Journal of Molecular Sciences, 20 (9). Art. No. 2259. ISSN 1422-0067. PMCID PMC6539498. https://resolver.caltech.edu/CaltechAUTHORS:20190507-105000874

[img] PDF - Published Version
Creative Commons Attribution.

3722Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190507-105000874

Abstract

We introduce and study the computational power of Oritatami, a theoretical model that explores greedy molecular folding, whereby a molecular strand begins to fold before its production is complete. This model is inspired by our recent experimental work demonstrating the construction of shapes at the nanoscale from RNA, where strands of RNA fold into programmable shapes during their transcription from an engineered sequence of synthetic DNA. In the model of Oritatami, we explore the process of folding a single-strand bit by bit in such a way that the final fold emerges as a space-time diagram of computation. One major requirement in order to compute within this model is the ability to program a single sequence to fold into different shapes dependent on the state of the surrounding inputs. Another challenge is to embed all of the computing components within a contiguous strand, and in such a way that different fold patterns of the same strand perform different functions of computation. Here, we introduce general design techniques to solve these challenges in the Oritatami model. Our main result in this direction is the demonstration of a periodic Oritatami system that folds upon itself algorithmically into a prescribed set of shapes, depending on its current local environment, and whose final folding displays the sequence of binary integers from 0 to N = 2^k−1 with a seed of size O(k) . We prove that designing Oritatami is NP-hard in the number of possible local environments for the folding. Nevertheless, we provide an efficient algorithm, linear in the length of the sequence, that solves the Oritatami design problem when the number of local environments is a small fixed constant. This shows that this problem is in fact fixed parameter tractable (FPT) and can thus be solved in practice efficiently. We hope that the numerous structural strategies employed in Oritatami enabling computation will inspire new architectures for computing in RNA that take advantage of the rapid kinetic-folding of RNA.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.3390/ijms20092259DOIArticle
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6539498PubMed CentralArticle
ORCID:
AuthorORCID
Geary, Cody0000-0003-2083-4259
Additional Information:© 2019 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/). Received: 15 April 2019; Accepted: 30 April 2019; Published: 7 May 2019. Author Contributions: All authors contributed to: conceptualization, methodology, validation, formal analysis, investigation, resources, writing–original draft preparation and review and editing, supervision, project administration. Software and visualization, P.-É. Meunier and N. Schabanel. C. Geary is a Carlsberg Postdoctoral Fellow supported by the Carlsberg Foundation. N. Schabanel is supported by Grants ANR-12-BS02-005 RDAM, IXXI MOLECAL, IXXI CALCASMOL, CNRS MoPrExProgMol and CNRS AMARP grants. S. Seki is in part supported by the Academy of Finland, Postdoctoral Researcher Grant 13266670/T30606, JST Program to Disseminate Tenure Tracking System, MEXT, Japan, No. 6F36 and JSPS KAKENHI Grant-in-Aid for Young Scientists (A) No. 16H05854 and for Challenging Research (Exploratory) No. 18K19779. The authors thank Abdulmelik Mohammed, Andrew Winslow, Damien Woods for discussions and encouragements. The authors declare no conflict of interest.
Funders:
Funding AgencyGrant Number
Carlsberg FoundationUNSPECIFIED
Agence Nationale pour la Recherche (ANR)ANR-12-BS02-005 RDAM
Centre National de la Recherche Scientifique (CNRS)IXXI MOLECAL
Centre National de la Recherche Scientifique (CNRS)IXXI CALCASMOL
Centre National de la Recherche Scientifique (CNRS)MoPrExProgMol
Centre National de la Recherche Scientifique (CNRS)AMARP
Academy of Finland13266670/T30606
Japan Science and Technology AgencyUNSPECIFIED
Ministry of Education, Culture, Sports, Science and Technology (MEXT)6F36
Japan Society for the Promotion of Science (JSPS)16H05854
Japan Society for the Promotion of Science (JSPS)18K19779
Subject Keywords:natural computing; self-assembly; molecular folding
Issue or Number:9
PubMed Central ID:PMC6539498
Record Number:CaltechAUTHORS:20190507-105000874
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190507-105000874
Official Citation:Geary, C.; Meunier, P.-É.; Schabanel, N.; Seki, S. Oritatami: A Computational Model for Molecular Co-Transcriptional Folding. Int. J. Mol. Sci. 2019, 20, 2259; doi: 10.3390/ijms20092259
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:95295
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:07 May 2019 18:03
Last Modified:03 Oct 2019 21:12

Repository Staff Only: item control page