Dimension augmentation and combinatorial criteria for efficient error-resistant DNA self-assembly

ABSTRACT

DNA self-assembly has emerged as a rich and promising primitive for nano-technology. Experimental and analytical evidence indicates that such systems are prone to errors, and accordingly, several error-correction mechanisms have been proposed for the tile model of self-assembly. These error-correction mechanisms suffer either from high resolution loss or a large increase in the number of tile-types. In this paper, we propose dimension augmented proof-reading, a technique that uses the third dimension to do error-correction in two dimensional self-assembling systems. This involves no resolution loss in the two dimensions of interest, results in a smaller increase in the number of tile-types than previous techniques, and appears to have the same error-correction properties.

Error-correcting systems need to be analyzed in the kinetic Tile Assembly Model; such analysis involves complicated Markov Chains and is cumbersome. In this paper, we also present a set of completely combinatorial criteria that can be used to prove properties of error-correcting self-assembling systems. We illustrate these criteria by applying them to two known proof-reading systems, one of which was not previously known to work. We then use these criteria to prove the correctness of dimension augmented proof-reading applied to a self-assembling system that computes the parity of a string.

REFERENCES

• 1: 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]
• 2: G Aggarwal, Q. Cheng, M. Goldwasser, M. Kao, P. Moisset, and R. Schweller. Complexities for generalized models of self-assembly. SIAM Journal on Computing, 34:1493--1515, 2005. An extended abstract of this work appeared in the proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA), 2004, pgs 880--889.
• 3: R. Barish, P. Rothemund, and E. Winfree. Two computational primitives for algorithmic self-assembly: Copying and counting. Nano Lett., 5:2586--2592, 2005.
• 4: Y. Baryshnikov, E. Coffman, and P. Momcilovic. DNA-based computation times. In Proceedings of the Tenth International Meeting on DNA Based Computers. Milano, Italy, June 2004.
• 5: Ho-Lin Chen , Qi Cheng , Ashish Goel , Ming-Deh Huang , Pablo Moisset de Espanés, Invadable self-assembly: combining robustness with efficiency, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 6: H. Chen and A. Goel. Error free self-assembly using error prone tiles. In Ferretti et al. {11}, pages 62--75.
• 7: H. Chen, A. Goel, C. Luhrs, and E. Winfree. Self-assembling tile systems that heal from small fragments. To appear, 2007.
• 8: H. Chen, A. Goel, R. Schulman, and E. Winfree. Error correction for DNA self-assembly: Preventing facet nucleation. Proceedings of the 11th International Meeting on DNA Based Computers (short abstract), June 2005.
• 9: Q. Cheng, A. Goel, and P. Moisset. Optimal self-assembly of counters at temperature two. Proceedings of the first Conference on Foundations of nanoscience: self-assembled architectures and devices, Apr 2004.
• 10: B. Ding and N. Seeman. Operation of a DNA robot arm inserted into a 2d dna crystalline substrate. Science, 384:1583--1585, December 2006.
• 11: C. Ferretti, G. Mauri, and C. Zandron, editors. DNA Computing 10, volume LNCS 3384, Berlin Heidelberg, 2005. Springer-Verlag.
• 12: M. Lagoudakis and T. LaBean. 2-D DNA self-assembly for satisfiability. In Erik Winfree and David K. Gifford, editors, DNA Based Computers V, volume 54 of DIMACS, pages 141--154, Providence, RI, 2000. American Mathematical Society.
• 13: J. Reif, S. Sahu, and P. Yin. Compact error-resilient computational DNA tiling assemblies. In Ferretti et al. {11}, pages 293--307.
• 14: P. Rothemund. Folding DNA to create nanoscale shapes and patterns. Nature, 440:297--302, 2006.
• 15: 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]
• 16: R. Schulman and E. Winfree. Programmable control of nucleation for algorithmic self-assembly. In Ferretti et al. {11}, pages 319--328. Extended abstract; preprint of the full paper is cond.mat/0607317 on arXiv.org.
• 17: W. Sherman and N. Seeman. A precisely controlled DNA biped walking device. Nano Letters, 4:1203--1207, 2004.
• 18: J.-S. Shin and N. Pierce. A synthetic DNA walker for molecular transport. J. Am. Chem. Soc., 126:10834--10835, 2004.
• 19: D. Soloveichik and E. Winfree. Complexity of compact proofreading for self-assembled patterns. In DNA Computing 11, Berlin Heidelberg, 2005. Springer-Verlay.
• 20: Y. Tian, Y. He, Y. Chen, P. Yin, and C. Mao. A DNAzyme that walks processively and autonomously along a one-dimensional track. Angewandte Chemie, 117:4429--4432, 2005.
• 21: Erik Winfree , John J. Hopfield, Algorithmic self-assembly of dna, California Institute of Technology, Pasadena, CA, 1998
• 22: E. Winfree. personal communications. 2005.
• 23: E. Winfree. Self-healing tile sets. Nanotechnology: Science and Computation, pages 55--78, 2006.
• 24: E. Winfree and R. Bekbolatov. Proofreading tile sets: Error-correction for algorithmic self-assembly. In Junghuei Chen and John Reif, editors, DNA Computing 9, volume LNCS 2943, pages 126--144, Berlin Heidelberg, 2004. Springer-Verlag.
• 25: E. Winfree, F. Liu, L. Wenzler, and N. Seeman. Design and self-assembly of two-dimensional DNA crystals. Nature, 394:539--544, 1998.
• 26: E. Winfree, X. Yang, and N. Seeman. Universal computation via self-assembly of DNA: Some theory and experiments. In Laura F. Landweber and Eric B. Baum, editors, DNA Based Computers II, volume 44 of DIMACS, pages 191--213, Providence, RI, 1998. American Mathematical Society.
• 27: H. Yan, X. Zhang, Z. Shen, and N. Seeman. A robust DNA mechanical device controlled by hybridization topology. Nature, 415:62--65, 2002.
• 28: P. Yin, H. Yan, X. Daniel, A. Turberfield, and J. Reif. A unidirectional DNA walker moving autonomously along a linear track. Angewandte Chemie, 43:4906--4911, 2004.
• 29: 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.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Error control codes

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Design, Theory