Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding Model

Autor: Yuki Ubukata, Daria Pchelina, Shinnosuke Seki, Nicolas Schabanel
Přispěvatelé: École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), University of Electro-Communications [Tokyo] (UEC), NTT Data Corp (NTT Data Corp), École normale supérieure - Paris (ENS Paris), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université Claude Bernard Lyon 1 (UCBL)
Jazyk: angličtina
Rok vydání: 2021
Předmět:
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
[SDV.BIO]Life Sciences [q-bio]/Biotechnology
Computer science
[SDV]Life Sciences [q-bio]
0102 computer and information sciences
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
01 natural sciences
03 medical and health sciences
Turing machine
symbols.namesake
Simple (abstract algebra)
Component (UML)
[SDV.BBM]Life Sciences [q-bio]/Biochemistry
Molecular Biology
[SDV.BBM.BC]Life Sciences [q-bio]/Biochemistry
Molecular Biology/Biochemistry [q-bio.BM]
Turing
030304 developmental biology
computer.programming_language
0303 health sciences
Reconfigurability
Folding (DSP implementation)
[INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation
Cellular automaton
Automaton
010201 computation theory & mathematics
symbols
[INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM]
computer
Algorithm
Zdroj: 14th LATIN 2020: São Paulo, Brazil
14th LATIN 2020: São Paulo, Brazil, Jan 2021, Sao Paulo, Brazil. pp.425-436, ⟨10.1007/978-3-030-61792-9_34⟩
LATIN 2020: Theoretical Informatics ISBN: 9783030617912
LATIN
DOI: 10.1007/978-3-030-61792-9_34⟩
Popis: International audience; The Oritatami model was introduced by Geary et al (2016) to study the computational potential of RNA cotranscriptional folding as first shown in wet-lab experiments by Geary et al (Science 2014). In Oritatami model, a molecule grows component by component (named beads) into the triangular grid and folds as it grows. More precisely, the δ last nascent beads are free to move and adopt the positions that maximizes the number of bonds with the current folded structure. Geary et al (2018) proved that the Oritatami model is capable of efficient Turing universal computation using a complicated construction that simulates Turing machines via tag systems. We propose here a simple Oritatami system which intrinsically simulates arbitrary 1D cellular automata. Being intrinsic, our simulation emulates the behavior of cellular automata in a readable way and in time linear in space and time of the simulated automaton. Oritatami model has proven to be a fruitful framework to study molecular reconfigurability. Our construction relies on the development of new mecanisms which are simple enough that we believe that some simplification of them may be implemented in the wet lab. An implementation of our construction can be downloaded for testing.
Databáze: OpenAIRE
Externí odkaz: