«Abstract. DNA self-assembly is emerging as a key paradigm for nano-technology, nano-computation, and several related disciplines. In nature, DNA ...»
Also, for the 2 × 2 snaked tile system and the original proofreading system, we took a straight line boundary of 200 tiles and tested the average time (in seconds; virtual time) for a block error to happen under different Gse ’s. Here, 2Gse − Gmc is set to be 0.2. Theoretically, the expected time for a block error to happen in the snaked tile system is O(e4Gse ), and the expected time for a block error to happen in the proofreading system is O(e3Gse ). The result is shown in ﬁgure 5(a); the y-axis uses a log-scale. Clearly, Gmc = 15, Gse = 7.8 Gmc = 15, Gse = 8.0 Original Proofreading Snaked Original Proofreading Snaked Time to assemble (seconds) 550 2230 6020 350 1750 3780 Error Probability 52% 24% 0% 63% 75% 0% Time it remains stable 0 0 0 0 5700 (seconds) after completion Table 1: Assembling a 20 × 20 Sierpinski block. A stability time of 0 indicates that the ﬁnal square became unstable (i.e., an extra block of tiles attached on the periphery of the desired supertile) even before the complete supertile formed. We only simulated our system for 400,000 seconds (virtual time). The values represent averages over 100 runs.
the slope of the curve for the snaked tile system conﬁrms our analysis – the slope is very close to 4, and signiﬁcantly more than the slope for the original proofreading system. For the larger values of G se, we could only plot the results for the original proof-reading system, since the simulator did not report any errors with the snaked tile system for the time scales over which we conducted the simulation.
We also tested the error rate for parity systems of different seed lengths. We called an experiment an error if the ﬁnal supertile was different from the one we expect in the absence of errors. We used Gse = 7.0, Gmc = 13.6. The result is shown in ﬁgure 5(b); again, a signiﬁcant reduction in error rate is observed. For both ﬁgures 5(a) and 5(b), qualitatively similar results were observed for widely varying simulation parameters.
Our simulation results show that our analysis is very close to reality even without idealized parameter conditions. For example, we did not use Gmc = 2Gse but instead used Gmc slightly smaller than 2Gse as suggested by Winfree . Also, the simulator allows tiles held by strength 3 to fall off, contrary to our assumption. Thus, we believe that our snaked system works much better (and under a much wider set of conditions) than we have been able to formally prove.
5 Future Directions It would be interesting to extend our analysis to remove some of our assumptions. Also, we believe that the total assembly time for our system should just be O(k 2 n) for assembling an n × n square using k × k snaked blocks. One of the biggest bottlenecks in proving this bound is an analysis of the assembly time of an n × n square assuming that there are no errors but that the system is reversible, i.e., tiles can both attach and detach. We believe that the assembly time for this system should be O(n) along the lines of the irreversible system , but have been unable to prove it.
Acknowledgments We would like to thank Qi Cheng and Erik Winfree for many useful discussions. We would also like to thank Erik Winfree for loaning us his tile simulator, xgrow, which was an indispensable aid in this research.
References  L. Adleman. Towards a mathematical theory of self-assembly. Technical Report 00-722, Department of Computer Science, University of Southern California, 2000.
 L. Adleman, Q. Cheng, A. Goel, and M.-D. Huang. Running time and program size for self-assembled squares. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 740–748. ACM Press, 2001.
 L. Adleman, Q. Cheng, A. Goel, M.-D. Huang, D. Kempe, P. Moisset de Espans, and P. Rothemund.
Combinatorial optimization problems in self-assembly. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 23–32. ACM Press, 2002.
 H. Chen, Q. Cheng, A. Goel, M.-D. Huang, and P. Moisset de Espans. Proofreading tile sets: Error correction for algorithmic self-assembly. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 883–892, 2004.
 M. Lagoudakis and T. LaBean. 2D DNA self-assembly for satisﬁability. 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.
 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.
 P. Rothemund. Theory and Experiments in Algorithmic Self-Assembly. PhD thesis, University of Southern California, 2001.
 P. Rothemund and E. Winfree. The program-size complexity of self-assembled squares (extended abstract). In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 459–468. ACM Press, 2000.
 H. Wang. Proving theorems by pattern recognition II. Bell Systems Technical Journal, 1961. 40:1-42.
 E. Winfree. Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology, Pasadena, 1998.
 E. Winfree and R. Bekbolatov. Proofreading tile sets: Error correction for algorithmic self-assembly.
In Proceedings of the Ninth International Meeting on DNA Based Computers. Madison, Wisconsin, June 2003.
 E. Winfree, F. Liu, L. Wenzler, and N. Seeman. Design and self-assembly of two-dimensional DNA crystals. Nature, (394):539–544, Aug 1998.
 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.
 E. Winfree et al.. The xgrow simulator. http://www.dna.caltech.edu/Xgrow/xgrow www.html.
 B. Yurke, A. Turberﬁeld, A. Mills Jr, F. Simmel, and J. Neumann. A DNA-fuelled molecular machine made of DNA. Nature, (406):605–608, Aug 2000.