Skip to main content
SpringerLink
Log in

Computation by Self-assembly of DNA Graphs

  • Published:
Genetic Programming and Evolvable Machines Aims and scope Submit manuscript

Abstract

Using three dimensional graph structure and DNA self-assembly we show that theoretically 3-SAT and 3-colorability can be solved in a constant number of laboratory steps. In this assembly, junction molecules and duplex DNA molecules are the basic building blocks. The graphs involved are not necessarily regular, so experimental results of self-assembling non regular graphs using junction molecules as vertices and duplex DNA molecules as edge connections are presented.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R. S. Braich, N. Chelyapov, C. Johnson, P. W. K. Rothemund, and L. Adleman, “Solution of a 20-variable 3-SAT problem on a DNA computer” Science Express, March 14, 2002.

  2. J. H. Chen and N. C. Seeman, “Synthesis from DNA of a molecule with the connectivity of a cube,” Nature, vol. 350, pp. 631-633, 1991.

    Article  Google Scholar 

  3. J. H. Chen, N. R. Kallenbach, and N. C. Seeman, “A specific quadrilateral synthesized from DNA branched junctions,” J. Am. Chem. Soc., vol. 111, pp. 6402-6407, 1989.

    Article  Google Scholar 

  4. U. Feldkamp, S. Saghafi, and H. Rauhe, “DNASequenceGenerator: A program for the construction of DNA sequences,” DNA Computing: Proceedings of the 7th International Meeting on DNA Based Computers, N. Jonoska and N. C. Seeman (eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 54, Springer LNCS: 2002, pp. 23-32.

  5. T. Head, “Formal language theory and DNA: an analysis of generative capacity of recombinant behaviours,” Bul. of Mathematical Biology, vol. 49, pp. 735-759, 1987.

    MathSciNet  Google Scholar 

  6. N. Jonoska, S. Karl, and M. Saito, “Creating 3-dimensional graph structures with DNA,” DNA computers III, H. Rubin and D. Wood (eds.), AMS DIMACS series, vol. 48, pp. 123-135, 1999.

  7. N. Jonoska, S. Karl, and M. Saito, “Three dimensional DNA structures in computing,” BioSystems, vol. 52, pp. 143-153, 1999.

    Article  Google Scholar 

  8. N. Jonoska and M. Saito, “Boundary components of thickened graphs,” DNA Computing: Proceedings of the 7th International Meeting on DNA Based Computers, N. Jonoska and N. C. Seeman (eds.), Springer LNCS, vol. 340, 2002, pp. 70-81.

  9. C. Mao, T. H. LaBean, J. H. Reif, and N. C. Seecyman, “Logical computation using algorithmic self-assembly of DNA triple-crossover molecules,” Nature, vol. 407, pp. 493-496, 2000.

    Article  Google Scholar 

  10. J. H. Reif, “Local parallel biomolecular computation,” DNA Computers III AMS DIMACS series, H. Rubin and D. H. Wood (eds.), 1999, pp. 217-254.

  11. Y. Sakakibara and C. Ferretti, “Splicing on tree-like structures,” DNA computers III, H. Rubin and D. H. Wood (eds.), AMS DIMACS series, vol. 48, 1999, pp. 361-275.

  12. N. C. Seeman, “De novo design of sequences for nucleic acid structural engineering,” J. of Biomolecular Structure & Dynamics, vol. 8,no. 3, pp. 573-581, 1990.

    Google Scholar 

  13. N. C. Seeman and N. R. Kallenbach, “Nucleic acid junctions: a successful experiment in macromolecular design, in Molecular Structure,” Chemical Reactivity and Biological Activity, J. J. Stezowski, J. L. Huang, and M. C. Shao (eds.), Oxford Univ. Press: Oxford, 1988, pp. 189-194.

    Google Scholar 

  14. H. Uejima, M. Hagiya, and S. Kobayashi, “Horn clause computation by self-assembly of DNA molecules,” DNA Computing: Proceedings of the 7th International Meeting on DNA Based Computers, N. Jonoska and N. C. Seeman (eds.), Springer LNCS, vol. 2340, 2002, pp. 308-320.

  15. S. A. Wasserman and N. R. Cozzarelli, “Biochemical topology: applications to DNA recombination and replication,” Science, vol. 232, pp. 951-960, 1986.

    Google Scholar 

  16. E. Winfree, X. Yang, and N. C. Seeman, “Universal computation via self-assembly of DNA: some theory and experiments,” DNA computers II, L. Landweber and E. Baum (eds.), AMS DIMACS series, vol. 44, 1998, pp. 191-214.

  17. E. Winfree, F. Liu, L. A. Wenzler, and N. C. Seeman, “Design and self-assembly of two-dimensional DNA crystals,” Nature, vol. 394, pp. 539-544, 1998.

    Article  Google Scholar 

  18. Y. Zhang and N. C. Seeman, “The construction of a DNA truncated octahedron,” J. Am. Chem. Soc., vol. 160, pp. 1661-1669, 1994.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of South Florida, Tampa, FL, 33620, USA

    NataŠa Jonoska

  2. Department of Chemistry, New York University, New York, NY, 10003, USA

    Phiset Sa-Ardyen & Nadrian C. Seeman

Authors
  1. NataŠa Jonoska
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Phiset Sa-Ardyen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nadrian C. Seeman
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Jonoska, N., Sa-Ardyen, P. & Seeman, N.C. Computation by Self-assembly of DNA Graphs. Genet Program Evolvable Mach 4, 123–137 (2003). https://doi.org/10.1023/A:1023980828489

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1023980828489

Search

Navigation