DNA算法在Hamilton路徑中的應(yīng)用教程文件

1、Good is good, but better carries it.精益求精，善益求善。DNA算法在Hamilton路徑中的應(yīng)用-DNA算法在Hamilton路徑中的應(yīng)用摘要DNA計(jì)算是生物計(jì)算中最受關(guān)注的一種計(jì)算，目前的DNA計(jì)算領(lǐng)域始于1994年Adleman先生的著名實(shí)驗(yàn)。DNA算法解決計(jì)算問題的基本思想是：以DNA堿基序列作為信息編碼的載體，利用現(xiàn)代分予生物學(xué)技術(shù)，在試管內(nèi)控制酶的作用下進(jìn)行DNA的序列反應(yīng)，Watson-Crick互補(bǔ)序列反應(yīng)作為實(shí)現(xiàn)運(yùn)算的過程。本文通過DNA計(jì)算尋找Hamilton路徑存在從而判定Hamilton路徑是否存在。該算法的創(chuàng)新之處在于通過一種新的計(jì)算

2、方法解決圖論中的一些NP完全問題。關(guān)鍵詞：DNA算法Adleman實(shí)驗(yàn)Hamilton路徑引言隨著計(jì)算機(jī)科學(xué)與數(shù)學(xué)的發(fā)展，圖論已經(jīng)應(yīng)用到了各個(gè)領(lǐng)域，其中包括物理學(xué)、化學(xué)、通訊科學(xué)、計(jì)算機(jī)技術(shù)、生物遺傳學(xué)等等。圖論為任何一個(gè)包含二元關(guān)系的系統(tǒng)提供了一個(gè)數(shù)學(xué)模型；利用圖直觀、漂亮的表現(xiàn)特性可以使人對(duì)現(xiàn)實(shí)的系統(tǒng)有清晰的了解現(xiàn)實(shí)世界中的許多問題的數(shù)學(xué)抽象形式可以用圖來述。如互聯(lián)網(wǎng)、交通網(wǎng)、通訊網(wǎng)、集成電路、分子結(jié)構(gòu)等都可用圖來描述。圖論已經(jīng)成為人們研究自然科學(xué)及社會(huì)科學(xué)的一個(gè)重要工具。其中Hamilton圖及相關(guān)領(lǐng)域，其應(yīng)用己越來越重要。Hamiton路徑問題眾所周知，圖的Hamiton路徑問題一直是

3、圖論中的一個(gè)十分重要且十分活躍的研究課題。十九世紀(jì)中期愛爾蘭的皇家天文學(xué)家哈密頓(WilliamRowanHamilton)提出，在一個(gè)有多個(gè)城市的地圖網(wǎng)絡(luò)中，尋找一條從給定的起點(diǎn)到給定的終點(diǎn)沿途恰好經(jīng)過所有其他城市一次的路徑。通常所說的Hamiton路徑問題是設(shè)G是一個(gè)有向圖,V1,V2是G的兩個(gè)頂點(diǎn),如果存在一條從V1出發(fā)到達(dá)V2,且經(jīng)過G中其它每個(gè)頂點(diǎn)一次且只有一次的有向路P,則稱P是G中從V1到V2的一條有向Hamilton路。尋找一個(gè)給定有向圖的有向Hamilton路問題是所謂的有向Hamilton路問題,簡(jiǎn)記為HPP問題。2.DNA算法的生物學(xué)基礎(chǔ)DNA計(jì)算機(jī)起源于人們對(duì)并行計(jì)算的

