A Caltech Library Service

Diverse and robust molecular algorithms using reprogrammable DNA self-assembly

Woods, Damien and Doty, David and Myhrvold, Cameron and Hui, Joy and Zhou, Felix and Yin, Peng and Winfree, Erik (2019) Diverse and robust molecular algorithms using reprogrammable DNA self-assembly. Nature, 567 (3). pp. 366-372. ISSN 0028-0836.

[img] PDF (Supplementary Information) - Supplemental Material
See Usage Policy.

[img] PDF (Supplementary Data) - Supplemental Material
See Usage Policy.

[img] PDF (Supplementary Figures) - Supplemental Material
See Usage Policy.


Use this Persistent URL to link to this item:


Molecular biology provides an inspiring proof-of-principle that chemical systems can store and process information to direct molecular activities such as the fabrication of complex structures from molecular components. To develop information-based chemistry as a technology for programming matter to function in ways not seen in biological systems, it is necessary to understand how molecular interactions can encode and execute algorithms. The self-assembly of relatively simple units into complex products is particularly well suited for such investigations. Theory that combines mathematical tiling and statistical–mechanical models of molecular crystallization has shown that algorithmic behaviour can be embedded within molecular self-assembly processes, and this has been experimentally demonstrated using DNA nanotechnology with up to 22 tile types. However, many information technologies exhibit a complexity threshold—such as the minimum transistor count needed for a general-purpose computer—beyond which the power of a reprogrammable system increases qualitatively, and it has been unclear whether the biophysics of DNA self-assembly allows that threshold to be exceeded. Here we report the design and experimental validation of a DNA tile set that contains 355 single-stranded tiles and can, through simple tile selection, be reprogrammed to implement a wide variety of 6-bit algorithms. We use this set to construct 21 circuits that execute algorithms including copying, sorting, recognizing palindromes and multiples of 3, random walking, obtaining an unbiased choice from a biased random source, electing a leader, simulating cellular automata, generating deterministic and randomized patterns, and counting to 63, with an overall per-tile error rate of less than 1 in 3,000. These findings suggest that molecular self-assembly could be a reliable algorithmic component within programmable chemical systems. The development of molecular machines that are reprogrammable—at a high level of abstraction and thus without requiring knowledge of the underlying physics—will establish a creative space in which molecular programmers can flourish.

Item Type:Article
Related URLs:
URLURL TypeDescription ReadCube access Correction ReadCube access - Author Correction
Doty, David0000-0002-3922-172X
Winfree, Erik0000-0002-5899-7523
Additional Information:© 2019 Springer Nature Publishing AG. Received 22 May 2018; Accepted 07 January 2019; Published 20 March 2019; Issue Date 21 March 2019. We thank C. Evans, A. Gopinath, B. Wei, C. Geary, S. Woo, P. Rothemund and Y. Rondelez for experimental advice; R. Barish for contributing to preliminary designs for algorithmic self-assembly by SST; C. Moore, T. Stérin, C. Thachuk, P.-É. Meunier and C. Geary for discussions on theory; and L. Qian, G. Tikhomirov and P. Petersen for AFM usage. This work was supported by National Science Foundation (NSF) grants CCF-1162589 (to E.W., D.D. and D.W.), CCF-1162459 (to P.Y.), CCF-1219274 (to D.W. and D.D.), CCF-1619343 (to D.D.), CCF-0832824 and CCF-1317694 (Expeditions in Computing, to E.W.) and CCF-1317291 (Expeditions in Computing, to P.Y.), and by NASA grant NNX13AJ56G (to D.W.). C.M. was funded by the Fannie and John Hertz Foundation. F.Z. and J.H. received support from the Caltech Summer Undergraduate Research Fellowship program. Author Contributions: D.W., D.D., E.W. and P.Y. conceived the study. D.W., D.D. and E.W. designed the circuits and wrote the manuscript. D.W. and D.D. carried out all data analysis and experiments reported except for the nanotube nucleation/melt experiments (which were performed by J.H. and D.W.) and the unzipping and other early experimental protocols (performed by F.Z., C.M. and D.D.). Competing interests: D.W., D.D., J.H., F.Z. and E.W. declare that they have no competing interests. P.Y. and C.M. declare competing interests: they are both listed as inventors on pending and issued patents on single-stranded tiles; and P.Y. is a co-founder of Ultivue Inc. and NuProbe Global.
Errata:In Fig. 1 of this Letter, prime symbols were erroneously included in some labels in panels c and d. In the bottom section of panel c, in the diagram beneath ‘SST self-assembly’, the labels w2a′, w3a′, w4a′ and w5a′ should read w2a, w3a, w4a and w5a, respectively. Similarly, in panel d, the labels w2a′ and w3a′ should read w2a and w3a, respectively. Additionally, there were some omissions in the Acknowledgements: R. Schulman should have been thanked for experimental advice, and R. Hariadi for contributing to preliminary designs for algorithmic self-assembly by SST. Finally, in Supplementary Figs. 8 and 9, the rightmost labels s should read s′, and on page 64 of the Supplementary Information a citation to Telser et al. (1989) was missing and has been added as ref. 89; the subsequent citations have been renumbered. The Supplementary Information has been updated accordingly, and minor changes have also been made to the phrasing throughout to improve clarity. The original, incorrect version of the Supplementary Information is included as Supplementary Information to this Amendment, for transparency. The original Letter has been corrected online.
Funding AgencyGrant Number
Fannie and John Hertz FoundationUNSPECIFIED
Caltech Summer Undergraduate Research Fellowship (SURF)UNSPECIFIED
Subject Keywords:Computer science; DNA computing
Issue or Number:3
Record Number:CaltechAUTHORS:20181211-124932769
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:91684
Deposited By: George Porter
Deposited On:20 Mar 2019 18:01
Last Modified:25 Feb 2020 00:40

Repository Staff Only: item control page