Geodesic
Using DNA Self-assembly Design Strategies to Motivate Graph Theory Concepts
J. Ellis-Monaghan1 ; G. Pangborn2
1 Department of Mathematics, Saint Michael’s College, Colchester, VT 05404
2 Department of Computer Science, Saint Michael’s College, Colchester, VT 05404
Mathematical modelling of natural phenomena, Tome 6 (2011) no. 6, pp. 96-107

Voir la notice de l'article provenant de la source EDP Sciences

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.
DOI : 10.1051/mmnp/20116606

J. Ellis-Monaghan 1 ; G. Pangborn 2

1 Department of Mathematics, Saint Michael’s College, Colchester, VT 05404
2 Department of Computer Science, Saint Michael’s College, Colchester, VT 05404 
@article{10_1051_mmnp_20116606,
     author = {J. Ellis-Monaghan and G. Pangborn},
     title = {Using {DNA} {Self-assembly} {Design} {Strategies} to {Motivate} {Graph} {Theory} {Concepts}},
     journal = {Mathematical modelling of natural phenomena},
     pages = {96--107},
     publisher = {mathdoc},
     volume = {6},
     number = {6},
     year = {2011},
     doi = {10.1051/mmnp/20116606},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/mmnp/20116606/}
}
TY  - JOUR
AU  - J. Ellis-Monaghan
AU  - G. Pangborn
TI  - Using DNA Self-assembly Design Strategies to Motivate Graph Theory Concepts
JO  - Mathematical modelling of natural phenomena
PY  - 2011
SP  - 96
EP  - 107
VL  - 6
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1051/mmnp/20116606/
DO  - 10.1051/mmnp/20116606
LA  - en
ID  - 10_1051_mmnp_20116606
ER  - 
%0 Journal Article
%A J. Ellis-Monaghan
%A G. Pangborn
%T Using DNA Self-assembly Design Strategies to Motivate Graph Theory Concepts
%J Mathematical modelling of natural phenomena
%D 2011
%P 96-107
%V 6
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1051/mmnp/20116606/
%R 10.1051/mmnp/20116606
%G en
%F 10_1051_mmnp_20116606
J. Ellis-Monaghan; G. Pangborn. Using DNA Self-assembly Design Strategies to Motivate Graph Theory Concepts. Mathematical modelling of natural phenomena, Tome 6 (2011) no. 6, pp. 96-107. doi: 10.1051/mmnp/20116606

[1] L. Adleman Science 1994 1021 1024

[2] J. Chen, N. Seeman Nature 1991 631 633

[3] H. Dietz, S. Douglas, W. Shih Science 2009 725 730

[4] J. Ellis-Monaghan Congressus Numerantium 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 J. Phys. Chem. B 2005 9839 9842

[7] M. Furst, G. Gross, L. Mcgeoch J. Assoc. Comput. Mach. 1988 523 534

[8] J. Girard, A. Gilbert, D. Lewis, M. Spuches American Journal of Undergraduate Research 2011 15 32

[9] Y. He, T. Ye, M. Su, C. Zhuang, A. Ribbe, W. Jiang, C. Mao Nature 2008 198 202

[10] B. Hogberg, T. Liedl, W. Shih J. Am. Chem. Soc. 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 Theoretical Computer Science 2009 1448 1460

[13] T. Labean, H. Li Nano Today 2007 26 35

[14] B. Landfraf. Drawing Graphs Methods and Models. Springer-Verlag, 2001, ch. 3D Graph Drawing, 172–192.

[15] D. Luo Materials Today 2003 38 43

[16] P. Rothemund Nature 2006 297 302

[17] N. Seeman Scientific American 2004 64 75

[18] N. Seeman Mol. Biotechnol. 2007 246 257

[19] W. Shih, J. Quispe, G. Joyce Nature 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 J. Algorithms 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 Science 2003 1882 1884

[24] Y. Zhang, N. Seeman J. Am. Chem. Soc. 1994 1661 1669

[25] J. Zheng, J. Birktoft, Y. Chen, T. Wang, R. Sha, P. Constantinou, S. Ginell, C. Mao, N. Seeman Nature 2009 74 77

Cité par Sources :