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

Abstract

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

How to cite

top

Ellis-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
  1. L. Adleman. Molecular computation to solutions of combinatorial problems. Science, 266 (1994), 1021–1024.  
  2. J. Chen, N. Seeman. Synthesis from DNA of a molecule with the connectivity of a cube. Nature, 350 (1991), 631–633.  
  3. H. Dietz, S. Douglas, W. Shih. Folding DNA into twisted and curved nanoscale shapes. Science, 325 (2009), 725–730.  
  4. J. Ellis-Monaghan. Transition polynomials, double covers, and biomolecular computing. Congressus Numerantium, 166 (2004), 181–192.  
  5. 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.  
  6. 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.  
  7. M. Furst, G. Gross, L. McGeoch. Finding a maximum-genus graph imbedding. J. Assoc. Comput. Mach., 35 (1988), 523–534.  
  8. J. Girard, A. Gilbert, D. Lewis, M. Spuches. Design optimization for DNA nanostructures. American Journal of Undergraduate Research, 9, no. 4 (2011), 15–32.  
  9. 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.  
  10. B. Hogberg, T. Liedl, W. Shih. Folding DNA origami from a double-stranded source of scaffold. J. Am. Chem. Soc., 131 (2009), 9154–9155.  
  11. N. Jonoska, G. McColm, A. Staninska. Spectrum of a pot for DNA complexes. In DNA, 2006, 83–94.  
  12. N. Jonoska, N. Seeman, G. Wu. On existence of reporter strands in DNA-based graph structures. Theoretical Computer Science, 410 (2009), 1448–1460.  
  13. T. LaBean, H. Li. Constructing novel materials with DNA. Nano Today, 2 (2007), 26–35.  
  14. B. Landfraf. Drawing Graphs Methods and Models. Springer-Verlag, 2001, ch. 3D Graph Drawing, 172–192.  
  15. D. Luo. The road from biology to materials. Materials Today, 6 (2003), 38–43.  
  16. P. Rothemund. Folding DNA to create nanoscale shapes and patterns. Nature, 440 (2006), 297–302.  
  17. N. Seeman. Nanotechnology and the double helix. Scientific American, 290 (2004), 64–75.  
  18. N. Seeman. An overview of structural DNA nanotechnology. Mol. Biotechnol., 37 (2007), 246–257.  
  19. W. Shih, J. Quispe, G. Joyce. A 1.7 kilobase single-stranded DNA that folds into a nanoscale octahedron. Nature, 427 (2004), 618–621.  
  20. 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.  
  21. C. Thomassen. The graph genus problem is NP-complete. J. Algorithms, 10 (1989), 568–576.  
  22. D. West. Introduction to Graph Theory. Prentice-Hall, Englewood Cliffs, NJ, 2000.  
  23. 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.  
  24. Y. Zhang, N. Seeman. Construction of a DNA-truncated octahedron. J. Am. Chem. Soc., 116 (1994), 1661–1669.  
  25. 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.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.