A Molecule Computing Model for Maximum Independent Set Problem Based on DNA/AuNP Conjugation

Abstract:

With the progress of DNA computing and nanotechnology, DNA/AuNP conjugation becomes an emerging interdisciplinary field. In this paper, a novel DNA computing model based on DNA/AuNP conjugation is developed to solve a maximum independent set problem (MIS). Making use of the hybridization between long DNA strands and short strands conjugated with gold nanoparticles, a series of searching process is implemented. After that, based on the number of DNA/AuNP conjugation on one DNA strand, the answer of the MIS is obtained. To verify the proposed algorithm, a simple paradigm is calculated by using the DNA computing model. In this model, there are some significant advantages such as easy detecting, and controllable automation. This work may demonstrate that DNA computing has the great potentiality in huge parallelism computation.

• Periodical: Advanced Materials Research (Volumes 690-693)
• Pages: 445-449
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.690-693.445
• Online since: May 2013
• Authors: Jing Yang, Cheng Zhang, Hao Wang
• Keywords: DNA Computing, DNA/AuNP Conjugation, Gel Electrophoresis, Maximum Independent Set Problem

References

[1] L. M. Adleman: Science Vol. 266 (1994), p.1021

[2] J. Yang, C. Zhang, J. Xu, et al. Sci China Ser F-Inf. Sci. Vol. 53 (2010), p.1409

[3] Jong-Shik Shin, N. A. Pierce: Nano Letters Vol. 4 (2004), p.905

[4] C. T. Celland, V. Risca, C. Bancroft: Nature Vol. 399 (1999), p.533

[5] A. Leier, C. Richter, W. Banzhaf, et al. Biosystems Vol. 57 (2000), p.13

[6] Q. Ouyang, P. D. Kaplan, S. Liu, A. Libchaber: Science Vol. 278 (1997), p.446

[7] R. Braich, N. Chelyapov, C. Johnson, et al. Science Vol. 296 (2002), p.499

[8] J. Xu, X. L. Qiang, G. Fang, K. Zhou: Chinese Sci. Bull. Vol. 51 (2006), p.2541

[9] X. Wang, Z. Bao, J. Hu, et al. BioSystems Vol. 91 (2008), p.117

[10] T. Head, G. Rozenberg, R. S. Bladergroen, et al. Biosystems Vol. 57 (2000), p.87

[11] R. P. Goodman: Nature nanotechnology Vol. 3 (2008), p.93

[12] C. Zhang, J. Yang, J. Xu: Langmuir Vol. 26 (2010), p.1416

[13] L. Qian, E. Winfree: Science Vol. 332 (2011), p.1196

[14] Gregor Heiss, Vidmantes Lapiene, Florian Kukolka, et al. Small Vol. 5(2009), p.1169

[15] S. R. Shin, K. S. Jin, C. K. Lee, et al. Adv. Mater. Vol. 21 (2009), p. (1907)

[16] B. Chakraborty, R. Sha, and N. C. Seeman: Proc. Natl. Acad. Sci. USA, Vol. 45(2008), p.17245

[17] C. Mao, T. H. LaBean, J. H. Reif, N. C. Seeman: Nature Vol. 407 (2000), p.493

[18] C. Zhang, J. Yang, J. Xu: Chinese Sci. Bull. Vol. 56 (2011), p.3566