A molecule computing model for maximum independent set problem based on DNA/AuNP conjugation

作者：Yang, Jing; Zhang, Cheng; Wang, Hao

来源：4th International Conference on Manufacturing Science and Engineering, ICMSE 2013, China,Shaanxi,Weinan,Dali, 2013-03-30 to 2013-03-31.

DOI：10.4028/www.scientific.net/AMR.690-693.445

• Computing model
• DNA computing model
• DNA strands
• DNA-computing
• Gel electrophoresis
• Gold Nanoparticles
• Interdisciplinary fields
• Maximum independent sets

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.

• 出版日期2013
• 单位华北电力大学; 北京大学