Document Open Access Logo

Oritatami Systems Assemble Shapes No Less Complex Than Tile Assembly Model (ATAM)

Authors Daria Pchelina, Nicolas Schabanel, Shinnosuke Seki, Guillaume Theyssier

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.51.pdf
  • Filesize: 19 MB
  • 23 pages

Document Identifiers

Author Details

Daria Pchelina
  • LIPN, Institut Galilée – Université Paris 13, France
Nicolas Schabanel
  • École Normale Supérieure de Lyon (LIP UMR5668 and IXXI, MC2), France
Shinnosuke Seki
  • University of Electro-Communications, Tokyo, Japan
Guillaume Theyssier
  • Aix-Marseille Université, CNRS, I2M, Marseille, France

Funding

  • Schabanel, Nicolas: CNRS MITI MoPrExProgMol; IXXI Molécal; CNRS MITI AMARP; CNRS MITI DNASALGO; CNRS INS2I Algadène.
  • Seki, Shinnosuke: JSPS KAKENHI Grant-in-Aids for Scientific Research (B) No. 20H04141 and (C) No. 20K11672.

Cite As Get BibTex

Daria Pchelina, Nicolas Schabanel, Shinnosuke Seki, and Guillaume Theyssier. Oritatami Systems Assemble Shapes No Less Complex Than Tile Assembly Model (ATAM). In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 51:1-51:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.STACS.2022.51

Abstract

Different models have been proposed to understand natural phenomena at the molecular scale from a computational point of view. Oritatami systems are a model of molecular co-transcriptional folding: the transcript (the "molecule") folds as it is synthesized according to a local energy optimisation process, in a similar way to how actual biomolecules such as RNA fold into complex shapes and functions. We introduce a new model, called turedo, which is a self-avoiding Turing machine on the plane that evolves by marking visited positions and that can only move to unmarked positions. Any oritatami can be seen as a particular turedo. We show that any turedo with lookup radius 1 can conversely be simulated by an oritatami, using a universal bead type set. Our notion of simulation is strong enough to preserve the geometrical and dynamical features of these models up to a constant spatio-temporal rescaling (as in intrinsic simulation). As a consequence, turedo can be used as a readable oritatami "higher-level" programming language to build readily oritatami "smart robots", using our explicit simulation result as a compiler. 
As an application of our simulation result, we prove two new complexity results on the (infinite) limit configurations of oritatami systems (and radius-1 turedos), assembled from a finite seed configuration. First, we show that such limit configurations can embed any recursively enumerable set, and are thus exactly as complex as aTAM limit configurations. Second, we characterize the possible densities of occupied positions in such limit configurations: they are exactly the Π₂-computable numbers between 0 and 1. We also show that all such limit densities can be produced by one single oritatami system, just by changing the finite seed configuration. 
None of these results is implied by previous constructions of oritatami embedding tag systems or 1D cellular automata, which produce only computable limit configurations with constrained density.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Molecular computing
  • Computing methodologies → Molecular simulation
  • Applied computing → Molecular structural biology
  • Theory of computation → Computability
  • Theory of computation → Complexity theory and logic
Keywords
  • Molecular Self-assembly
  • Co-transcriptional folding
  • Intrinsic simulation
  • Arithmetical hierarchy of real numbers
  • 2D Turing machines
  • Computability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Sebastián Barbieri, Jarkko Kari, and Ville Salo. The group of reversible Turing machines. In Cellular Automata and Discrete Complex Systems, pages 49-62. Springer International Publishing, 2016. URL: https://doi.org/10.1007/978-3-319-39300-1_5.
  2. Florent Becker, Diego Maldonado, Nicolas Ollinger, and Guillaume Theyssier. Universality in freezing cellular automata. In Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Kiel, Germany, July 30 - August 3, 2018, Proceedings, pages 50-59, 2018. URL: https://doi.org/10.1007/978-3-319-94418-0_5.
  3. Marianne Delorme, Jacques Mazoyer, Nicolas Ollinger, and Guillaume Theyssier. Bulking ii: Classifications of cellular automata. Theor. Comput. Sci., 412(30):3881-3905, 2011. URL: https://doi.org/10.1016/j.tcs.2011.02.024.
  4. Erik D. Demaine, Jacob Hendricks, Meagan Olsen, Matthew J. Patitz, Trent A. Rogers, Nicolas Schabanel, Shinnosuke Seki, and Hadley Thomas. Know when to fold 'em: Self-assembly of shapes by folding in oritatami. In DNA Computing and Molecular Programming - 24th International Conference, DNA 24, Jinan, China, October 8-12, 2018, Proceedings, volume LNCS 11145, pages 19-36, 2018. URL: https://doi.org/10.1007/978-3-030-00030-1_2.
  5. D. Doty, J. H. Lutz, M. J. Patitz, R. T. Schweller, and S. M. Summer. The tile assembly model is intrinsically universal. In Proceedings of the 53rd Annual Foundations of Computer Science (FOCS), 2012. Google Scholar
  6. David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, and Damien Woods. The tile assembly model is intrinsically universal. In FOCS2012: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, pages 302-310, 2012. Google Scholar
  7. Erling Følner. On groups with full banach mean value. MATHEMATICA SCANDINAVICA, 3:243, December 1955. URL: https://doi.org/10.7146/math.scand.a-10442.
  8. Cody Geary, Guido Grossi, Ewan K. S. McRae, Paul W. K. Rothemund, and Ebbe S. Andersen. RNA origami design tools enable cotranscriptional folding of kilobase-sized nanoscaffolds. Nature Chemistry, 13:549-558, 2021. Google Scholar
  9. Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, and Shinnosuke Seki. Programming biomolecules that fold greedily during transcription. In MFCS2016: Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, volume 58 of LIPIcs, pages 43:1-43:14, 2016. Google Scholar
  10. Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, and Shinnosuke Seki. Oritatami: A computational model for molecular co-transcriptional folding. International Jounal of Molecular Sciences, 9(2259), 2019. URL: https://doi.org/10.3390/ijms20092259.
  11. Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, and Shinonsuke Seki. Proving the Turing universality of oritatami cotranscriptional folding. In ISAAC 2018: Proceedings of the 29th International Symposium on Algorithms and Computation, volume 123 of LIPIcs, pages 23:1-23:13, 2018. Google Scholar
  12. Cody Geary, Paul W. K. Rothemund, and Ebbe S. Andersen. A single-stranded architecture for cotranscriptional folding of RNA nanostructures. Science, 345:799-804, 2014. Google Scholar
  13. E. Goles, N. Ollinger, and G. Theyssier. Introducing freezing cellular automata. In J. Kari, I. Törmä, and M. Szabados, editors, Exploratory Papers of Cellular Automata and Discrete Complex Systems (AUTOMATA 2015), pages 65-73, 2015. Google Scholar
  14. Petr Kůrka. Topological and symbolic dynamics. Société Mathématique de France, 2003. Google Scholar
  15. James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, and Scott M. Summers. Computability and complexity in self-assembly. Theory Comput. Syst., 48(3):617-647, 2011. URL: https://doi.org/10.1007/s00224-010-9252-0.
  16. Diego Maldonado, Anahí Gajardo, Benjamin Hellouin de Menibus, and Andrés Moreira. Nontrivial turmites are Turing-universal. J. Cell. Autom., 13(5-6):373-392, 2018. URL: http://www.oldcitypublishing.com/journals/jca-home/jca-issue-contents/jca-volume-13-number-5-6-2018/jca-13-5-6-p-373-392/.
  17. Yusei Masuda, Shinnosuke Seki, and Yuki Ubukata. Towards the algorithmic molecular self-assembly of fractals by cotranscriptional folding. In CIAA2018: the 23rd International Conference on Implementation and Application of Automata, volume 10977 of LNCS, pages 261-273. Springer, 2018. Google Scholar
  18. Nicolas Ollinger and Guillaume Theyssier. Freezing, bounded-change and convergent cellular automata. CoRR, abs/1908.06751, 2019. URL: http://arxiv.org/abs/1908.06751.
  19. Matthew J. Patitz. An introduction to tile-based self-assembly and a survey of recent results. Natural Computing, 13(2):195-224, 2014. Google Scholar
  20. Daria Pchelina, Nicolas Schabanel, Shinnosuke Seki, and Yuki Ubukata. Simple intrinsic simulation of cellular automata in oritatami molecular folding model. In Yoshiharu Kohayakawa and Flávio Keidi Miyazawa, editors, LATIN 2020: Theoretical Informatics - 14th Latin American Symposium, São Paulo, Brazil, January 5-8, 2021, Proceedings, volume 12118 of Lecture Notes in Computer Science, pages 425-436. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-61792-9_34.
  21. Paul W. K. Rothemund, Nick Papadakis, and Erik Winfree. Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biology, 2:2041-2053, 2004. Google Scholar
  22. Nicolas Schabanel. Simple OS simulator, 2021. URL: http://perso.ens-lyon.fr/nicolas.schabanel/OSsimulator/.
  23. Nicolas Schabanel and Shinnosuke Seki. Turedo to oritatami compiler, 2022. URL: https://hub.darcs.net/turedo2oritatami/turedo2oritatami.
  24. Erik Winfree. Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology, 1998. Google Scholar
  25. Xizhong Zheng and Klaus Weihrauch. The arithmetical hierarchy of real numbers. In Mirosław Kutyłowski, Leszek Pacholski, and Tomasz Wierzbicki, editors, Mathematical Foundations of Computer Science 1999, pages 23-33, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact