DNA計算在圖論中的應用

1、DNA計算在圖論中的應用摘要：DNA計算是計算機科學和分子生物學互相結(jié)合、互相滲透而產(chǎn)生的新興交叉研究領域。DNA計算具有高度的并行性、運算速度快、信息貯存容量大等優(yōu)點。這為解決圖論中的一些問題尤其是圖論中的NP-完全問題提供了新的途徑。首先介紹了DNA計算的基本原理。然后詳細介紹了圖最小生成樹的DNA算法以及哈密頓圖的DNA算法。最后介紹了DNA計算在圖論應用的領域中存在的一些尚待解決的問題。關(guān)鍵詞：DNA計算、圖論、最小生成樹、哈密頓圖1. 引言自從Adleman博士于1994年開創(chuàng)性地用DNA計算實現(xiàn)了7個頂點的有向圖的哈密爾頓問題以來，國際上DNA計算在圖論應用的研究領域中，主要集中在

2、對哈密頓圖問題、圖著色問題和圖頂點的最小覆蓋問題的求解上。繼Adleman之后1998年，Roweis給出一種基于Sticker模型的解決集合最小覆蓋問題的方法。2000年，Head等又用基于質(zhì)粒的DNA計算求解了圖的最大團問題。同年，F(xiàn)aulhammer等人對騎士周游問題用DNA計算進行了求解【1】。2004年，Zuwairie Ibrahim等人提出了一種求解最短有向路問題的一種DNA算法。2006年， Aili Han和Daming Zhu提出了解決旅行者問題的一種新的DNA編碼方法【2】。電子計算機在解決圖與組合優(yōu)化中的NP-問題是非常的困難，特別是規(guī)模特別大時幾乎是不可能的。DNA計

3、算機將具有以下幾個方面的突出優(yōu)點:(l)具有高度的并行性，運算速度快。(2)DNA作為信息的載體其貯存的容量非常之大。(3)DNA計算機所消耗能量極小。(4)DNA分子的資源豐富【3】。這些決定了DNA計算在解決非線性復雜問題、NP完全問題時具有其他計算模式所無法比擬的優(yōu)勢。2. DNA計算的基本原理DNA計算的本質(zhì)就是利用大量不同的核酸分子雜交，產(chǎn)生類似于某種數(shù)學過程的一種組合的結(jié)果，并根據(jù)限定條件對其進行篩選的。單鏈DNA可看作由符號A、C、G、T組成的串,同電子計算機中編碼0和1一樣,可表示成4字母的集合來譯碼信息。特定的酶可充當“軟件”來完成所需的各種信息處理工作【4】。DNA計算的基

4、本思想是：利用DNA分子的雙螺旋結(jié)構(gòu)和堿基互補配對的性質(zhì),將所要處理的問題編碼成特定的DNA分子,在生物酶的作用下,生成各種數(shù)據(jù)池；然后利用現(xiàn)代分子生物技術(shù)如聚合酶鏈反應、聚合重疊放大技術(shù)、超聲波降解、分子純化、電泳、磁珠分離等手段破獲運算結(jié)果；最后通過測序或其它方法解讀計算結(jié)果。DNA計算的核心問題是將經(jīng)過編碼后的DNA鏈作為輸入,在試管內(nèi)或其它載體上經(jīng)過一定時間完成控制的生物化學反應,以此來完成運算,使得從反應后的產(chǎn)物中能得到全部的解空間。3. DNA計算在圖論中的應用3.1最小生成樹問題文中我們考慮的圖是連通賦權(quán)簡單圖。若圖是連通的無向圖或強連通的有向圖，則從圖中任意一個頂點出發(fā)遍歷圖中

