文献类型：期刊文章

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

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

出　　处：《南京大学学报（自然科学版）》

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

年　　份：2016

卷　　号：52

期　　号：4

起止页码：656-661

语　　种：中文

收录情况：BDHX、BDHX2014、CAS、CSCD、CSCD2015_2016、JST、MR、RCCSE、ZGKJHX、ZMATH、核心刊

摘　　要：色数是图论中的一个重要的参数,其属于著名NP(Non-deterministic Polynomial)-完全问题范畴.巨量的着色方案使验证变得相当困难,以至于在传统计算机上无法实现.目前已经有多种算法用于研究图定点着色问题,比如遗传算法,粒子群算法,神经网络算法和模拟退火算法等.随着DNA自组装技术与DNA计算机研究的展开,一些NP-完全问题以及NP-难问题的计算模型被相继提出.除了传统的DNA分子结构被用作计算材料外,其他的DNA分子结构也被用于分子生物计算,比如质粒DNA分子、分子信标结构以及DNA Tile等.采用DNA纳米折纸结构编码信息,借助于纳米结构之间的粘性末端进行自组装,给出了一种非确定性的图着色模型.通过创建数以亿计的参与计算的DNA纳米折纸结构,该算法可以并行的测试每种可能的着色方案.

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

分 类 号：TP301]