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

DNA计算的基本理论及算法的研究魏涛(陕西理工学院数学系信息与计算科学专业2003级2班，陕西汉中723001)指导教师：周涛［摘要］DNA计算是一种模拟生物分子结构并借助于分子生物技术进行计算的新方法，开创了以生化反应 作为计算工具的先例，它是解决一类难以计算问题的一种新方法，特别是它在解决NP难问题时显示出其 巨大的潜力.由于DNA计算刚刚兴起，很多工作还都处于起步阶段，这就需要更多的人了解什么是DNA计 算.本文主要在前人研究的基础上，综述了 DNA计算的生物机理，编码方法，并就图论中的最大团问题、 运筹学中的整数规划问题给予了具体的分析，利用了基于表面的DNA计算中的采用荧光标示策略，提出了 一种解决数理逻辑中的简单推理问题方案，并尝试了 DNA计算在命题公式推理中的应用，最后并就软计算 中的遗传算法和DNA算法做了必要的比较，使读者易认识DNA计算巨大潜力.［关键词］DNA计算；最大团问题；整数规划；数理逻辑；DNA编码1引言自从1994南加州大学Adleman［1］开拓性的采用现代分子生物技术在试管里用DNA分子的生化反 应解决了一个简单的有向图的哈密尔顿路径问题(HPP: Hamiltonian path problem),开创了 DNA 计算领域之后，紧接着1995年Lipton⑵在Adlenan的基础上解决了更有趣的NP-完全问题(可满足 问题)，1997年0uyang［3］等有利用DNA计算解决了另一个NP-完全问题(图的最大团问题).2000 年，Wisconson大学的Liu'"］等介绍一种基于表面计算的SAT问题的解决方法，这为DNA计算向DNA 计算机的发展提供了进一步的理论依据，DNA计算的发展是非常迅速的，当然与大批的学者从事这 方面的研究是分不开的.自从人们用生物遗传物质的思想开始到用DNA解决问题，人们一直在总结和 寻找新的方法来充分的利用DNA这种分子结构.随着计算机技术的不断发展，人类文明的不断程度的 不断提高，各种复杂的规划问题，NP-完全问题，逻辑推理问题，在各个领域内不断涌现，而现代的 计算技术对这类问题可谓束手无策，不是速度太慢，就是存储不够，而用DNA计算来处理不但节省 材料而且廉价，更重要的是DNA计算可以处理极其复杂的并行运算，具有高度的并行性从此揭开了 DNA计算的新篇章.本文首先介绍DNA计算的基本理论、基本方法，并以图的最大团问题和整数规划 问题为例分别分析了试管方式和表面方式的DNA计算，在此基础上作者给出了数理逻辑中推理问题 的DNA计算解法，并对DNA遗传算法和DNA计算作了简要的对比说明，最后阐述了 DNA计算所面临 的问题和障碍.图2. 1脱氧核糖核酸化学结构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编码体制非常相近，在计算机中的每一个操作，对应 DNA串中的酶的作用，当然这种酶（算子）在设计上仍有很多问题，有时不能满足需求，如果这个 问题被解决了，那么DNA计算机的产生也就不远了，人们也就很容易接受DNA计算方法.3 DNA计算的生物操作及特点3. 1 DNA计算的生物操作合成：将核昔酸按一定次序合成一条所需的链；溶合：把两个试管的溶液倒入另一个试管以达到溶合；复合：把两条互补单链DNA链通过冷却的方法来重新结合；熔解：双链DNA通过加热分解成单链互补的部分；连接或修复：在双链DNA中，若其中一条单链中有不连续的部分，可以通过DNA连接酶来修复;复制：通过聚合酶链式反应，将DNA串复制；分离：使用凝胶电泳使DNA串按长度排列的重要技术；提取：使用亲和力提纯技术提取包含特定短序列的所有链；聚合：DNA聚合是实现DNA修复和复制等功能；切割：利用切割酶对DNA双链进行切割；切断：利用限制在酶在某一特定的位置切断DNA双链；标不：设置标示链，标示两条完整序列来合成一条双链；替换和删除：利用聚合酶链式反应操作来插入，替换或删除DNA链；绑结：使用DNA结合酶来粘贴DNA链；破损及切除：使用外核酸梅，限制内核酸酶及凝结电泳来完成；检测及读取：若一个给定试管中至少包含一个DNA链，则说'是，，反之说'不'.3.2 DNA计算的特点DNA计算的核心问题是将经过编码的DNA链作为输入，在试管内经过一定时间完成控制的生化 反应以此来完成运算，使得反映后的产物及溶液中能得到全部的解空间，DNA分子生物算法具有如 下三个优点'⑵：（1）DNA分子生物算法具有高度的并行性，运算速度快的特点.在Adi eman的实验中通过适当估 计DNA串的并行操作数目可达IO”.许多研究者认为用当前技术10顶到IO?。

