| 图顶点着色问题的DNA计算模型 |
| |
| 引用本文： | 强小利,赵东明,张凯.图顶点着色问题的DNA计算模型[J].计算机学报,2009,32(12). |
| |
| 作者姓名： | 强小利 赵东明 张凯 |
| |
| 作者单位： | 北京大学信息科学技术学院高可信软件技术教育部重点实验室,北京,100871 |
| |
| 基金项目： | 国家自然科学基金，国家"八六三"高技术研究发展计划项目基金，中国教育部博上点基金，中国博上后科学基金 |
| |
| 摘 要： | DNA计算是以DNA分子作为数据的一种新型计算模式.为了减少DNA计算中编码的数量,不降低生化实验操作的可靠性,文中建立了一种基于酶切技术和PCR技术的图顶点着色DNA计算模型,给出了实现该模型的双编码的编码方案.分析表明,利用酶切技术和PCR技术能够有效删除非解并读取真解.该模型的解的检测方法类似于DNA测序技术,使得该模型更容易实现自动化操作.
|
| 关 键 词： | DNA计算 图顶点着色问题 编码 |
A DNA Computing Model for Graph Vertex Coloring Problem |
| |
| QIANG Xiao-Li,ZHAO Dong-Ming,ZHANG Kai.A DNA Computing Model for Graph Vertex Coloring Problem[J].Chinese Journal of Computers,2009,32(12). |
| |
| Authors: | QIANG Xiao-Li ZHAO Dong-Ming ZHANG Kai |
| |
| Abstract: | DNA computing is a novel computation paradigm with DNA molecules as"data",and biochemistry trials as"information processing instruments".In this paper,a DNA computing model to solve graph vertex 3-coloring problem is proposed based on enzyme digestion reactions.The graph vertex coloring problem is encoded by double encoding method and the false solutions deletion and the true solutions detection are updated and automized partly after enzyme digestion reactions and polymerase chain reaction.This method could be easier and faster to read out the solution.Especially,the procedure of solution detection is similar to DNA sequencing technology. |
| |
| Keywords: | DNA computing graph vertex coloring problem encoding |
| 本文献已被 万方数据 等数据库收录！ |
|