5、的所有頂點，這個過程中經(jīng)過的邊所構(gòu)成的子圖稱為原圖的生成樹。所以最小生成樹可描述為：在連通圖G的所有生成樹中，代價（生成樹各邊權(quán)值之和）最小的生成樹稱為最小生成樹【5】。最小生成樹可簡記為MST。下面討論求解最小生成樹問題的算法。根據(jù)最小支撐樹的定義，我們可以將最小支撐樹的算法簡單概括如下: 針對圖G，從空樹T開始，往集合T中逐條選擇權(quán)最小的邊（始終保持邊數(shù)=頂點數(shù)-1），直到無法再擴展為止。具體步驟如下：步驟一:從E中選取一條最小權(quán)的邊，記為el=，E=e1；記n=2，Vn=vl，vZ。步驟二:如果n=G，則T=(Vn,En-1)是最小支撐樹；否則執(zhí)行步驟3。步驟三:從中選一條權(quán)最小的邊(表

6、示連接頂點Vn，V-Vn的邊)記為en-1=，Vn+1 = Vn vn,En=En-1en-1，把n換成n+1，轉(zhuǎn)入第2步。我們來介紹上面提到的算法所對應的分子操作步驟:步驟一:對圖的頂點、邊以及邊的權(quán)進行DNA編碼：對于圖G的任意頂點vi，用長度為20的寡聚核苷片斷表示(即它包含20個堿基)，并記為Ni(i=1，2，n)。然后利用Ni構(gòu)造n個探針，并分別記為Q1,Q2,Qn。對于圖G的邊eij由三個部分表示:第一部分是寡聚核著酸片斷Ni的堿基的補鏈所構(gòu)成的寡聚核苷酸片斷；第二部分是寡聚核苷酸片斷Nj的堿基的補鏈所構(gòu)成的寡聚核苷酸片斷。第三部分是長度為( wij 為邊eij的權(quán)，D=max w

7、ij )的寡聚核苷酸片斷；下面通過例子解釋編碼問題。根據(jù)圖1，可得到,D=max1，5，4，4，2，3，6，5，7=7。因此根據(jù)上面的公式，可以得到對應于邊權(quán)w12 ，w23 ，w34 ，w45 ，w15 ，w26 ，w36 ，w46 ，w56 ，編碼的寡聚核苷酸片斷的長度分別為：26，22，30，13，5，9，22，18，18。由于篇幅所限，我們這里就只拿e12 ，e23 ，舉例。頂點1，2，3的編碼如下：N1：TCGGTAATGCTAGCTGGAGAN2: TATAGGCCATGCGATCGGTAN3: CGTTAAGCAGTACGAGTCAG根據(jù)編碼規(guī)則，得到e12 ，e23的編碼為：N

