DNA自组装的可满足性问题模型  

DNA Self-assembly Model for General Satisfiability Problem

作　　者：宋勃升[1] 殷志祥[1,2] 甄诚[1] 华程[1] 

机构地区：[1]安徽理工大学理学院,安徽淮南232001 [2]华中科技大学控制科学与工程系,武汉430074

出　　处：《小型微型计算机系统》2011年第9期1872-1875,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(30570431;60873144)资助;国家"八六三"高技术研究发展计划项目基金(2006AA01Z104)资助;教育部新世纪优秀人才支持计划项目(NCET-06-0555)资助;安徽省教育厅自然科学基金项目(KJ2007B173)资助;安徽省优秀人才基金资助

摘　　要：DNA自组装技术在DNA计算和纳米技术领域都发挥着极其重要的作用,许多小规模NP完全问题都可以通过自组装模型得以解决.文中以可满足问题为模型,通过构造范式中变量的特殊补链,使其与初始数据库中初始DNA链发生杂交反应,形成发夹结构,利用形成发夹结构的DNA链与没形成发夹结构的DNA链长度不同的特点,通过凝胶电泳将这些带发夹的DNA链提取出来;然后加入与这些特殊补链完全互补的DNA链,在一定温度下,通过碱基互补配对原则,发夹结构又将被重新打开.该模型充分利用了DNA分子间的自组装能力,在计算过程中只需要用到凝胶电泳操作,在一定程度上大大减少了因生物操作过多而引起的各种实验误差.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 with hairpin by gel electrophoresis; then add up these special chain＇s fully complementary DNA chains, at a certain temperature, according to Watson-Crick principle, hairpin structure would be re-opened. The model makes full use of DNA molecules self- assembly capability, we only need to use gel electrophoresis operation in the calculation, it can greatly reduces of experimental error caused by the excessive operation.

关 键 词：DNA计算 NP完全问题 可满足问题 自组装 

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