Programming Self-Assembly of DNA Tiles

• Autorzy: Bellia, M. , Occhiuto, M. E.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

DNA Tile self assembly; aTAM model; combinatory logic; π - calculus; consensus problem

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 143, nr 1/2
• Strony: 35--49
• Opis fizyczny: Bibliogr. 24 poz., rys., tab.

Twórcy

autor

Bellia, M.

• Dipartimento di Informatica University of Pisa, Italy,

autor

Occhiuto, M. E.

• Dipartimento di Informatica University of Pisa, Italy,

Bibliografia

• [1] Rothemund PWK, Winfree E. The Program Size Complexity of Self-Assembled Squares - [Revised May 20 - 2000]. In: ACM Symposium on Theory of Computing (as Extended Abstract); 2000. p. 459–468.
• [2] Carbone A, Seeman N.C. Molecular Tiling and DNA self-assembly. In: Aspects of Molecular Computing. LNCS 2950; 2004. p. 6183.
• [3] Patitz M.J. An Introduction to Tile-Based Self-assembly. In: 11th Unconventional Computation and Natural Computation. LNCS 7445; 2012. p. 34–62.
• [4] Winfree E, Yang X, Seeman N. Universal Computation via Self-Assembly of DNA: Some Theory and Experiments. In: 2th DIMACS Meeting on DNA Based Computers. vol. 44; 1996. p. 191–214.
• [5] Demaine E.D, Demaine M.L, Fekete S.P, Patitz M.J, Schweller R.T, Winslow A, et al. One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece. Technical report, arXiv:1212.4756 [cs.DS], 2012. In: ICALP; 2014. p. 368–379.
• [6] Mo D, Stefanovic D. Iterative Self-Assembly with Dynamic Strength Transformation and Temperature Control. In: DNA Computing and Molecular Programming: 19th International Conference. LNCS 8141; 2013. p. 123–140.
• [7] Wang H. Proving Theorems by Pattern Recognition - II. Bell Systems Technical Journal. 1961;40.
• [8] Wang H. Dominoes and the AEA case of the Decision Problem. In: Symp. on Mathematical Theory of Automata; 1963. p. 23–55.
• [9] Winfree E. Simulations of Computing by Self-Assembly. In: 4th DIMACS Meeting on DNA Based Computer; 1998. .
• [10] Doty D. Theory of Algorithmic Self-Assembly. Comm ACM. 2012;55(12).
• [11] Doty D, Patitz M.J. A domain-specific language for programming in the tile assembly model. In: Proceedings of DNA; 2009. p. 2534.
• [12] Belia M, Occhiuto M.E. DNA Tiles, Wang Tiles and Combinators. In: Proc. of CS&P’2013. CEUR vol.1032; 2013. p. 114.
• [13] Rothemund P.W.K, Papadakis N,Winfree E. Algorithmic Self-Assembly of DNA Sierpinski Triangles. PLOS Biology. 2004;2(12):2041–2053.
• [14] Chen Y.J, et al. Programmable Chemical Controllers made from DNA. Nature Nanotechnology. 2013;8:755–762.
• [15] Angluin D, Aspnes J, Eisenstat D. A simple population protocol for fast robust approximate majority. Distributed Computing. 2008;21:87–102.
• [16] Milner R, Parrow J, Walker D. A Calculus of Mobile Processes, I-II. Information and Computation. 1992;100:1–77.
• [17] Jonoska N, Seeman N.C. Computing by Molecular Self-Assembly. Interface Focus. 2012;2:504–511.
• [18] Douglas S.M, Bachelet I, Church G.M. A Logic-Gated Nanorobot for Targeted Transport of Molecular Payloads. Science. 2012;335(6070):831–834.
• [19] Hopcroft J, Motwani R, Ullman J. Introduction to Automata Theory, Languages, and Computation. 2nd ed. AddisonWesley, Higher Education; 2003.
• [20] Winfree E, Liu F, Wenzler L.A, Seeman NC. Design and Self-Assembly of Two-Dimensional DNA Crystals. Nature. 1998;394:539–544.
• [21] Neary T, Woods D. Four Small Universal Turing Mchines. Fundamenta Informaticae. 2009;91:105–126.
• [22] Lee H, et al. Molecularly Self-Assembled Nucleic Acid Nanoparticles for Targeted In Vivo siRNA Delivery. Nat Nano. 2012;7(6):389–393.
• [23] Zhu G, et al. Self-assembled, Aptamer-tethered DNA Nanotrains for Targeted Transport of Molecular Drugs in Cancer Theranostic. PNAS. 2013;110(20):7998–8003.
• [24] Soloveichik D, Seelig G, Winfree E. DNA as a universal substrate for chemical kinetics. PNAS. 2010;107(12):5393–5398.

Identyfikatory

DOI

10.3233/FI-2016-1302