8、12：ATCCATTACGATCGACCTCGATCGATTGCTAGGCCATGACGGATATATATCCGGTACGCTAGCCATN23：ATATCCGGTACGCTAGCCATGATGTGACTGAATCGAAGTTAGGCAATTCGTCATGCTCAGTC注意：寡聚核普苷片斷Nij中帶下劃線的部分為邊的權(quán)值長度。然后將等量邊eij (li步驟二:從試管B中取出部分溶液進行瓊脂糖漿凝膠電泳，跑在最前端的就是最短的DNA鏈，該DNA鏈對應的一定是圖G的權(quán)最小的邊。提取出這些DNA鏈并用PCI進行擴增和純化來增加它的純度。步驟三:對第二步的產(chǎn)物進行測序并記錄這條邊。不妨記這條邊為e12

9、=v1v2，同時記V1=v1，v2。如果V1=V(G)，則停止；如果 V1V(G)，那么利用探針Q1，Q2將含有頂點v1及含有頂點v2的邊e12從試管B中分離出來，然后再分別利用探針Q1，Q2將含有頂點v1及含有頂點v2分離出來建立新的試管，仍然記為B，轉(zhuǎn)入第2步。按此操作，最多經(jīng)過n-1步，就可以找到圖G的最小生成樹，而且在生物操作中，用電泳代替了權(quán)值的比較，更加適合于尋找比較復雜的圖的最小生成樹。3.2 哈密頓路徑問題哈密頓路徑又稱為哈密頓回路，是指一個圖中,從圖的一個頂點出發(fā),沿著圖中的邊(各頂點連線),經(jīng)過所有頂點且只經(jīng)過一次,最終又回到起點,這條回路就稱為哈密頓路徑。在一個賦權(quán)圖中的

10、所有哈密頓路徑中，所經(jīng)各邊權(quán)值之和最小的哈密頓路徑稱為最短哈密頓路徑，也稱為最短哈密頓回路。哈密頓路徑問題是一個NP-完全問題。本節(jié)闡述了利用DNA計算的方法找出無向賦權(quán)圖中的所有哈密頓路徑并找出最短的哈密頓路徑的算法。在1994年Adleman博士用DNA計算首次實現(xiàn)了7個頂點的有向圖的哈密爾頓問題。這里采取一種與Adleman博士不同的編碼方式。Adleman博士當時采用DNA鏈的長短的編碼方式來代表權(quán)值的不同。這種編碼方式隨著問題規(guī)模的增長DNA鏈的結(jié)構(gòu)也會隨之不穩(wěn)定，在實際中的可行性也隨之降低。文中采用通過鏈中G，C含量的不同來代表不同的權(quán)值。對于權(quán)值較高的邊使其具有高的GC含量；因為

11、GC配對是形成三個共價鍵其解鏈溫度大于AT形成的二個共價鍵的結(jié)合。并且與Adleman博士在1994年所做的實驗不同的是，這里解決的是無向圖。在算法里將無向邊作為兩條有向邊進行處理。下面討論求解無向賦權(quán)圖中的哈密頓路徑問題的算法。哈密頓求解的問題可形式的表示為：給定無向賦權(quán)圖G=(V,E,W),V表示圖的頂點，E表示圖的邊，W表示圖各邊的權(quán)值。設圖中，V=n，即V(G)=V0,V1,V2Vn-1，如果存在為V0 為起始點以Vn-1為終點的一條包含圖p個頂點一次且僅一次的路，則稱這條路為為以V0 為起始點以Vn-1為終點的一條Hamilion路?？梢詫⑶蠼鉄o向賦權(quán)圖中的哈密頓路徑問題的算法簡單概

12、括如下:隨即產(chǎn)生圖G的所有路徑，從中找出含有n個頂點的的路徑。并從這些路徑中找出經(jīng)過圖G所有頂點（V(G)=V0,V1,V2Vn-1）且只經(jīng)過一次的路徑。再從中得到權(quán)值最小的路徑。具體步驟如下：步驟一：隨即產(chǎn)生圖G中的所有路徑，記為P。步驟二：從P中找出含有n個頂點的所有路徑，記為P1。步驟三：從P1中找出經(jīng)過所有頂點V(G)=V0,V1,V2Vn-1且只經(jīng)過一次的所有路徑，這些路徑既是圖G所有的哈密頓路徑，記為P2。步驟四：從P2中找到其中權(quán)值最小的一條路徑，這條路徑既是圖G的最短哈密頓路徑。我們來介紹上面提到的算法所對應的分子操作步驟:步驟一：首先對圖中所有的頂點V(G)和所有的邊E(G)

13、進行編碼。Vj= Vj Vj”用20bps的寡居核苷酸表示,。Vj代表頂點Vj的前端的10個寡居核苷酸，Vj” 代表頂點Vj的前端的10個寡居核苷酸。邊eij由頂點Vi的后10個寡居核苷酸Vi”，權(quán)值w和Vj的后10個寡居核苷酸Vj表示。其中w通過邊編碼的CG含量不同來代表它的大小，并根據(jù)實際情況選定邊編碼的長度。下面通過例子解釋編碼問題。根據(jù)圖2，用20bps長度的DNA鏈表示圖的邊，并且通過代表各邊的DNA鏈中的CG含量來區(qū)分權(quán)值的大小。圖中有6種不同的權(quán)值，為了在后續(xù)試驗中比較容易區(qū)別出不同的權(quán)值，這里可以領GC含量各相差4。各邊的GC含量分別為：0，4，8，12，16，20。無向圖的邊

14、可以看成有向邊，只不過入度和出度不同。由于篇幅所限，我們這里就只拿e01 ，e10 ，e12，舉例。頂點V0, V1, V2編碼如下：V0：GTCGATGATG CATTAAGCTGV1：ATCTGAGAGA GGAATCGATAV2：CAGGTAAATC TCATAGCATT注：單下劃線表示頂點Vj的前10個寡居核苷酸Vj，雙下劃線表示頂點Vj的前10個寡居核苷酸Vj“。根據(jù)編碼規(guī)則，得到e01 ，e10 ，e12的編碼為：e01：CATTAAGCTGGCATGTGGAATCAGTCAGAAATCTGAGAGAe10：ATCTGAGAGAGCATGTGGAATCAGTCAGAACATTAAG

15、CTGe12：GGAATCGATAATATAATTATAATTAATATACAGGTAAATC注：黑色下劃線表示邊的權(quán)值。按照上面的編碼方法生成所有頂點和邊的補鏈，并加上連接酶和緩沖液加入試管中。使之得到充分的復制。DNA分子大量冗余的特點保證了一定能得到所有可能性的路徑。步驟二：在步驟一得基礎上，利用V1和Vn-1構(gòu)造探針Q1和Qn-1。并且以這兩個探針為引物進行PCR反應。這樣試管中以V1為起始點以Vn-1為終點的路徑的到大量的復制。步驟三：對于步驟二生成的產(chǎn)物，進行凝膠、層析和多次的純化的到長度在制定區(qū)間的分子（這個區(qū)間保證得到所有經(jīng)過n個頂點的路徑）。步驟四：利用V1, V2Vn-1構(gòu)

16、造探針Q1 ,Q2Qn-1。在第三步的基礎上，以Q1 ,Q2Qn-1為引物，用磁珠分離的方式進行過濾。最終剩下的就是圖G中的所有哈密頓路徑。步驟五：在步驟四的基礎上，以邊權(quán)的編碼作為引物，進行PCR擴增。同時對試管溶液進行緩慢的加熱。使GC含量較低的路徑得到較大幾率的擴增，并進行多次循環(huán)的PCR擴增。步驟六：對步驟五得到的試管溶液進行凝膠電脈得到濃度最高的DNA鏈。這條DNA鏈既是圖G的最短哈密頓路徑。4. DNA計算在圖論中存在的問題DNA計算在圖論應用的領域中還存在一些尚待解決的問題。第一,圖論中權(quán)編碼的問題，編碼不夠合理會直接影響到整個算法的性能。第二, 如何對算法進行設計和優(yōu)化以降低算

17、法的空間復雜度。第三，操作的規(guī)模和次數(shù)問題，操作規(guī)模過于龐大直接影響到算法的精確性和計算時間。參考文獻：【1】韓愛麗. 賦權(quán)圖上優(yōu)化問題的DNA計算方法研究. 中國博士學位論文全文數(shù)據(jù)庫.2008【2】YuseiTsuboi,Zuwairie Ibrahim. Algorithm of graph isomorphism with three dimensional DNA graph structures. International Journal of Hybrid Intelligent Systems .2005【3】劉永現(xiàn).賦權(quán)圖的DNA計算模型. 中國碩士學位論文全文數(shù)據(jù)庫.2008【4】殷志祥，張佳秀. 圖論中的DNA計算模型. 系統(tǒng)工程與電子技術(shù).2007【5】韓世芬. 基于DNA計算的遺傳算法解決最小生成樹問題. 鄂州大學學報.2008【6】崔光照，張勛才，王延峰.DNA計算中編碼序列的優(yōu)化設計方案.計算機應用研究 .2007【7】周康，殷燕芳，李玉華等. 編碼的模型分析. 華中科技大學學報自然科學版.2007 許進，強小利，方剛等. 一種圖頂點著色DNA計算機模型. 科學通報.2006 朱翔鷗 ,劉文斌 ,孫川. DNA計