Oritatami System : a Survey and the Impossibility of Simple Simulation at Small Delays

• Autorzy: Rogers T. A. , Seki S.

Identyfikatory

DOI

10.3233/FI-2017-1571

• Języki publikacji: EN

Abstrakty

EN

RNA sequences start folding immediately as they are synthesized by RNA polymerase (cotranscriptional folding). The oritatami system (OS) is a novel mathematical model to study computational aspects of cotranscriptional folding. In this paper, we first provide a survey throughout existing research topics and results on oritatami systems and offer research directions of significance. Simulation of an oritatami system in a different ratio (delay) of transcription speed to the speed of folding is one of them. We will introduce a simple notion of simulation, and prove that there is an OS of delay δ that cannot be simulated by any oritatami system at larger delay.

Słowa kluczowe

EN

oritatami system; RNA cotranscriptional folding; molecular self-assembly; turing universality; simulation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 359--372
• Opis fizyczny: Bibliogr. 15 poz., rys.

Twórcy

autor

Rogers T. A.

• Department of Computer Science and Computer Engineering, University of Arkansas, USA

autor

Seki S.

• Department of Computer and Network Engineering, The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu, Tokyo, 1828585, Japan

Bibliografia

• [1] Geary C, Rothemund PWK, Andersen ES. A Single-Stranded Architecture for Cotranscriptional Folding of RNA Nanostructures. Science, 2014;345(6198):799–804. doi:10.1126/science.1253920.
• [2] Elliott D, Ladomery M. Molecular Biology of RNA. Oxford University Press, 2nd edition, 2016. ISBN:9780199671397, 0199671397.
• [3] Merkhofer EC, Hu P, Johnson TL. Introduction to Cotranscriptional RNA Splicing. In: Hertel KJ (ed.), Spliceosomal Pre-mRNA Splicing: Methods and Protocols, volume 1126 of Methods in Molecular Biology, Springer, 2014 pp. 83–96. doi:10.1007/978-1-62703-980-2_6.
• [4] Watters KE, Strobel EJ, Yu AM, Lis JT, Lucks JB. Cotranscriptional Folding of a Riboswitch at Nucleotide Resolution. Nat. Struct. Mol. Biol., 2016;23(12):1124–1133. doi:10.1038/nsmb.3316.
• [5] Feynman RP. Feynman Lectures on Computation. Westview Press, 1996. ISBN-10:0738202967, 13:978-0738202969.
• [6] Geary C, Meunier PE, Schabanel N, Seki S. Programming Biomolecules that Fold Greedily during Transcription. In: Proc. MFCS 2016, volume 58 of LIPIcs. 2016 pp. 43:1–43:14. doi:10.4230/LIPIcs.MFCS.2016.43.
• [7] Woods D. Intrinsic universality and the computational power of self-assembly. In: Proc. MCU 2013, volume 128. Open Publishing Association, 2013 pp. 16–22. doi:10.4204/EPTCS.128.5.
• [8] Han YS, Kim H, Ota M, Seki S. Nondeterministic Seedless Oritatami Systems and Hardness of Testing Their Equivalence. In: Proc. DNA 22, LNCS 9818. Springer, 2016 pp. 19–34. doi:10.1007/978-3-319-43994-5_2.
• [9] Elonen A. Molecular Folding and Computation. Bachelor Thesis, Aalto University, 2016.
• [10] Geary C, Meunier PE, Schabanel N, Seki S. Folding Turing is Hard but Feasible. ArXiv:1508.00510v2.
• [11] Han YS, Kim H. Ruleset Optimization on Isomorphic Oritatami Systems. In: Proc. DNA 23. Springer, 2017 In press.
• [12] Han YS, Kim H, Rogers TA, Seki S. Self-attraction Removal from Oritatami Systems. In: Proc. DCFS, 10316 LNCS. 2017 pp. 164–176. doi:10.1007/978-3-319-60252-3_13.
• [13] Ota M, Seki S. Rule Set Design Problems for Oritatami Systems. Theor. Comput. Sci., 2017;671:26–35. URL RuleSetDesignProblemsforOritatamiSystems.
• [14] Geary C, Andersen ES. Design Principles for Single-Stranded RNA Origami Structures. In: Proc. DNA 20, LNCS 8727. Springer, 2014 pp. 1–19. doi:10.1007/978-3-319-11295-4_1.
• [15] Cook M. Universality in Elementary Cellular Automata. Complex Systems, 2004;15:1–40.