Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-26T17:14:13.120Z Has data issue: false hasContentIssue false
  • English
  • Français

Using DNA Self-assembly Design Strategies to Motivate Graph Theory Concepts

Published online by Cambridge University Press:  05 October 2011

J. Ellis-Monaghan  and
G. Pangborn
J. Ellis-Monaghan*
Affiliation:
Department of Mathematics, Saint Michael’s College, Colchester, VT 05404
G. Pangborn
Affiliation:
Department of Computer Science, Saint Michael’s College, Colchester, VT 05404
*
⋆Corresponding author. E-mail: [email protected]
Get access

Abstract

A number of exciting new laboratory techniques have been developed using the Watson-Crick complementarity properties of DNA strands to achieve the self-assembly of graphical complexes. For all of these methods, an essential step in building the self-assembling nanostructure is designing the component molecular building blocks. These design strategy problems fall naturally into the realm of graph theory. We describe graph theoretical formalism for various construction methods, and then suggest several graph theory exercises to introduce this application into a standard undergraduate graph theory class. This application provides a natural framework for motivating central concepts such as degree sequence, Eulerian graphs, Fleury’s algorithm, trees, graph genus, paths, cycles, etc. There are many open questions associated with these applications which are accessible to students and offer the possibility of exciting undergraduate research experiences in applied graph theory.

Keywords

branched junction moleculesself-assemblyDNA complexesgraphs
Type
Research Article
Information
Mathematical Modelling of Natural Phenomena , Volume 6 , Issue 6: Biomathematics Education , 2011 , pp. 96 - 107
Copyright
© EDP Sciences, 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Adleman, L.. Molecular computation to solutions of combinatorial problems. Science, 266 (1994), 1021–1024. CrossRefGoogle ScholarPubMed
Chen, J., Seeman, N.. Synthesis from DNA of a molecule with the connectivity of a cube. Nature, 350 (1991), 631–633. CrossRefGoogle ScholarPubMed
Dietz, H., Douglas, S., Shih, W.. Folding DNA into twisted and curved nanoscale shapes. Science, 325 (2009), 725–730. CrossRefGoogle ScholarPubMed
Ellis-Monaghan, J.. Transition polynomials, double covers, and biomolecular computing. Congressus Numerantium, 166 (2004), 181–192. Google Scholar
J. Ellis-Monaghan, G. Pangborn, L. Beaudin, N. Bruno, A. Hashimoto, B. Hopper, P. Jarvis, D. Miller. Minimal tile and bond-edge types for self-assembling DNA graphs. Manuscript.
Freedman, K., Lee, J., Li, Y., Luo, D., Sbokeleva, V., Ke, P.. Diffusion of single star-branched dendrimer-like DNA. J. Phys. Chem. B, 109 (2005), 9839–9842. CrossRefGoogle ScholarPubMed
Furst, M., Gross, G., McGeoch, L.. Finding a maximum-genus graph imbedding. J. Assoc. Comput. Mach., 35 (1988), 523–534. CrossRefGoogle Scholar
Girard, J., Gilbert, A., Lewis, D., Spuches, M.. Design optimization for DNA nanostructures. American Journal of Undergraduate Research, 9, no. 4 (2011), 15–32. Google Scholar
He, Y., Ye, T., Su, M., Zhuang, C., Ribbe, A., Jiang, W., Mao, C.. Hierarchical self-assembly of DNA into symmetric supramolecular polyhedra. Nature, 452 (2008), 198–202. CrossRefGoogle ScholarPubMed
Hogberg, B., Liedl, T., Shih, W.. Folding DNA origami from a double-stranded source of scaffold. J. Am. Chem. Soc., 131 (2009), 9154–9155. CrossRefGoogle Scholar
N. Jonoska, G. McColm, A. Staninska. Spectrum of a pot for DNA complexes. In DNA, 2006, 83–94.
Jonoska, N., Seeman, N., Wu, G.. On existence of reporter strands in DNA-based graph structures. Theoretical Computer Science, 410 (2009), 1448–1460. CrossRefGoogle ScholarPubMed
LaBean, T., Li, H.. Constructing novel materials with DNA. Nano Today, 2 (2007), 26–35. CrossRefGoogle Scholar
B. Landfraf. Drawing Graphs Methods and Models. Springer-Verlag, 2001, ch. 3D Graph Drawing, 172–192.
Luo, D.. The road from biology to materials. Materials Today, 6 (2003), 38–43. CrossRefGoogle Scholar
Rothemund, P.. Folding DNA to create nanoscale shapes and patterns. Nature, 440 (2006), 297–302. CrossRefGoogle ScholarPubMed
Seeman, N.. Nanotechnology and the double helix. Scientific American, 290 (2004), 64–75. CrossRefGoogle ScholarPubMed
Seeman, N.. An overview of structural DNA nanotechnology. Mol. Biotechnol., 37 (2007), 246–257. CrossRefGoogle ScholarPubMed
Shih, W., Quispe, J., Joyce, G.. A 1.7 kilobase single-stranded DNA that folds into a nanoscale octahedron. Nature, 427 (2004), 618–621. CrossRefGoogle ScholarPubMed
A. Staninska. The graph of a pot with DNA molecules. in Proceedings of the 3rd annual conference on Foundations of Nanoscience (FNANO’06), April 2006, 222–226.
Thomassen, C.. The graph genus problem is NP-complete. J. Algorithms, 10 (1989), 568–576. CrossRefGoogle Scholar
D. West. Introduction to Graph Theory. Prentice-Hall, Englewood Cliffs, NJ, 2000.
Yan, H., Park, S., Finkelstein, G., Reif, J., LaBean, T.. DNA-templated self-assembly of protein arrays and highly conductive nanowires. Science, 301 (2003), 1882–1884. CrossRefGoogle ScholarPubMed
Zhang, Y., Seeman, N.. Construction of a DNA-truncated octahedron. J. Am. Chem. Soc., 116 (1994), 1661–1669. CrossRefGoogle Scholar
Zheng, J., Birktoft, J., Chen, Y., Wang, T., Sha, R., Constantinou, P., Ginell, S., Mao, C., Seeman, N.. From molecular to macroscopic via the rational design of a self-assembled 3D DNA crystal. Nature, 461 (2009), 74–77. CrossRefGoogle ScholarPubMed