| DNA自组装的可满足性问题模型 |
| |
| 引用本文： | 宋勃升,殷志祥,甄诚,华程.DNA自组装的可满足性问题模型[J].小型微型计算机系统,2011,32(9). |
| |
| 作者姓名： | 宋勃升 殷志祥 甄诚 华程 |
| |
| 作者单位： | 1. 安徽理工大学理学院,安徽淮南,232001
2. 安徽理工大学理学院,安徽淮南232001;华中科技大学控制科学与工程系,武汉430074 |
| |
| 基金项目： | 国家自然科学基金项目(30570431,60873144)资助; 国家“八六三”高技术研究发展计划项目基金(2006AA01Z104)资助; 教育部新世纪优秀人才支持计划项目(NCET-06-0555)资助; 安徽省教育厅自然科学基金项目(KJ2007B173)资助; 安徽省优秀人才基金资助 |
| |
| 摘 要： | DNA自组装技术在DNA计算和纳米技术领域都发挥着极其重要的作用,许多小规模NP完全问题都可以通过自组装模型得以解决.文中以可满足问题为模型,通过构造范式中变量的特殊补链,使其与初始数据库中初始DNA链发生杂交反应,形成发夹结构,利用形成发夹结构的DNA链与没形成发夹结构的DNA链长度不同的特点,通过凝胶电泳将这些带发夹的DNA链提取出来；然后加入与这些特殊补链完全互补的DNA链,在一定温度下,通过碱基互补配对原则,发夹结构又将被重新打开.该模型充分利用了DNA分子间的自组装能力,在计算过程中只需要用到凝胶电泳操作,在一定程度上大大减少了因生物操作过多而引起的各种实验误差.
|
| 关 键 词： | DNA计算 NP完全问题 可满足问题 自组装 |
DNA Self-assembly Model for General Satisfiability Problem |
| |
| SONG Bo-sheng
,
YIN Zhi-xiang
,
ZHEN Cheng
,
HUA Cheng.DNA Self-assembly Model for General Satisfiability Problem[J].Mini-micro Systems,2011,32(9). |
| |
| Authors: | SONG Bo-sheng YIN Zhi-xiang ZHEN Cheng HUA Cheng |
| |
| Affiliation: | SONG Bo-sheng1,YIN Zhi-xiang1,2,ZHEN Cheng1,HUA Cheng11(Department of Mathematics and Physics,Anhui University of Science and Technology,Huainan 232001,China)2(Department of Control Science and Engineering,Huazhong University of Science and Technology,Wuhan 430074,China) |
| |
| Abstract: | DNA self-assembly technology has played an important role in the field of DNA computing and nanotechnology.Many NP complete problems can be solved by self-assembly model.In this paper,we take the general satisfiability problem as a model,construction the special form of supplement chain with variable in normal form,hybridization with the them,So it can form hairpin structure,since the DNA chain with hairpin and the DNA chains with no-hairpin structure can have different length,we can extracted these chains ... |
| |
| Keywords: | DNA computing NP complete problem satisfiability problem self-assembly |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
