nach oben

Natural Computing

Erschienen in:

01.06.2008

Combining self-healing and proofreading in self-assembly

verfasst von: David Soloveichik, Matthew Cook, Erik Winfree

Erschienen in: Natural Computing | Ausgabe 2/2008

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Molecular self-assembly is a promising approach to bottom-up fabrication of complex structures. A major impediment to the practical use of self-assembly to create complex structures is the high rate of error under existing experimental conditions. Recent theoretical work on algorithmic self-assembly has shown that under a realistic model of tile addition and detachment, error correcting tile sets are possible that can recover from the attachment of incorrect tiles during the assembly process. An orthogonal type of error correction was recently considered as well: whether damage to a completed structure can be repaired. It was shown that such self-healing tile sets are possible. However, these tile sets are not robust to the incorporation of incorrect tiles. It remained an open question whether it is possible to create tile sets that can simultaneously resist wholesale removal of tiles and the incorporation of incorrect ones. Here we present a method for converting a tile set producing a pattern on the quarter plane into a tile set that makes the same pattern (at a larger scale) but is able to withstand both of these types of errors.

Vorheriger Artikel On the complexity of graph self-assembly in accretive systems

Nächster Artikel How crystals that sense and respond to their environments could evolve

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Some backward growth can occur as a result of insufficient attachments in a growing complex that has not been subjected to wholesale tile removal. Chen and Goel’s construction handles this type of backward growth but not the more extensive incorrect backward growth possible after tile removal.

Allowing self-assembly to start from a preexisting seed boundary as in this paper, rather than from a single seed tile as in (Winfree 2006), actually permits the use of a simpler transformation that produces a scale-up factor of just 2.

This formulation ignores the initiation free energy of hybridization, which is non-negligible. See (Winfree 1998b) for details of how this free energy can be treated, yielding a model that is formally identical, but with slightly altered physical meanings for G _mc and k _f.

Assuming f = r ₂, since r ₁ ≫ f, if a tile is added that bonds only with strength 1, it falls off very quickly as it should to obey the aTAM. Tiles attached with strength 2 stick much longer, allowing an opportunity for other tiles to attach to them. Once a tile is bonded with total strength 3, it is very unlikely to dissociate (unless surrounding tiles fall off first).

The approach here and in (Chen and Goel 2005) should be contrasted with the approach in (Winfree 1998b) where the effort is to maximize the “rate of growth” f − r ₂ while maintaining a low error rate per tile. While for the tile systems considered there, the rate of growth is indeed proportional to f − r ₂, the tile systems considered here and in (Chen and Goel 2005) can grow quickly even assuming f = r ₂. This is possible because of strong bonds that bias the assembly forward even if f = r ₂.

We use the standard asymptotic notation defined as follows: f(x) = O(g(x)) means that that there is c > 0 such that f(x) ≤ c·g(x) for large enough x. Similarly, f(x) = Ω(g(x)) means that there is c > 0 such that f(x) ≥ c·g(x) for large enough x. We write f(x) = Θ(g(x)) if f(x) = O(g(x)) and f(x) = Ω(g(x)).

The Markov inequality states that for any non-negative random variable X, Pr[X ≥ a] ≤ E[X]/a where E[X] is the expected value of X.

At the reflecting barrier the expected time to take a step is twice as large since only the forward direction is possible. However, this does not affect the asymptotic results.

See (Feller 1968) for the general form of the expected duration of 1D discrete time random walks, from which the above expression is derived.

Adleman LM, Cheng Q, Goel A, Huang M-DA (2001) Running time and program size for self-assembled squares. In ACM Symposium on theory of computing (STOC), 740–748

Aggarwal G, Cheng Q, Goldwasser MH, Kao M-Y, de Espanés PM, Schweller RT (2005) Complexities for generalized models of self-assembly. SIAM J Comput 34:1493–1515MATHCrossRefMathSciNet

Barish RD, Rothemund PWK, Winfree E (2005) Two computational primitives for algorithmic self-assembly: Copying and counting. Nano Lett 5:2586–2592CrossRef

Chen HL, Goel A (2005) Error free self-assembly using error prone tiles. In: Ferretti C, Mauri G, Zandron C (eds) DNA Computing 10, LNCS vol 3384. Berlin, Springer-Verlag, pp 62–75

Cook M, Rothemund PWK, Winfree E (2004) Self-assembled circuit patterns. In: Chen J, Reif J (eds) DNA Computing 9, LNCS vol 2943. Berlin, Springer-Verlag, pp 91–107

