DNA计算的基本理论及算法的研究.docVIP

DNA计算的基本理论及算法的研究 魏涛 （陕西理工学院数学系信息与计算科学专业2003级2班，陕西 汉中 723001） 指导教师：周涛 [摘要] DNA计算是一种模拟生物分子结构并借助于分子生物技术进行计算的新方法，开创了以生化反应作为计算工具的先例，它是解决一类难以计算问题的一种新方法，特别是它在解决NP难问题时显示出其巨大的潜力.由于DNA计算刚刚兴起，很多工作还都处于起步阶段，这就需要更多的人了解什么是DNA计算.本文主要在前人研究的基础上，综述了DNA计算的生物机理，编码方法，并就图论中的最大团问题、运筹学中的整数规划问题给予了具体的分析,利用了基于表面的DNA计算中的采用荧光标示策略，提出了一种解决数理逻辑中的简单推理问题方案，并尝试了DNA计算在命题公式推理中的应用，最后并就软计算中的遗传算法和DNA算法做了必要的比较，使读者易认识DNA计算巨大潜力. [关键词] DNA计算；最大团问题；整数规划；数理逻辑；DNA编码 1 引言 自从1994南加州大学Adleman开拓性的采用现代分子生物技术在试管里用DNA分子的生化反应解决了一个简单的有向图的哈密尔顿路径问题（HPP: Hamiltonian path problem），开创了DNA计算领域之后，紧接着1995年Lipton在Adlenan的基础上解决了更有趣的NP-完全问题（可满足问题），1997年Ouyang等有利用DNA计算解决了另一个NP-完全问题（图的最大团问题）.2000年，Wisconson大学的Liu等介绍一种基于表面计算的SAT问题的解决方法，这为DNA计算向DNA计算机的发展提供了进一步的理论依据，DNA计算的发展是非常迅速的，当然与大批的学者从事这方面的研究是分不开的.自从人们用生物遗传物质的思想开始到用DNA解决问题，人们一直在总结和寻找新的方法来充分的利用DNA这种分子结构.随着计算机技术的不断发展，人类文明的不断程度的不断提高，各种复杂的规划问题，NP-完全问题，逻辑推理问题，在各个领域内不断涌现，而现代的计算技术对这类问题可谓束手无策，不是速度太慢，就是存储不够，而用DNA计算来处理不但节省材料而且廉价，更重要的是DNA计算可以处理极其复杂的并行运算，具有高度的并行性从此揭开了DNA计算的新篇章.本文首先介绍DNA计算的基本理论、基本方法，并以图的最大团问题和整数规划问题为例分别分析了试管方式和表面方式的DNA计算，在此基础上作者给出了数理逻辑中推理问题 的DNA计算解法，并对DNA遗传算法和DNA计算作了简要的对比说明，最后阐述了DNA计算所面临的问题和障碍. 2 DNA分子的生物机理和计算性 随着科学的进步，人们从利用有形资源外，并且开始对大自然这种无形更加重视，因为任何生命或存在的东西都有其合理性，根据这种思想，人们揭开了生物遗传物质的面纱，并在应用于科技、军事方面取得了很多成果. 根据现代细胞学和遗传的研究得知，控制生物性状的主要物质是脱氧核糖核酸DNA（如图2.1）.DNA是一种高分子化合，组成它的基本单位是脱氧核苷酸，每一分子地脱氧核苷酸是由一分子的磷酸，一分子脱氧核糖和一分子的含氮碱基组成的（其中含氮碱基共有四种，分别为腺嘌呤（Adenine）:A、鸟嘌呤(Guanine):G、胞嘧啶(Cytosine）:C和胸腺嘧啶(Thymine):T）这是DNA的化学组成.DNA的组成结构非常特殊，它是由两条双向平行的脱氧核苷酸长链围绕一个共同的纤维轴旋转而成的（其内部是通过碱基配对形成的有规则的双螺旋结构，其中腺嘌呤A与胸腺嘧啶T配对（A-T），鸟嘌呤G与胞嘧啶C配对(C-G)，组成DNA分子的碱基虽然只有四种配，配对方式只有两种）（如图2)由于碱基对可重复排列的，所以DNA分子具有多样性.在分子生物计算中通常都采用DNA这种高分子化合物，这不仅因为DNA是生命信息的载体而且由于在遗传工程实验室中DNA容易操作. DNA计算的基本思想就是利用DNA特殊的双螺旋结构和碱基互补配对原则进行信息编码的，将要解决的问题的用DNA分子链编码，在生物酶的作用下生成各种数据池（data pool）,然后再通过一定的规则将原始问题的数据运算高度并行地影射成DNA分子链的可控生化反应过程，最后利用聚合链式反应PCR、超声波降解、诱变等分子生物技术检测所需要的运算结果.其核心问题的就是将经过编码的DNA链作为输入，通过试管方式、表面方式等来完成生物运算，从而能得到全部的解空间. 图2.2 DNA平面结构 此外，从DNA的原理来看它与数学操作非常类似，DNA的单链可看作四个符号A 、G、C、T组成的串.可表示成由集合{A，T，C，G}形成的一个串空间（潜在解空间）.酶可看作作用在DNA串上的一个算子，这种方法就和计算机中的0、1编码体制非