三维DNA自组装在多维背包问题中的应用研究-论文.pdf

《三维DNA自组装在多维背包问题中的应用研究-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第l3卷第36期2013年12月科学技术与工程VoI．13No．36Dec．20l31671—1815(2013)36—10787—07ScienceTechnologyandEngineering@2013Sci．Tech．Engrg．生物科学三维DNA自组装在多维背包问题中的应用研究牛莹张勋才范瑞丽崔光照(郑州轻工业学院电气信息工程学院，郑州450001)摘要利用DNA自组装执行计算的思想已从实验上被证明具有可行性。利用DNA瓦片自组装执行计算的方法，由于其通用性正被广泛研究，已有多种理论模型被提出以解决各种NP问题。基于DNATile自组装模型理论在三维下的扩展，设计了可以实

2、现这一算法的三维DNATile组装系统。提出了一种用于解决多维背包问题的三维DNA自组装模型；该模型可以非确定性的输出可行性解决方案。分析表明系统可以在线性组装步骤内完成计算，所需的Tile种类数与问题维数无关。为探索三维DNA自组装的计算能力进行了一次有意义的尝试。关键词DNA计算自组装多维背包问题DNATile中图法分类号Q754；文献标志码A1994年Adlemanl】借助于DNA分子和生物酶，计算模型]。1998年，Winfree首次提出了一种二通过可控的生化反应，成功解决了7顶点的Hamil-维DNA自组装的抽象模型，即瓦片自组装模型，ton路径问题。这从生物的角度上提出

3、了一种传统Brun对TAM进行了深入的研究，提出了加法和乘电子计算机无法在多项式时间内解决NP一难问题的法的计算模型_5J，并且应用于解决可满足性新方法，标志着一种全新计算领域的开始。问题。DNA计算的原理是利用DNA分子的双螺旋结经过十几年的探索和研究，DNA计算无论是从构以及碱基互补配对原则把DNA分子作为信息的理论研究和还是生化试验方面都取得了很多重要“载体”，借助生物酶和生化操作，通过一系列可控的进展。尤其是二维DNA自组装模型的研究与应的生化反应对信息进行处理的一种计算模式。用进展显著，但基于三维DNA结构的自组装模型尚1995年Lipton在Adleman的启发下，对D

4、NA未被很好的研究。近年来，DNA自组装技术发展迅序列进行布尔矢量编码，使其可以像逻辑门电路一猛，不论从理论或实验的角度看，构造三维DNA自样具有逻辑判断能力，并给出了一种可以解决可满组装瓦片结构都已具备可行性。相信随着生足性问题的计算模型j，从而证明了DNA计算可以化实验技术的不断提高，很快将有适合于计算的三用来解决所有的NP完全问题J。1997年Ouyang维DNA瓦片在实验室中被构造出来。等人利用Lipton的编码方式，给出了求解最大团的背包问题是属于典型的组合优化问题，被证明是NP难问题的一种12]。现实生活中的许多问题也都可以用背包问题来描述，如装箱问题、货仓装2013年

5、7月19日收到国家自然科学基金(61076103，61070238、载、存储分配、项目选择决策等。由于其计算的复河南省教育厅自然科学研究项目(2011A510025)、河南省科技计划基金(112300413208)杂性和难解性，成为信息解码学和数论领域研究中和郑州轻工业学院科研基金(201lXJJ025)资助的一个热门话题。2007年Darehmirki13]采用DNA通信作者简介：张勋才(1981一)，男，博士，副教授。研究方向：智能信息处理与优化控制，系统工程。E—mail：zhangxuncai@pku．计算解决了0～1背包问题。2009年Cheng等¨采edu．cn用二维自

6、组装模型来解决多维背包问题。基于上科学技术与工程l3卷面的研究理论和成果，现利用DNA分子的巨大并行理仍和二维DNA自组装相同。文献[11]提出的三性和海量的存储能力，提出三维DNA自组装求解多维DNA计算模型，并成功解决了图着色问题，在此维背包问题的方法。将它应用于解决多维背包问题。三维DNA瓦片的组装条件，如果瓦片S≤T，g，1三维DNA自组装模型>系统，A是的一个配置，瓦片￡∈T当且自组装是自然界中普遍存在着的一种现象，例仅当满足如下条件，才能在位置(，Y，z)组装到配如原子通过自组装形成分子，行星通过自组装形成置A上，生成新的配置A：星系，细胞壁，微型管的形成等。自组装是一

7、组无(1)(．Y．)隹A。序系统在没有外部的干预下，个别部件之间进行互(2)∑g(b(f)，bd{(，y，。)】))≥。动，而组成一个有组织的结构的过程。DNA分子自组装过程可以简单描述为：一些携(3)V(“，，)∈，(“，，)≠(，y，)j带着输入信息的DNA分子，在一定的温度，浓度，酸A(U，，)：(，，)。碱度以及特定的酶的作用下，根据Watson．Crick互(4)A(．Y．)=t。补配对原则，通过自组装生成新的带有输出信息的这意味着一个Tilet要能搞组装到