Programming Self-Assembly of DNA Tiles

Issue title: Concurrency, Specification and Programming (CS&P)

Guest editors: Ludwik Czaja, Wojciech Penczek and Krzysztof Stencel

Article type: Research Article

Authors: Bellia, Marco | Occhiuto, M. Eugenia^*

Affiliations: Dipartimento di Informatica, University of Pisa, Italy. [email protected], [email protected]

Correspondence: [*] Address for correspondence: Dipartimento di Informatica, University of Pisa, Italy

Abstract: The paper considers molecular programming in the abstract Tile Assembly Model, aTAM. Using simple constructions, an interpreter for the full Combinatory Logic, CL, is formally defined in aTAM. It provides an approach for sequential programming in aTAM, and produces a DNA molecular machine. This machine lives in a suitable solution and when receives a seed that linearly encodes a CL program and an input for the program, produces a grid which encodes a computation of the program on its input. The paper considers the construction cost and some alternative approaches. Finally, as a case study in distributed programming in aTAM, the paper considers the consensus problem and shows how an aTAM program for it can be formally derived by using π-calculus.

Keywords: DNA Tile self assembly, aTAM model, Combinatory Logic, π-calculus, Consensus problem

DOI: 10.3233/FI-2016-1302

Journal: Fundamenta Informaticae, vol. 143, no. 1-2, pp. 35-49, 2016