DNA算法在Hamilton路径中的应用教程文件

1、Good is good, but better carries it.精益求精，善益求善。DNA算法在Hamilton路径中的应用-DNA算法在Hamilton路径中的应用摘要DNA计算是生物计算中最受关注的一种计算，目前的DNA计算领域始于1994年Adleman先生的著名实验。DNA算法解决计算问题的基本思想是：以DNA碱基序列作为信息编码的载体，利用现代分予生物学技术，在试管内控制酶的作用下进行DNA的序列反应，Watson-Crick互补序列反应作为实现运算的过程。本文通过DNA计算寻找Hamilton路径存在从而判定Hamilton路径是否存在。该算法的创新之处在于通过一种新的计算

2、方法解决图论中的一些NP完全问题。关键词：DNA算法Adleman实验Hamilton路径引言随着计算机科学与数学的发展，图论已经应用到了各个领域，其中包括物理学、化学、通讯科学、计算机技术、生物遗传学等等。图论为任何一个包含二元关系的系统提供了一个数学模型；利用图直观、漂亮的表现特性可以使人对现实的系统有清晰的了解现实世界中的许多问题的数学抽象形式可以用图来述。如互联网、交通网、通讯网、集成电路、分子结构等都可用图来描述。图论已经成为人们研究自然科学及社会科学的一个重要工具。其中Hamilton图及相关领域，其应用己越来越重要。Hamiton路径问题众所周知，图的Hamiton路径问题一直是

3、图论中的一个十分重要且十分活跃的研究课题。十九世纪中期爱尔兰的皇家天文学家哈密顿(WilliamRowanHamilton)提出，在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿途恰好经过所有其他城市一次的路径。通常所说的Hamiton路径问题是设G是一个有向图,V1,V2是G的两个顶点,如果存在一条从V1出发到达V2,且经过G中其它每个顶点一次且只有一次的有向路P,则称P是G中从V1到V2的一条有向Hamilton路。寻找一个给定有向图的有向Hamilton路问题是所谓的有向Hamilton路问题,简记为HPP问题。2.DNA算法的生物学基础DNA计算机起源于人们对并行计算的

4、研究和追求，以传统的图灵机(Turing-Machine)为原型的现代电子计算机很难从真正意义上实现并行算。于是人们将目光投向了其它领域，以求获得完全不同的计算方式和计算理念。1994年Adleman的实验，标志DNA计算领域的开始。DNA算法解决计算问题的基本思想是：以DNA碱基序列作为信息编码的载体，利用现代分予生物学技术，在试管内控制酶的作用下进行DNA的序列反应，Watson-Crick互补序列反应作为实现运算的过程。以反应前的DNA序列作为输入的数据，反应后的DNA序列作为运算的结果。DNA计算的操作方法一般有抽取、切割、溶解、退火、合成、杂交、扩增PCR、检测、分离、电泳、磁珠分离

5、、连接和合并等一系类操作。DNA（脱氧核糖核酸）是所有生物主要的遗传物质，它是一种高分子化合物，组成它的基本单位是脱氧核苷酸。每个脱氧核苷酸是由一分子磷酸、一分子脱氧核苷酸和一分子含氮碱基组成的.含氮碱基有4种，腺嘌呤（A）、鸟嘌呤(G)、胞嘧啶（C）和胸腺嘧啶(T)。DNA分子不仅具有一定的化学成分，还具有规则的双螺旋结构。结构的主要特点是：（1）DNA分子是由两条平行的脱氧核苷酸长链盘旋而成；（2）DNA份子中的脱氧核糖和磷酸交替连接，排列在外侧；（3）DNA两条链上的碱基通过氢连接起来，形成碱基对。碱基对的组成有一定的规律，这就是嘌呤与嘧啶配对。A和T配对，C和G配对。这就是著名的碱基互

6、补配对原则。组成DNA的碱基虽然只有四种，而且这四种碱基的配对方式只有两种，但由于碱基对具有多种不同的排列顺序，因而就构成了DNA分子的多样性。图1简单的描述了DNA分子的双螺旋结构。图1：DNA分子的双螺旋结构3.DNA算法的原理为了计算简单起见，取一个只有四个顶点的图，图2如下所示图2简单模型图现在我们的问题就是找到这个网络中，从北京到上海的Hamilton径。当然这个问题的答案很简单，实际路线显然是北京成都南京上海。不过我们的真正问题在于怎样用DNA分子计算来得到这个结果。无论如何，对于DNA分子来说，其所有的信息都用碱基顺序来表示的。而两条DNA链如果其上的碱基顺序可以互补配对的话，那

