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

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

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

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

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

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

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

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

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

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

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

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

12、A鏈磁珠進(jìn)行分離，選取通過節(jié)點l，2，3，4，5至少一次的路徑。5)通過PCR擴(kuò)增和和凝膠電泳，檢測是否有Hamilton路徑存在。通過實驗步驟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é)：事實上，HPP問題已經(jīng)被證明是一個NP完全問題，不可能存在一個有效的算法

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

14、人工的機(jī)械計算的工具。DNA計算給出了一種大自然的計算方式，它不用加減，而是用切割、刪除、熔解、退火等生化反應(yīng)，這些生物體中的現(xiàn)象都隱含著計。DNA計算表明，數(shù)學(xué)可能是生物固有的根基，是大自然的結(jié)構(gòu)和運轉(zhuǎn)的核心。因此，研究DNA計算，不僅可能得到效率更高的計算工具，也引發(fā)出對生命本質(zhì)的一種思考。此外,DNA計算的優(yōu)點運算速度快、低能耗、存儲容量高、可以真正實現(xiàn)并行工作為DNA計算提供了廣闊的前景。參考文獻(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上運行。#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,