基于“DNA折纸术”设计图着色问题的解决方案  

A “DNA origami”-based approach to the solution of graph coloring problem

作　　者：俞洋[1] 苏邵[2] 晁洁[2] 

机构地区：[1]上海科技管理干部学院电子信息系,上海201800 [2]南京邮电大学材料科学与工程学院,有机电子与信息显示国家重点实验室培育基地&信息科学与纳米技术研究院,先进生物与化学制造协同创新中心(国家级2011协同创新中心),南京210023

出　　处：《南京大学学报（自然科学版）》2016年第4期656-661,共6页Journal of Nanjing University（Natural Science）

基　　金：江苏省科技厅面上项目(BK20151504);南京邮电大学人才引进项目(NY214175)

摘　　要：色数是图论中的一个重要的参数,其属于著名NP(Non-deterministic Polynomial)-完全问题范畴.巨量的着色方案使验证变得相当困难,以至于在传统计算机上无法实现.目前已经有多种算法用于研究图定点着色问题,比如遗传算法,粒子群算法,神经网络算法和模拟退火算法等.随着DNA自组装技术与DNA计算机研究的展开,一些NP-完全问题以及NP-难问题的计算模型被相继提出.除了传统的DNA分子结构被用作计算材料外,其他的DNA分子结构也被用于分子生物计算,比如质粒DNA分子、分子信标结构以及DNA Tile等.采用DNA纳米折纸结构编码信息,借助于纳米结构之间的粘性末端进行自组装,给出了一种非确定性的图着色模型.通过创建数以亿计的参与计算的DNA纳米折纸结构,该算法可以并行的测试每种可能的着色方案.In the graph theory,graph coloring is an assignment of labels which are traditionally called ＂colors＂ to elements of a graph that subject to certain constraints.Graph coloring belongs to the famous category of NP（Polynomial Non-deterministic）-complete problems.The huge coloring schemes make the verification too difficult to be achieved in traditional computers.Until now,there are many algorithms used in the study of graph coloring problem,such as genetic algorithm,particle swarm optimization algorithm,neural network algorithm and simulated annealing algorithm.DNA computing is a branch of computing which can be traced back to 1994 when Aldeman firstly demonstra-ted a proof-of-concept use of DNA as a form of computation to solve the seven-point Hamiltonian path problem.DNA computing dedicates to use DNA,biochemistry together with molecular biology hardware to take the place of the traditional silicon-based computer technologies.Theory,experiments and applications are the concerns in the DNA computing research field.Some NP-complete problems and the computational model of NP-complete problems have been put forward.Typically,DNA strands with special enzymes are used as the calculating materials.With the development of DNA self-assembly technology,other DNA nanostructures are also used for molecular biology,such as plasmid DNA molecules,molecular beacon structures,as well as DNA Tiles.In this paper,the DNA origami-based nanostructures are employed for encoding information.Through the self-assembly of the sticky ends in the DNA origami-based nanostructures and the special enzymes which can identify the restriction sites,we demonstrated a deterministic graph coloring model.Based on the creation of millions of DNA origami nanostructures involved in the calculation,this algorithm can be parallelized in testing each possible coloring scheme.To easily address the graph coloring problem,the DNA origami-based nanostructures are designed large enough which could be readily detected by atomic force microscopy and transm

关 键 词：DNA计算 DNA“折纸术” NP-完全问题 图着色问题 纳米金颗粒 

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