7、它们就会形成局部的或者整条链的双链结构，这就是著名的DNA双螺旋。配对规则AT;TA;GC;CG。(注意DNA链是具有方向性的，互补配对的双链方向相反)。编码：每个节点：随机生成一个8个核苷酸的字母链,并且保证每一个节点的编码是唯一的和可识别的。代表各个城市的碱基顺序以及它们的互补链上的碱基顺序。北京：5-AGGCTTGA-33-TCCGAACT-5成都：5-GACCTACA-33-CTGGATGT-5南京：5-CCGAAATT-33-GGCTTTAA-5上海：5-TTAGCGAT-33-AATCGCTA-5上面的碱基顺序实际上是随机的，为了表示各个城市之间的联系，我们也同样用一个碱基顺序来表

8、示这个信息。不过这个碱基顺序是被上面的顺序所决定的。（默认DNA链方向为5-3）比如北京成都：TTGAGACC我们所使用的是北京这个城市的后半段碱基顺序加上成都这个城市的前半段碱基顺序，来表示这个信息。按照这样的规则，我们依次构造图2中所有的联系方式。）北京成都：TTGAGACC成都北京：TACAAGGC北京上海：TTGATTAG成都上海：TACATTAG成都南京：TACACCGA南京上海：AATTTTAG由于我们已经知道答案是：北京成都南京上海，将这个答案转换为碱基顺序的话，显然我们有“TTGAGACCTACACCGAAATTTTAG”。观察一下这个碱基顺序很显然它就是简单的把北京至成都、成

9、都至南京、南京至上海的这三段碱基顺序给连在一起了。为了便于理解，图3如下。有下图可知，通过成都编码的互补链，可以把两个城市边通过DNA连接酶连接起来。图3用DNA连接酶连接代表各个城市之间联系的DNA链。将上述代表各个城市的互补链以及代表各个城市之间联系的DNA链若干以及DNA连接酶等加入试管。由于DNA连接酶所固有的限制，它决不会随便把任意两条DNA链在一起，以此类推在DNA连接酶的作用下，所有可以连接在一起的DNA链最终都连接在了一起。由于DNA连接酶的效率，几乎在一秒之内，所有可能的穿越网络的路径就通过该方式连接在一起了。4.Hamilton路径的DNA算法实现4.1DNA算法步骤算法步

10、骤：给定一个有N个顶点的网络1.随机生成图中的各条路径；只保留那些由起始节点开始并且由终止节点结束的那些路径；只保留那些只经过n个节点路径（假设图有n个节点）；只保留那些每个节点只进入一次的那些路径；如果存在这样的路径，输出。4.2Adleman实验：图4如下所示，顶点V0为起点，V6为终点,根据上面所述步骤，寻找Hamilton路径。图4编码：每个节点：随机生成一个20个核苷酸的字母链,并且保证每一个节点的编码是唯一的和可识别的。顶点用V表示，Vi-j表示i个顶点到j个顶点的边边：Vi-j前10个核苷酸是Vi(i=0除外,当i=0时,取V0的全部编码)的3端的10个核苷酸,边Vij的后10个

11、核苷酸是Vj(当j=6时,取V6的全部编码)的5端的10个核苷酸。实验步骤如下：对图中每一个节点(V=0和V=6除外)和每一条有向边Vi-j，加入50pmol（为Vi的互补DNA链）h和50pmol的Vi-j,混合后在连接酶的作用下发生连接反应，生成一个通过图的随机路径集。2)用V0及做引物,通过聚合酶链式反应(PolymeraseChainReaction,PCR)将第一步产生的由节点V0开始、V6结束的路径进行扩增。3)通过凝胶电泳技术，选出分子质量为140bp的DNA编码，得到路径中只有7个节点的DNA序列。4)将第三步的结果进行亲和纯化，相继重复用Vl，V2，V3，V4，V5的互补DN