4、研究和追求，以傳統(tǒng)的圖靈機(jī)(Turing-Machine)為原型的現(xiàn)代電子計(jì)算機(jī)很難從真正意義上實(shí)現(xiàn)并行算。于是人們將目光投向了其它領(lǐng)域，以求獲得完全不同的計(jì)算方式和計(jì)算理念。1994年Adleman的實(shí)驗(yàn)，標(biāo)志DNA計(jì)算領(lǐng)域的開始。DNA算法解決計(jì)算問題的基本思想是：以DNA堿基序列作為信息編碼的載體，利用現(xiàn)代分予生物學(xué)技術(shù)，在試管內(nèi)控制酶的作用下進(jìn)行DNA的序列反應(yīng)，Watson-Crick互補(bǔ)序列反應(yīng)作為實(shí)現(xiàn)運(yùn)算的過程。以反應(yīng)前的DNA序列作為輸入的數(shù)據(jù)，反應(yīng)后的DNA序列作為運(yùn)算的結(jié)果。DNA計(jì)算的操作方法一般有抽取、切割、溶解、退火、合成、雜交、擴(kuò)增PCR、檢測(cè)、分離、電泳、磁珠分離

5、、連接和合并等一系類操作。DNA（脫氧核糖核酸）是所有生物主要的遺傳物質(zhì)，它是一種高分子化合物，組成它的基本單位是脫氧核苷酸。每個(gè)脫氧核苷酸是由一分子磷酸、一分子脫氧核苷酸和一分子含氮堿基組成的.含氮堿基有4種，腺嘌呤（A）、鳥嘌呤(G)、胞嘧啶（C）和胸腺嘧啶(T)。DNA分子不僅具有一定的化學(xué)成分，還具有規(guī)則的雙螺旋結(jié)構(gòu)。結(jié)構(gòu)的主要特點(diǎn)是：（1）DNA分子是由兩條平行的脫氧核苷酸長(zhǎng)鏈盤旋而成；（2）DNA份子中的脫氧核糖和磷酸交替連接，排列在外側(cè)；（3）DNA兩條鏈上的堿基通過氫連接起來，形成堿基對(duì)。堿基對(duì)的組成有一定的規(guī)律，這就是嘌呤與嘧啶配對(duì)。A和T配對(duì)，C和G配對(duì)。這就是著名的堿基互

6、補(bǔ)配對(duì)原則。組成DNA的堿基雖然只有四種，而且這四種堿基的配對(duì)方式只有兩種，但由于堿基對(duì)具有多種不同的排列順序，因而就構(gòu)成了DNA分子的多樣性。圖1簡(jiǎn)單的描述了DNA分子的雙螺旋結(jié)構(gòu)。圖1：DNA分子的雙螺旋結(jié)構(gòu)3.DNA算法的原理為了計(jì)算簡(jiǎn)單起見，取一個(gè)只有四個(gè)頂點(diǎn)的圖，圖2如下所示圖2簡(jiǎn)單模型圖現(xiàn)在我們的問題就是找到這個(gè)網(wǎng)絡(luò)中，從北京到上海的Hamilton徑。當(dāng)然這個(gè)問題的答案很簡(jiǎn)單，實(shí)際路線顯然是北京成都南京上海。不過我們的真正問題在于怎樣用DNA分子計(jì)算來得到這個(gè)結(jié)果。無論如何，對(duì)于DNA分子來說，其所有的信息都用堿基順序來表示的。而兩條DNA鏈如果其上的堿基順序可以互補(bǔ)配對(duì)的話，那

7、它們就會(huì)形成局部的或者整條鏈的雙鏈結(jié)構(gòu)，這就是著名的DNA雙螺旋。配對(duì)規(guī)則AT;TA;GC;CG。(注意DNA鏈?zhǔn)蔷哂蟹较蛐缘?，互補(bǔ)配對(duì)的雙鏈方向相反)。編碼：每個(gè)節(jié)點(diǎn)：隨機(jī)生成一個(gè)8個(gè)核苷酸的字母鏈,并且保證每一個(gè)節(jié)點(diǎn)的編碼是唯一的和可識(shí)別的。代表各個(gè)城市的堿基順序以及它們的互補(bǔ)鏈上的堿基順序。北京：5-AGGCTTGA-33-TCCGAACT-5成都：5-GACCTACA-33-CTGGATGT-5南京：5-CCGAAATT-33-GGCTTTAA-5上海：5-TTAGCGAT-33-AATCGCTA-5上面的堿基順序?qū)嶋H上是隨機(jī)的，為了表示各個(gè)城市之間的聯(lián)系，我們也同樣用一個(gè)堿基順序來表

