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

J. Ellis-Monaghan; G. Pangborn

Mathematical Modelling of Natural Phenomena (2011)

- Volume: 6, Issue: 6, page 96-107
- ISSN: 0973-5348

## Access Full Article

top## Abstract

top## How to cite

topEllis-Monaghan, J., and Pangborn, G.. "Using DNA Self-assembly Design Strategies to Motivate Graph Theory Concepts." Mathematical Modelling of Natural Phenomena 6.6 (2011): 96-107. <http://eudml.org/doc/222368>.

@article{Ellis2011,

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.},

author = {Ellis-Monaghan, J., Pangborn, G.},

journal = {Mathematical Modelling of Natural Phenomena},

keywords = {branched junction molecules; self-assembly; DNA complexes; graphs},

language = {eng},

month = {10},

number = {6},

pages = {96-107},

publisher = {EDP Sciences},

title = {Using DNA Self-assembly Design Strategies to Motivate Graph Theory Concepts},

url = {http://eudml.org/doc/222368},

volume = {6},

year = {2011},

}

TY - JOUR

AU - Ellis-Monaghan, J.

AU - Pangborn, G.

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

JO - Mathematical Modelling of Natural Phenomena

DA - 2011/10//

PB - EDP Sciences

VL - 6

IS - 6

SP - 96

EP - 107

AB - 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.

LA - eng

KW - branched junction molecules; self-assembly; DNA complexes; graphs

UR - http://eudml.org/doc/222368

ER -

## References

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

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.