A Molecule Computing Model for Maximum Independent Set Problem Based on DNA/AuNP Conjugation
A Molecule Computing Model for Maximum Independent Set Problem Based on DNA/AuNP Conjugation
复制标题
DOI：
10.4028/www.scientific.net/amr.690-693.445
复制
发表时间：
2013-05
期刊：
影响因子：
--
通讯作者：
Jing Yang;Cheng Zhang;Hao Wang
中科院分区：
文献类型：
--
作者：
Jing Yang;Cheng Zhang;Hao Wang
随着DNA计算和纳米技术的发展，DNA/AuNP偶联成为一个新兴的交叉学科领域。本文提出了一种基于DNA/AuNP共轭的DNA计算模型来求解最大独立集问题（MIS）。利用金纳米粒子与DNA长链和短链的杂交，实现了一系列的搜索过程。之后，基于一条DNA链上的DNA/AuNP缀合的数目，获得MIS的答案。为了验证所提出的算法，一个简单的范例计算使用DNA计算模型。该模型具有检测方便、自动化程度可控等显著优点。这一工作表明DNA计算在大规模并行计算中具有巨大的潜力。
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.