8、示這個(gè)信息。不過這個(gè)堿基順序是被上面的順序所決定的。（默認(rèn)DNA鏈方向?yàn)?-3）比如北京成都：TTGAGACC我們所使用的是北京這個(gè)城市的后半段堿基順序加上成都這個(gè)城市的前半段堿基順序，來表示這個(gè)信息。按照這樣的規(guī)則，我們依次構(gòu)造圖2中所有的聯(lián)系方式。）北京成都：TTGAGACC成都北京：TACAAGGC北京上海：TTGATTAG成都上海：TACATTAG成都南京：TACACCGA南京上海：AATTTTAG由于我們已經(jīng)知道答案是：北京成都南京上海，將這個(gè)答案轉(zhuǎn)換為堿基順序的話，顯然我們有“TTGAGACCTACACCGAAATTTTAG”。觀察一下這個(gè)堿基順序很顯然它就是簡(jiǎn)單的把北京至成都、成

9、都至南京、南京至上海的這三段堿基順序給連在一起了。為了便于理解，圖3如下。有下圖可知，通過成都編碼的互補(bǔ)鏈，可以把兩個(gè)城市邊通過DNA連接酶連接起來。圖3用DNA連接酶連接代表各個(gè)城市之間聯(lián)系的DNA鏈。將上述代表各個(gè)城市的互補(bǔ)鏈以及代表各個(gè)城市之間聯(lián)系的DNA鏈若干以及DNA連接酶等加入試管。由于DNA連接酶所固有的限制，它決不會(huì)隨便把任意兩條DNA鏈在一起，以此類推在DNA連接酶的作用下，所有可以連接在一起的DNA鏈最終都連接在了一起。由于DNA連接酶的效率，幾乎在一秒之內(nèi)，所有可能的穿越網(wǎng)絡(luò)的路徑就通過該方式連接在一起了。4.Hamilton路徑的DNA算法實(shí)現(xiàn)4.1DNA算法步驟算法步

10、驟：給定一個(gè)有N個(gè)頂點(diǎn)的網(wǎng)絡(luò)1.隨機(jī)生成圖中的各條路徑；只保留那些由起始節(jié)點(diǎn)開始并且由終止節(jié)點(diǎn)結(jié)束的那些路徑；只保留那些只經(jīng)過n個(gè)節(jié)點(diǎn)路徑（假設(shè)圖有n個(gè)節(jié)點(diǎn)）；只保留那些每個(gè)節(jié)點(diǎn)只進(jìn)入一次的那些路徑；如果存在這樣的路徑，輸出。4.2Adleman實(shí)驗(yàn)：圖4如下所示，頂點(diǎn)V0為起點(diǎn)，V6為終點(diǎn),根據(jù)上面所述步驟，尋找Hamilton路徑。圖4編碼：每個(gè)節(jié)點(diǎn)：隨機(jī)生成一個(gè)20個(gè)核苷酸的字母鏈,并且保證每一個(gè)節(jié)點(diǎn)的編碼是唯一的和可識(shí)別的。頂點(diǎn)用V表示，Vi-j表示i個(gè)頂點(diǎn)到j(luò)個(gè)頂點(diǎn)的邊邊：Vi-j前10個(gè)核苷酸是Vi(i=0除外,當(dāng)i=0時(shí),取V0的全部編碼)的3端的10個(gè)核苷酸,邊Vij的后10個(gè)

