LIPIcs.DNA.2020.6.pdf
- Filesize: 0.6 MB
- 22 pages
Document
ALCH: An Imperative Language for Chemical Reaction Network-Controlled Tile Assembly
Authors
-
Part of:
Volume:
26th International Conference on DNA Computing and Molecular Programming (DNA 26)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on DNA Computing and Molecular Programming - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-09-04
File
Document Identifiers
Acknowledgements
We thank the three anonymous reviewers for their helpful comments and suggestions. We especially thank reviewer 3 for their detailed insights, comments, and suggestions.
Cite As Get BibTex
Titus H. Klinge, James I. Lathrop, Sonia Moreno, Hugh D. Potter, Narun K. Raman, and Matthew R. Riley. ALCH: An Imperative Language for Chemical Reaction Network-Controlled Tile Assembly. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DNA.2020.6
Abstract
In 2015 Schiefer and Winfree introduced the chemical reaction network-controlled tile assembly model (CRN-TAM), a variant of the abstract tile assembly model (aTAM), where tile reactions are mediated via non-local chemical signals. In this paper, we introduce ALCH, an imperative programming language for specifying CRN-TAM programs. ALCH contains common features like Boolean variables, conditionals, and loops. It also supports CRN-TAM-specific features such as adding and removing tiles. A unique feature of the language is the branch statement, a nondeterministic control structure that allows us to query the current state of tile assemblies. We also developed a compiler that translates ALCH to the CRN-TAM, and a simulator that simulates and visualizes the self-assembly of a CRN-TAM program. Using this language, we show that the discrete Sierpinski triangle can be strictly self-assembled in the CRN-TAM. This solves an open problem that the CRN-TAM is capable of self-assembling infinite shapes at scale one that the aTAM cannot. ALCH allows us to present this construction at a high level, abstracting species and reactions into C-like code that is simpler to understand. Our construction utilizes two new CRN-TAM techniques that allow us to tackle this open problem. First, it employs the branching feature of ALCH to probe the previously placed tiles of the assembly and detect the presence and absence of tiles. Second, it uses scaffolding tiles to precisely control tile placement by occluding any undesired binding sites.
Subject Classification
ACM Subject Classification
- Theory of computation → Models of computation
Keywords
- Tile assembly
- Chemical reaction network
- Sierpinski triangle
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Florent Becker. Pictures worth a thousand tiles, a geometrical programming language for self-assembly. Theoretical Computer Science, 410(16):1495-1515, 2009. Theory and Applications of Tiling. URL: https://doi.org/10.1016/j.tcs.2008.12.011.
- Matthew Cook, David Soloveichik, Erik Winfree, and Jehoshua Bruck. Programmability of chemical reaction networks. In Algorithmic Bioprocesses, Natural Computing Series, pages 543-584. Springer, 2009. URL: https://doi.org/10.1007/978-3-540-88869-7_27.
- 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 Proceedings of the 53rd Symposium on Foundations of Computer Science, pages 302-310. IEEE, 2012. URL: https://doi.org/10.1109/FOCS.2012.76.
- David Doty and Matthew J. Patitz. A domain-specific language for programming in the tile assembly model. In Proceedings of the 17th International Conference on DNA Computing and Molecular Programming, pages 25-34. Springer Berlin Heidelberg, 2009. URL: https://doi.org/10.1007/978-3-642-10604-0_3.
- Irving Robert Epstein and John Anthony Pojman. An Introduction to Nonlinear Chemical Dynamics: Oscillations, Waves, Patterns, and Chaos. Oxford University Press, 1998. URL: https://doi.org/10.1021/ed077p450.1.
- Martin Feinberg. Foundations of chemical reaction network theory. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-03858-8.
- David Furcy, Scott M. Summers, and Christian Wendlandt. New bounds on the tile complexity of thin rectangles at temperature-1. In Proceedings of the 25rd International Conference on DNA Computing and Molecular Programming, pages 100-119. Springer International Publishing, 2019. URL: https://doi.org/10.1007/978-3-030-26807-7_6.
- James I. Lathrop, Jack H. Lutz, and Scott M. Summers. Strict self-assembly of discrete Sierpinski triangles. Theoretical Computer Science, 410(4):384-405, 2009. URL: https://doi.org/10.1016/j.tcs.2008.09.062.
- Anthony M. L. Liekens and Chrisantha T. Fernando. Turing complete catalytic particle computers. In Advances in Artificial Life, pages 1202-1211. Springer Berlin Heidelberg, 2007. URL: https://doi.org/10.1007/978-3-540-74913-4_120.
- Pierre-Étienne Meunier and Damien Woods. The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 328-341. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055446.
- Nicholas Schiefer and Erik Winfree. Universal computation and optimal construction in the chemical reaction network-controlled tile assembly model. In Proceedings of the 21st International Conference on DNA Computing and Molecular Programming, pages 34-54. Springer International Publishing, 2015. URL: https://doi.org/10.1007/978-3-319-21999-8_3.
- Nicholas Schiefer and Erik Winfree. Time complexity of computation and construction in the chemical reaction network-controlled tile assembly model. In Proceedings of the 22nd International Conference on DNA Computing and Molecular Programming, pages 165-182. Springer International Publishing, 2016. URL: https://doi.org/10.1007/978-3-319-43994-5_11.
- Nadrian C. Seeman. Nucleic acid junctions and lattices. Journal of Theoretical Biology, 99(2):237-247, 1982. URL: https://doi.org/10.1016/0022-5193(82)90002-9.
- Marko Vasić, David Soloveichik, and Sarfraz Khurshid. CRN++: Molecular programming language. Natural Computing, pages 1-17, 2020. URL: https://doi.org/10.1007/s11047-019-09775-1.
- Erik Winfree. Algorithmic self-assembly of DNA. PhD thesis, California Institute of Technology, 1998. URL: https://resolver.caltech.edu/CaltechETD:etd-05192003-110022.