12、A链磁珠进行分离，选取通过节点l，2，3，4，5至少一次的路径。5)通过PCR扩增和和凝胶电泳，检测是否有Hamilton路径存在。通过实验步骤1和2后，PCR扩增的产生的部分序列如下：0-1-2-3-4-5-60-3-2-3-4-5-60-1-3-2-3-4-5-60-3-4-5-6通过步骤三后，筛选出的序列如下0-1-2-3-4-5-60-3-2-3-4-5-6通过步骤四后，剩下的序列为0-1-2-3-4-5-6最后通过步骤五，存在0-1-2-3-4-5-6，该路径就是我们所求的Hamilton路径。把结果输出。总结：事实上，HPP问题已经被证明是一个NP完全问题，不可能存在一个有效的算法

13、(即不可能在多项式时间内完成计算)。但在Adlemn的实验里。他通过完整而标准的实验方法步骤，解决了较小规模图的HPP问题，然而，这种方法在原理上也同样适用于比较大的图。这种方法的关键是大规模的并行计算和碱基互补原则。实质上，此算法是在执行穷举搜索，在Adleman的算法中，DNA串的巨大规模的并行计算处理了令人讨厌的不确定性，碱基互补原则用来确保构造出边的序列就是图G中的路。生物计算中用到的生物操作与常规的数学操作有很大的不同，建立在生物操作基础上的计算是一种全新的计算方式，它与传统的电子计算机不仅有效率上的差别，更有本质上的区别。电子计算机顺序计算的方式反映了人们对计算认识程度，开发了一种

14、人工的机械计算的工具。DNA计算给出了一种大自然的计算方式，它不用加减，而是用切割、删除、熔解、退火等生化反应，这些生物体中的现象都隐含着计。DNA计算表明，数学可能是生物固有的根基，是大自然的结构和运转的核心。因此，研究DNA计算，不仅可能得到效率更高的计算工具，也引发出对生命本质的一种思考。此外,DNA计算的优点运算速度快、低能耗、存储容量高、可以真正实现并行工作为DNA计算提供了广阔的前景。参考文献：1(美)邦迪(Bondy,J.A.)，默蒂(Murty,U.S.R.)图论及其应用北京：科学出版社，19842高琳，马瑞年，许进.有向最短哈密尔顿路问题的DNA算法J.系统工程与电子技术,2

15、002,24(8)：102-1053AdlemanLM.HYPERLINK8/index.html?sid=Science&Title=Molecular%20Computation%20of%20Solutions%20to%20Combina-tional%20Problems%5bJ%5d&aufirst=Adleman%20L%20M&volume=5187&issue=1t_blankMolecularComputationofSolutionstoCombina-tionalProb-lemsJ.Science,1994,266(5187).：102110244LiptonRJ.H

16、YPERLINK8/index.html?sid=Science&Title=DNA%20solution%20of%20hard%20computation%20problem%5bJ%5d&aufirst=Lipton%20R%20J&volume=5210&issue=2t_blankDNAsolutionofhardcomputationproblemJ.Science,1995,268(5210)：5425455G.P.RajaSekhar.DNACOMPUTING-GRAPHALGORITHMS6MinyiGuo，Michael(Shan-Hui)，Weng-LongChangFa

17、stparallelmolecularsolutiontothedominating-setproblemonmassivelyparallelbio-computingJParallelComputing2004,30：11091125求Hamiton路径的程序代码如下。用C+编程。在VisualC+6.0上运行。#include#defineMAX_POINT_NUM100#defineInfintyINT_MAXtypedefstructEdgeintadj;Edge,AMAX_POINT_NUMMAX_POINT_NUM;typedefstructintpointMAX_POINT_N

18、UM;Aarcs;intpnum;integdenum;Graph;voidCreateUDN(Graph&G,intm,intn)inti,j,k;printf(输入顶点：n);for(i=1;i=m;i+)scanf(%d,&G.pointi);for(i=1;i=m;i+)for(j=1;j=m;j+)G.arcsij.adj=0;printf(输入有边相连的顶点的序号：n);for(k=1;k=n;k+)scanf(%d,%d,&i,&j);G.arcsij.adj=1;G.arcsji.adj=1;intfun(intn)/*if(n=1)return1;elsereturnn*fun(n-1);*/returnn=1?1:n*fun(n-1);voidpailie(intn,inta1216)intk1,i,j,k,p,m=1;/a1216=0,0,1;for(i=2;i0;j-)for(k=i;k0;k-)k1=j&1?k:i+1-k;for(p=1;p=k)=ajp;ai*j-k1+1k=i;/*for(i=1;i=m;i+)for(j=1;j=n;j+)printf(%d,