11、核苷酸是Vj(當(dāng)j=6時(shí),取V6的全部編碼)的5端的10個(gè)核苷酸。實(shí)驗(yàn)步驟如下：對(duì)圖中每一個(gè)節(jié)點(diǎn)(V=0和V=6除外)和每一條有向邊Vi-j，加入50pmol（為Vi的互補(bǔ)DNA鏈）h和50pmol的Vi-j,混合后在連接酶的作用下發(fā)生連接反應(yīng)，生成一個(gè)通過圖的隨機(jī)路徑集。2)用V0及做引物,通過聚合酶鏈?zhǔn)椒磻?yīng)(PolymeraseChainReaction,PCR)將第一步產(chǎn)生的由節(jié)點(diǎn)V0開始、V6結(jié)束的路徑進(jìn)行擴(kuò)增。3)通過凝膠電泳技術(shù)，選出分子質(zhì)量為140bp的DNA編碼，得到路徑中只有7個(gè)節(jié)點(diǎn)的DNA序列。4)將第三步的結(jié)果進(jìn)行親和純化，相繼重復(fù)用Vl，V2，V3，V4，V5的互補(bǔ)DN

12、A鏈磁珠進(jìn)行分離，選取通過節(jié)點(diǎn)l，2，3，4，5至少一次的路徑。5)通過PCR擴(kuò)增和和凝膠電泳，檢測(cè)是否有Hamilton路徑存在。通過實(shí)驗(yàn)步驟1和2后，PCR擴(kuò)增的產(chǎn)生的部分序列如下：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路徑。把結(jié)果輸出?？偨Y(jié)：事實(shí)上，HPP問題已經(jīng)被證明是一個(gè)NP完全問題，不可能存在一個(gè)有效的算法

13、(即不可能在多項(xiàng)式時(shí)間內(nèi)完成計(jì)算)。但在Adlemn的實(shí)驗(yàn)里。他通過完整而標(biāo)準(zhǔn)的實(shí)驗(yàn)方法步驟，解決了較小規(guī)模圖的HPP問題，然而，這種方法在原理上也同樣適用于比較大的圖。這種方法的關(guān)鍵是大規(guī)模的并行計(jì)算和堿基互補(bǔ)原則。實(shí)質(zhì)上，此算法是在執(zhí)行窮舉搜索，在Adleman的算法中，DNA串的巨大規(guī)模的并行計(jì)算處理了令人討厭的不確定性，堿基互補(bǔ)原則用來確保構(gòu)造出邊的序列就是圖G中的路。生物計(jì)算中用到的生物操作與常規(guī)的數(shù)學(xué)操作有很大的不同，建立在生物操作基礎(chǔ)上的計(jì)算是一種全新的計(jì)算方式，它與傳統(tǒng)的電子計(jì)算機(jī)不僅有效率上的差別，更有本質(zhì)上的區(qū)別。電子計(jì)算機(jī)順序計(jì)算的方式反映了人們對(duì)計(jì)算認(rèn)識(shí)程度，開發(fā)了一種

14、人工的機(jī)械計(jì)算的工具。DNA計(jì)算給出了一種大自然的計(jì)算方式，它不用加減，而是用切割、刪除、熔解、退火等生化反應(yīng)，這些生物體中的現(xiàn)象都隱含著計(jì)。DNA計(jì)算表明，數(shù)學(xué)可能是生物固有的根基，是大自然的結(jié)構(gòu)和運(yùn)轉(zhuǎn)的核心。因此，研究DNA計(jì)算，不僅可能得到效率更高的計(jì)算工具，也引發(fā)出對(duì)生命本質(zhì)的一種思考。此外,DNA計(jì)算的優(yōu)點(diǎn)運(yùn)算速度快、低能耗、存儲(chǔ)容量高、可以真正實(shí)現(xiàn)并行工作為DNA計(jì)算提供了廣闊的前景。參考文獻(xiàn)：1(美)邦迪(Bondy,J.A.)，默蒂(Murty,U.S.R.)圖論及其應(yīng)用北京：科學(xué)出版社，19842高琳，馬瑞年，許進(jìn).有向最短哈密爾頓路問題的DNA算法J.系統(tǒng)工程與電子技術(shù),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上運(yùn)行。#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(輸入頂點(diǎn)：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(輸入有邊相連的頂點(diǎn)的序號(hào)：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,