Feller W (1968) An introduction to probability theory and its applications, vol 1. New York, Wiley

Rothemund PWK, Papakakis N, Winfree E (2004) Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol 2:e424CrossRef

Rothemund PWK, Winfree E (2000) The program-size complexity of self-assembled squares. In: ACM symposium on theory of computing (STOC), pp 459–468

LaBean TH, Yan H, Kopatsch J, Liu F, Winfree E, Reif JH, Seeman NC (2000) Construction, analysis, ligation, and self-assembly of DNA triple crossover complexes. J Am Chem Soc 122:1848–1860CrossRef

Lagoudakis MG, LaBean TH (2000) 2-D DNA self-assembly for satisfiability. In: Winfree E, Gifford DK (eds) DNA Based Computers V, DIMACS vol 54. Providence, RI, American Mathematical Society, pp 141–154

Mao C, LaBean TH, Reif JH, Seeman NC (2000) Logical computation using algorithmic self-assembly of DNA triple-crossover molecules. Nature 407:493–496CrossRef

Mao C, Sun W, Seeman NC (1999) Designed two-dimensional DNA holliday junction arrays visualized by atomic force microscopy. J Am Chem Soc 121:5437–5443CrossRef

Reif J (1999) Local parallel biomolecular computing. In: Rubin H, Wood DH (eds) DNA Based Computers III, DIMACS vol 48. Providence, RI, American Mathematical Society, pp 217–254

Reif JH, Sahu S, Yin P (2005) Compact error-resilient computational DNA tiling assemblies. In: Ferretti C, Mauri G, Zandron C (eds) DNA Computing 10, LNCS vol 3384. Berlin, Springer-Verlag, pp 293–307

Schulman R, Winfree E (2005a) Programmable control of nucleation for algorithmic self-assembly. In: Ferretti C, Mauri G, Zandron C (eds) DNA Computing 10, LNCS vol 3384. Berlin, Springer-Verlag, pp 319–328. Extended abstract in DNA Computing 10; preprint of the full paper is cond-mat/0607317 on arXiv.org

Schulman R, Winfree E (2005b) Self-replication and evolution of DNA crystals. In: Capcarrere MS, Freitas AA, Bentley PJ, Johnson CG, Timmis J (eds) Advances in Artificial Life: 8th European Conference (ECAL), LNCS vol 3630. Berlin, Springer-Verlag, pp 734–743

Soloveichik D, Winfree E (2005) Complexity of compact proofreading for self-assembled patterns. In: DNA Computing 11. Berlin, Springer-Verlag

Soloveichik D, Winfree E (2007) Complexity of self-assembled shapes. SIAM J Comput 36:1544–1569MATHCrossRefMathSciNet

Winfree E (1996) On the computational power of DNA annealing and ligation. In: Lipton RJ, Baum E B (eds) DNA Based Computers, DIMACS vol 27. Providence, RI, American Mathematical Society, pp 199–221

Winfree E (1998a) Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology, Pasadena

Winfree E (1998b) Simulations of computing by self-assembly. Technical Report CS-TR:1998.22, Caltech

Winfree E (2006) Self-healing tile sets. In: Chen J, Jonoska N, Rozenberg G (eds) Nanotechnology: science and computation. Springer-Verlag, Berlin, pp 55–78CrossRef

Winfree E, Bekbolatov R (2004) Proofreading tile sets: error-correction for algorithmic self-assembly. In: Chen J, Reif J (eds) DNA Computing 9, LNCS vol 2943. Berlin, Springer-Verlag, pp 126–144

Winfree E, Liu F, Wenzler LA, Seeman NC (1998) Design and self-assembly of two dimensional DNA crystals. Nature 394:539–544CrossRef

Winfree E, Yang X, Seeman NC (1998) Universal computation via self-assembly of DNA: some theory and experiments. In: Landweber LF, Baum EB (eds) DNA Based Computers II, DIMACS vol 44. Providence, RI, American Mathematical Society, pp 191–213

Titel: Combining self-healing and proofreading in self-assembly
verfasst von: David Soloveichik
Matthew Cook
Erik Winfree
Publikationsdatum: 01.06.2008
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 2/2008
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-007-9036-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2008

Spiking neural P systems with extended rules: universality and languages

Foreword

On the complexity of graph self-assembly in accretive systems

Experimental implementation and analysis of a DNA computing readout method based on real-time PCR with TaqMan probes

On length-separating test tube systems

Automating the DNA computer: solving n-Variable 3-SAT problems