skip to main content
10.5555/1347082.1347127acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article

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

Published: 20 January 2008 Publication History

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]
L. Adleman, Q. Cheng, A. Goel, and M. Huang. Running time and program size for self-assembled squares. In ACM Symposium on Theory of Computing, pages 740--748, 2001.
[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]
H. Chen, Q. Cheng, A. Goel, M. Huang, and P. Moisset. Invadable self-assembly: Combining robustness with efficiency. ACM-SIAM Symposium on Discrete Algorithms (SODA), to appear, 2004.
[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]
P. Rothemund and E. Winfree. The program-size complexity of self-assembled squares. In Symposium on Theory of Computing (STOC), pages 459--468, Portland, Oregon, United States, May 2000. ACM Press.
[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]
E. Winfree. Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology, Computation and Neural Systems Option, 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.

Cited By

View all
  • (2012)Theory of algorithmic self-assemblyCommunications of the ACM10.1145/2380656.238067555:12(78-88)Online publication date: 1-Dec-2012
  • (2011)Temperature 1 self-assemblyProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133081(570-589)Online publication date: 23-Jan-2011
  • (2010)A molecular solution to the hitting-set problem in DNA-based supercomputingInformation Sciences: an International Journal10.1016/j.ins.2009.11.019180:6(1010-1019)Online publication date: 1-Mar-2010

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms
January 2008
1289 pages
  • Program Chair:
  • Shang-Hua Teng

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 20 January 2008

Check for updates

Qualifiers

  • Research-article

Conference

SODA08
Sponsor:
SODA08: 19th ACM-SIAM Symposium on Discrete Algorithms
January 20 - 22, 2008
California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 17 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2012)Theory of algorithmic self-assemblyCommunications of the ACM10.1145/2380656.238067555:12(78-88)Online publication date: 1-Dec-2012
  • (2011)Temperature 1 self-assemblyProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133081(570-589)Online publication date: 23-Jan-2011
  • (2010)A molecular solution to the hitting-set problem in DNA-based supercomputingInformation Sciences: an International Journal10.1016/j.ins.2009.11.019180:6(1010-1019)Online publication date: 1-Mar-2010

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media