License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DNA.2020.6
URN: urn:nbn:de:0030-drops-129592
Go to the corresponding LIPIcs Volume Portal

Klinge, Titus H. ; Lathrop, James I. ; Moreno, Sonia ; Potter, Hugh D. ; Raman, Narun K. ; Riley, Matthew R.

ALCH: An Imperative Language for Chemical Reaction Network-Controlled Tile Assembly

LIPIcs-DNA-2020-6.pdf (0.6 MB)


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.

BibTeX - Entry

  author =	{Titus H. Klinge and James I. Lathrop and Sonia Moreno and Hugh D. Potter and Narun K. Raman and Matthew R. Riley},
  title =	{{ALCH: An Imperative Language for Chemical Reaction Network-Controlled Tile Assembly}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{6:1--6:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-163-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{174},
  editor =	{Cody Geary and Matthew J. Patitz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-129592},
  doi =		{10.4230/LIPIcs.DNA.2020.6},
  annote =	{Keywords: Tile assembly, Chemical reaction network, Sierpinski triangle}

Keywords: Tile assembly, Chemical reaction network, Sierpinski triangle
Collection: 26th International Conference on DNA Computing and Molecular Programming (DNA 26)
Issue Date: 2020
Date of publication: 04.09.2020
Supplementary Material: The ALCH compiler and the CRN-TAM simulator, together with examples and visual illustrations, are available at

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI