Top

Natural Computing

Published in:

26-09-2023

Programmable single-stranded architectures for computing

Authors: Yu Kihara, Shinnosuke Seki

Published in: Natural Computing | Issue 3/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Oritatami is a mathematical model of co-transcriptional folding, a phenomenon in which, while being synthesized (transcribed) sequentially, an RNA sequence folds upon itself into complex structures via hydrogen bonds between its nucleotides (A, C, G, and U). RNA sequences fold co-transcriptionally to perform computations in-vivo such as gene expression regulation and splicing. Co-transcriptional folding has been recently proven modularly programmable for assembling structures in-vitro in the RNA origami framework as well as for computing arbitrary computable functions in-silico using the oritatami model. In this tutorial, we overview computations in oritatami and their “bricks” to build up from, that is, modules, and then discuss what should be done along with concrete open problems as a seed for further fruitful developments in computation by co-transcriptional folding.

previous article Planar Rosa: a family of quasiperiodic substitution discrete plane tilings with 2n-fold rotational symmetry

next article Gauge-invariance in cellular automata

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Alberts B, Johnson A, Lewis J, Morgan D, Raff M, Roberts K, Walter P (2014) Molecular biology of the cell, 6th edn. Garland Science

Arora S, Barak B (2009) Computational complexity: a modern approach. Cambridge University Press, CambridgeCrossRefMATH

Demaine ED, Hendricks J, Olsen M, Patitz MJ, Rogers TA, Schabanel N, Seki S, Thomas H (2018) Know when to fold ’em: self-assembly of shapes by folding in oritatami. In: Proceedings of the 24th international conference on DNA computing and molecular programming (DNA 24), volume 11145 of LNCS, Springer, pp 19–36

Diestel R (2010) Graph theory, 4th edn. Springer, ChamCrossRefMATH

Doty D, Lutz J H, Patitz M J, Schweller RT, Summers SM, Woods D (2012) The tile assembly model is intrinsically universal. In: Proceedings of the 53rd annual IEEE symposium on foundations of computer science (FOCS 2012), pp 302–310

Elliott D, Ladomery M (2016) Molecular biology of RNA. Oxford University Press, Oxford

Fazekas SZ, Kim H, Matsuoka R, Morita R, Seki S (2021) Linear bounds on the size of conformations in greedy deterministic oritatami. Int J Found Comput Sci 32(5):575–596MathSciNetCrossRefMATH

Fazekas SZ, Kim H, Matsuoka R, Seki S, Takeuchi H (2022) On algorithmic self-assembly of squares by co-transcriptional folding. In: Proceedings of the 33rd international symposium on algorithms and computation (ISAAC 2022), volume 248 of LIPIcs, pp 37:1–37:15

Feynman RP (1996) Feynman lectures on computation. Addison-Wesley, London

Geary C, Andersen E S (2014) Design principles for single-stranded RNA origami structures. In: Proceedings of the 20th international conference on DNA computing and molecular programming (DNA 20), volume 8727 of LNCS, pp 1–19. Springer

Geary C, Grossi G, McRae EKS, Rothemund PWK, Andersen ES (2021) RNA origami design tools enable cotranscriptional folding of kilobase-sized nanoscaffolds. Nat Chem 13:549–558CrossRef

Geary C, Meunier P-É, Schabanel N, Seki S (2018) Proving the turing universality of oritatami co-transcriptional folding. In: Proceedings of the 29th international symposium on algorithms and computation (ISAAC 2018), volume 123 of LIPIcs, pp 23:1–23:13

Geary C, Meunier PÉ, Schabanel N, Seki S (2019) Oritatami: a computational model for molecular cotranscriptional folding. Int J Mol Sci 20(9):2259

Geary C, Meunier P-É, Schabanel N, Seki S (2016) Programming biomolecules that fold greedily during transcription. In: Proceedings of the 41st international symposium on mathematical foundations of computer science (MFCS 2016), volume 58 of LIPIcs, pp 43:1–43:14

Geary C, Rothemund PWK, Andersen ES (2014) A single-stranded architecture for cotranscriptional folding of RNA structures. Science 345(6198):799–804CrossRef

Geary MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co

Hader D, Koch A, Patitz MJ, Sharp M (2020) The impacts of dimensionality, diffusion, and directedness on intrinsic universality in the abstract tile assembly model. In: Proceedings of the 2020 ACM-SIAM symposium on discrete algorithms (SODA 2020), pp 2607–2624

Hagiya M, Arita M, Kiga D, Sakamoto K, Yokoyama S (1997) Towards parallel evaluation and learning of boolean \(\mu \)-formulas with molecules. In: Proceedings of the DIMACS workshop on DNA based computers, volume 48 of DIMACS series in discrete mathematics and theoretical computer science, pp 57–72

Han Y-S, Kim H (2018) Construction of geometric structure by oritatami system. In: Proceedings of the 24th international conference on DNA computing and molecular programming (DNA 24), volume 11145 of LNCS, pp 173–188

Han Y-S, Kim H (2019) Ruleset optimization on isomorphic oritatami systems. Theoret Comput Sci 128–139

Han Y-S, Kim H (2021) Impossibility of strict assembly of infinite fractals by oritatami. Nat Comput 20(4):691–701MathSciNetCrossRef

Han Y-S, Kim H, Masuda Y, Seki S (2021) A general architecture of oritatami systems for simulating arbitrary finite automata. Theoret Comput Sci 870:29–52MathSciNetCrossRefMATH

Han Y-S, Kim H, Ota M, Seki S (2018) Nondeterministic seedless oritatami systems and hardness of testing their equivalence. Nat Comput 17(1):67–79MathSciNetCrossRefMATH

Han Y-S, Kim H, Rogers TA, Seki S (2019) Self-attraction removal from oritatami systems. Int J Found Comput Sci 30(6–7):1047–1067MathSciNetCrossRefMATH

Han Y-S, Kim H, Seki S (2020) Transcript design problems of oritatami systems. Nat Comput 19(2):323–335MathSciNetCrossRefMATH

Harel D, Sardas M (1998) An algorithm for straight-line drawing of planar graphs. Algorithmica 20(2):119–135MathSciNetCrossRefMATH

Hopcroft JE, Motwani R, Ullman JD (2001) Introduction to automata theory, languages, and computation, 2nd edn. Addison Wesley, LondonMATH

Iwano N (2023) Concurrent signal passing by co-transcriptional folding. Bachelor’s thesis, The University of Electro-Communications. Tokyo, Japan

Jaeger L, Chworos A (2006) The architectonics of programmable RNA and DNA nanostructures. Curr Opin Struct Biol 16(4):531–543CrossRef

Kari L, Kopecki S, Meunier PÉ, Patitz MJ, Seki S (2017) Binary pattern tile set synthesis is NP-hard. Algorithmica 78(1):1–46MathSciNetCrossRefMATH

Lathrop JI, Lutz JH, Summers SM (2009) Strict self-assembly of discrete Sierpinski triangles. Theoret Comput Sci 410:384–405MathSciNetCrossRefMATH

Marcus P, Schabanel N, Seki S (2023) Ok, a kinetic model for locally reconfigurable molecular systems. In: Visins of DNA nanotechnology at 40 for the next 40, pp 229–240. Springer

Maruyama K, Seki S (2021) Counting infinitely by oritatami co-transcriptional folding. Nat Comput 20(2):329–340MathSciNetCrossRefMATH

Masuda Y, Seki S , Ubukata Y (2018) Towards the algorithmic molecular self-assembly of fractals by cotranscriptional folding. In: Proceedings of the 23rd international conference on implementation and application of automata (CIAA 2018), volume 10977 of LNCS, pp 261–273

Merkhofer EC, Hu P, Johnson TL (2014) Introduction to cotranscriptional RNA folding. In: Methods in molecular biology, volume 1126, pp 83–96. Springer

Nalin S, Theyssier G (2022) On turedo hierarchies and intrinsic universality. In: Proceedings of the 28th international conference on DNA computing and molecular programming (DNA 28), volume 238 of LIPIcs, pp 6:1–6:18

Ota M, Seki S (2017) Ruleset design problems for oritatami systems. Theoret Comput Sci 671:26–35MathSciNetCrossRefMATH

Pchelina D, Schabanel N, Seki S, Theyssier G (2022) Oritatami systems assemble shapes no less complex than tile assembly model (aTAM). In: Proceedings of the 39th international symposium on theoretical aspects of computer science (STACS 2022), volume 219 of LIPIcs, pp 51:1–51:23

Pchelina D, Schabanel N, Seki S, Ubukata Y (2020) Simple intrinsic simulation of cellular automata in oritatami molecular folding model. In: Proceedings of the 14th Latin American symposium on theoretical informatics (LATIN 2020), volume 12118 of LNCS, pp 425–436

Reif JH, Majumder U (2010) Isothermal reactivating whiplash PCR for locally programmable molecular computation. Nat Comput 9(1):183–206MathSciNetCrossRefMATH

Rogers TA, Seki S (2017) Oritatami system; a survey and the impossibility of simple simulation at small delays. Fund Inf 154(1–4):359–372MathSciNetMATH

Rose JA, Komiya K, Yaegashi S, Hagiya M (2006) Displacement whiplash PCR: optimized architecture and experimental validation. In: Proceedings of the 12th international meeting on DNA computing (DNA12), volume 4287 of LNCS, pp 393–403

Rothemund PWK, Papadakis N, Winfree E (2004) Algorithmic self-assembly of DNA Sierpinski triangle. PLoS Biol 2:e424

Rothemund PWK, Winfree E (2000) The program-size complexity of self-assembled squares (extended abstracts). In: Proceedings of the 32nd annual ACM symposium on theory of computing (STOC 2000), pp 459–468. ACM

Schabanel N (2016) Simple OS simulator. http://perso.ens-lyon.fr/nicolas.schabanel/OSsimulator/

Watters KE, Strobel EJ, Yu AM, Lis JT, Lucks JB (2016) Cotranscriptional folding of a riboswitch at nucleotide resolution. Nat Struct Mol Biol 23(12):1124–1131CrossRef

Title: Programmable single-stranded architectures for computing
Authors: Yu Kihara
Shinnosuke Seki
Publication date: 26-09-2023
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 3/2023
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-023-09963-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2023

Enumeration of maximal cycles generated by orthogonal cellular automata

On von Neumann regularity of cellular automata

Associating parallel automata network dynamics and strictly one-way cellular automata

Complexity of limit cycles with block-sequential update schedules in conjunctive networks

Cellular automata and substitutions in topological spaces defined via edit distances

Multiobjective evolutionary algorithm IDEA and k-means clustering for modeling multidimenional medical data based on fuzzy cognitive maps

Premium Partner