基于自组装纳米颗粒的顶点着色问题的DNA计算模型  

DNA Computing Model Based on Self-assembled Nanoparticle Solving Vertex Coloring Problem

作　　者：陈芳 殷志祥 CHEN Fang;YIN Zhixiang(School of Mathematics and Big Data,Anhui University of Science and Technology,Huainan 232001)

机构地区：[1]安徽理工大学数学与大数据学院,淮南232001

出　　处：《长春理工大学学报（自然科学版）》2018年第4期123-126,131,共5页Journal of Changchun University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金(61672001;61702008)

摘　　要：自组装纳米颗粒由于其特殊的结构,具有较好的稳定性,广泛应用于DNA计算中,使用DNA自组装模型可以有效减少运算的复杂度。文章利用自组装纳米金属颗粒求解了图的顶点着色问题。首先,将图的顶点进行自组装设计;其次,根据顶点构造相应的连接探针,二者通过碱基互补配对自动生成初始数据池;最后,利用特殊结构的删除探针对数据池中的方案进行筛选,结合凝胶电泳得到满足条件的解。该模型无需对DNA片段进行编码,操作简单,在检测解时无需酶的参与,降低了复杂度,提高了运算效率。Self-assembled nanoparticle has been widely used in DNA computing because of its special structure and good stability. The computational complexity can be reduced effectively by using DNA self-assembly model. In this paper,the problem of vertex coloring is solved by using self-assembled metal nanoparticles. Firstly,the vertices of the graph are self-assembled and designed. Secondly,the corresponding ligation probes are constructed according to the vertices;and the initial datasets are generated automatically by base-pairing pairing. Finally,a special structure deletion probe is used to screen the solution in the data pool,and the solution satisfying the condition is obtained by using gel electrophoresis. The model does not need to encode the DNA fragments,and the operation is simple. No enzyme is involved in the detection of the solution,which reduces the complexity and improves the operation efficiency.

关 键 词：DNA计算 自组装 纳米颗粒 顶点着色问题 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]