个串的并行操作是可以 达到的，而且目前巨型机每秒的执行速度IO'?个操作，虽然DNA计算每个操作本身与电子实现相比 非常缓慢，但对于当前要求的巨型机或更强的计算挑战DNA的反应的巨大并行性是一补偿.(2) DNA作为信息的载体其存储容量非常之大，一立方米DNA溶液可存储一万亿亿的二进制的 数据，远远超过了目前所有的电子计算机的储存量.(3) DNA分子生物计算所消耗的能量只有一台电子计算机完成同样计算所消耗能量的十几亿分 之一.DNA计算的上述特性即高度并行性，大容量，低消耗，是目前计算机所无法代替的.从这个意 上说1994年有Adi eman所开发的生物计算机具有划时代的意义.4 DNA计算的编码方法及影响编码的因素编码方法是研究怎样把一个问题进行编码能生成问题所有无重复的可能的潜在解，其中比较著 名的方法有Wisconsin大学的A. G. Frutos等提出的模板影射方法和Feldkamp等提出的最小长度字 串方法，本节主要介绍编码的基本理论和基本因素4. 1模板影射方法模版影射方法是将DNA分子的编码过程分为二步：(1)搜索满足一定条件的二进制串作为模板 集合T,其中“1”代表A/T的位置，“0”代表G/C的位置；(2)搜索满住一定条件的编码二进制串 作为集合M,然后由：TxMt S最终得到所期望的DNA编码序列集合S,其规则为 1x1tT,1x0tA,0x1tG,0x0tC.模板一影射方法主要的理论基础是当模板集合T和影射集 合M中的各序列间的距离均大于d时，他们所产生的目标序列距离也大于d. . G. Frutos等采用8bp 的DNA序列代表一个可能的布尔变量组合，编码的要求如下：(1) GC含量为50%；(2) 任两个编码之间的汉明距离大于等于4；(3) 妒(x的补码序列)和y' (y的反码序列)之间的汉明距离大于等于4；模板集合T必须满足条件(1), (2)和(3)；影射集合M满足条件(2), (3).最后他们得到一 个有108个编码的DNA序列集合，并进行了杂交实验.实验结果表明，对于长度为16bp的DNA分了， 完全匹配与不完全匹配(有4个不同的位点)的解链温度7；的差别最小为lOkcal/mol.为了克服DNA序列间的移位杂交，引出如下一个最小距离的定义⑹：11 x 11= min(H (x, x"), HM (x, < xx >), HM (x, < xx" >), HM (x, < >)).其中H (xy)表不二进制串的汉明距离，< XX >表示任一二进制串与其相连后去掉首尾二个字 母后所得的串的序列，r表示反序列，表示二个不等长的二进制之间的最小移位汉明距离，即 Garzon等提出的H一距离.他要求模板集合T必须满足式(7)定义的最小距离Wx\^d ,影射集合M 采用距离大于d的二进制纠错码.显然模版影射方法所能得到的最大编码数取决于模板集合T和影射 集合M的大小，然而模版影射集合T和映射集合M的选择有时是相互制约的.所以，目前还不能从理 论上证明如何能够的到一个最大的编码集合.4.2最小长度子串方法Feldkamp等提出的最小长度子串评价方法:所有DNA序列(长度n,)间的相同子串的长度为-1， 而长度为的了串在编码集合中最多只能出现一次.于是可以定义为⑹：。

1 一-1)m .DNA序列间的相似度，显然0越大，DNA分子的相似度就越小出错杂交的几率也就越小.这与 Baum提出要求任意DNA分子间的相同或互补序列的长度不大于一个任意一个正整数k相似.但是， 在实际涉及设计中究竟k制取多大目前还难以确定.他们的搜索方法如下⑹四］：(1) 产生所有长度为rib的基础串(base strand)集合；(2) 过滤掉各种不满足条件的基础串如回文结构,CG含量，启动子，多聚GGG等.(3) 随机选取一个的基础串作为有向树的树根;然后去掉树根顶点的第一个字母,在其末尾分别 加上4各碱基A, C, G, T生成4个树叶顶点;重复此过程直到生成长度为％-七的有向路.(4) 对新生成的DNA序列用各种不同的过滤器进行过滤，如CG含量、解链温度,酶识别序列，同源 性等；(5) 如果新生成的DNA序列满足要求，就将其加入新生成的序列合并中止该有向树搜索过程;否 则就回到上一顶点直到遍历完整个有向树；(6) 重复(3) (4) (5)步直到基础串集合变为空集.acgcgccgcgcA