Invadable self-assembly: combining robustness with efficiency

ABSTRACT

DNA self-assembly is emerging as a key paradigm for nano-technology, nano-computation, and several related disciplines. In nature, DNA self-assembly is often equipped with explicit mechanisms for both error prevention and error correction. For artificial self-assembly, these problems are even more important since we are interested in assembling large systems with great precision. So far, theoretical studies of DNA self-assembly have primarily focused on the efficiency of the assembly process in terms of the program size and the running time. In this paper, we perform a preliminary study of algorithms for DNA self-assembly that are both robust and efficient.Strand invasion is an important error-correction mechanism observed in several natural self-assembling systems. We first define invadable self-assemblies as self-assembling systems which can effectively use the strand invasion mechanism for error-correction. We then show that O(log² n/ log log n) tiles are sufficient to assemble an n × n square in this model. The running time of our system is Õ (n). We obtain our result by growing a counter which simulates Chinese remaindering. The running time and the program size of our invadable system are within polylogarithmic factors of known lower bounds for general systems, i.e. the efficiency penalty for obtaining robustness is small in our model. We also show how to simulate an arbitrary Turing machine using an invadable self-assembly system.

REFERENCES

• 1: L. Adleman. Towards a mathematical theory of self-assembly. Technical Report 00-722, Department of Computer Science, University of Southern California, 2000.
• 2: Leonard Adleman , Qi Cheng , Ashish Goel , Ming-Deh Huang, Running time and program size for self-assembled squares, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.740-748, July 2001, Hersonissos, Greece [doi>10.1145/380752.380881]
• 3: Len Adleman , Qi Cheng , Ashish Goel , Ming-Deh Huang , David Kempe , Pablo Moisset de Espanés , Paul Wilhelm Karl Rothemund, Combinatorial optimization problems in self-assembly, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509913]
• 4: Q. Cheng and P. Moisset de Espanes. Resolving two open problems in the self-assembly of squares. Technical Report 03-793, University of Southern California, 2003.
• 5: M. Lagoudakis and T. LaBean. 2d dna self-assembly for satisfiability. In Proceedings of the 5th DIMACS Workshop on DNA Based Computers in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 54. MIT: Cambridge, 1999.
• 6: J. Reif. Local parallel biomolecular computation. In H. Rubin, editor, Third Annual DIMACS Workshop on DNA Based Computers, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1998.
• 7: Paul Wilhelm Karl Rothemund , Leonard M. Adleman, Theory and experiments in algorithmic self-assembly, 2001
• 8: Paul W. K. Rothemund , Erik Winfree, The program-size complexity of self-assembled squares (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.459-468, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335358]
• 9: H. Wang. Proving theorems by pattern recognition ii. Bell Systems Technical Journal, 1961. 40:1--42.
• 10: E. Winfree. Personal communication.
• 11: Erik Winfree , John J. Hopfield, Algorithmic self-assembly of dna, 1998
• 12: E. Winfree, F. Liu, L. Wenzler, and N. Seeman. Design and self-assembly of two-dimensional dna crystals, 6 pages. Nature, (394):539--544, Aug 1998.
• 13: E. Winfree, X. Yang, and N. Seeman. Universal computation via self-assembly of dna: Some theory and experiments. In Proceedings of the Second Annual Meeting on DNA Based Computers. Princeton University, June 1996.
• 14: B. Yurke, A. Turberfield, A. Mills Jr, F. Simmel, and J. Neumann. A dna-fuelled molecular machine made of dna. Nature, (406):605--608, Aug 2000.