江智蘭

（安徽理工大學(xué)理學(xué)院 安徽 淮南 232001）

0 引言

目前對DNA計(jì)算的研究越來越多，并且DNA計(jì)算的應(yīng)用也越來越廣。自從1994年Adleman博士開創(chuàng)性地用DNA計(jì)算實(shí)現(xiàn)了七個頂點(diǎn)的有向圖的Hamilton路[1]問題以來，DNA計(jì)算就吸引了國內(nèi)外許多的研究學(xué)者，各種DNA計(jì)算模型也因很強(qiáng)的實(shí)用性成為研究熱點(diǎn)，本文主要探討中國郵遞員問題的解的檢測問題。DNA自組裝是分子與分子在一定的條件下，依賴非共價鍵分子間作用力自發(fā)連接成結(jié)構(gòu)穩(wěn)定的分子聚體的過程，早在1962年Wang用DNA單鏈組裝成瓦片作為計(jì)算的手段[2]，1998年，Winfree在他的博士論文中首先提出一種二維自組裝的抽象模型，命名稱為瓦片組裝模型（TAM）[3]；2000年，Lagoudakis給出了利用二維TAM求解可滿足性問題的方法.不斷取得成果，尤其是在密碼破譯和圖論與組合優(yōu)化問題方面[4]。2008年，Cheng提出了一種基于DNA瓦片自組裝的橢圓曲線密鑰交換算法；同年Chen利用TAM實(shí)現(xiàn)了一次一密加密算法Huang利用DNA瓦片自組裝解決了0-1規(guī)劃問題.2009年，zhu等用自組裝技術(shù)設(shè)計(jì)了一個軟件系統(tǒng)，一體化集成程序來設(shè)計(jì)DNA圖案和相呼應(yīng)的陣列[5]；2011年宋勃升，殷志祥等利用DNA自組裝成發(fā)夾結(jié)構(gòu)解決可滿足性問題，在計(jì)算過程中只需要用到凝膠電泳操作，在一定程度上大大減少了因生物操作過多而引起的各種實(shí)驗(yàn)誤差[6]。在同年張成等人利用DNA計(jì)算和納米技術(shù)相結(jié)合研究了自組裝DNA/納米顆粒分子邏輯計(jì)算模型摘要將AuNP自組裝聚合色變與DNA計(jì)算相結(jié)合，構(gòu)建了納米分子邏輯計(jì)算模型[7].2009年，李瑋等人提出了虛擬權(quán)值和虛擬節(jié)點(diǎn)的概念，給出了中國郵遞員問題的一種基于DNA計(jì)算的求解算法[8]。本文主要探討中國郵遞員問題的解的檢測問題。

中國郵遞員問題是由我國管梅谷教授首先提出并加以研究的NP完全問題中的一種。

問題描述：郵遞員在郵局分揀好需要郵遞的郵件后，到他管轄的區(qū)域內(nèi)的每一條街道投遞，最后返回郵局。對于這個問題郵遞員希望找出一條行走距離最短的路線。

將中國郵遞員問題轉(zhuǎn)化為圖論模型就可以這樣描述：我們把郵遞員所管轄的區(qū)域看做一個連通的加權(quán)無向圖G＝（V，E），其中V＝（v1，v2，…vn）是街道的交叉口和端點(diǎn)，E＝（E1，E2，…Em）是街道，權(quán)看作街道的長度。解決中國郵遞員問題，就是在連通加權(quán)無向圖總，找一條經(jīng)過每邊至少一次且權(quán)和最小的閉鏈，即對圖G中給定的節(jié)點(diǎn)vi，需要從所有可能路徑集{Pi}中求得一條最優(yōu)路徑Pj，Pj滿足：①Pj是從節(jié)點(diǎn)vi開始到節(jié)點(diǎn)vi結(jié)束；②Pj是經(jīng)過所有邊至少一次且權(quán)和最小的一條路。

1 中國郵遞員問題的DNA計(jì)算模型

1.1 基本算法

步驟1：所搜出G的所有閉路徑；

步驟2：找出那些開始于G，也結(jié)束與G的固定節(jié)點(diǎn)的閉路徑；

步驟3：找出那些經(jīng)過圖G國有邊至少一次的閉路徑，即保留G的所有廣義Euler回路；

步驟4：找出最短的廣義Euler回路，即權(quán)和最小的，也就是我們所求的；

步驟5：確定郵遞員的路線。

1.2 DNA算法及生物操作

步驟1：對給定圖G的節(jié)點(diǎn)和邊進(jìn)行編碼。對圖G中的任意節(jié)點(diǎn)vi生成長度為20bp的核酸序列分別記為V1，V2，…Vn，并且對權(quán)長wi生成長度為10bp的寡聚核苷酸序列記作d1，d2，…dm。每條邊eij即相鄰兩節(jié)點(diǎn)vi和vj之間的路的編碼包含三部分。第一部分是寡聚核苷酸片段Vi的后10個堿基的補(bǔ)所構(gòu)成的寡聚核苷酸片段；第二部分是表示權(quán)的編碼及表示di的寡聚核苷酸片段；第三部分是寡聚核苷酸片段vj的前10個堿基的補(bǔ)所構(gòu)成的寡聚核苷酸片段。如果Vi是V1即是起點(diǎn)的時候，路的寡聚核苷酸片段的第一個部分是寡聚核苷酸V1的全部即20個堿基的補(bǔ)構(gòu)成的，如果vj是V1，那么路的寡聚核苷酸片段的第三部分是寡聚核苷酸V1的全部即20個堿基的補(bǔ)構(gòu)成的。那么由vj到vi的路eji以類似的方法得到編碼。對編碼好的核苷酸片段為了生成圖G的所有閉路徑，我們將一定量的節(jié)點(diǎn)vi所對應(yīng)的DNA片段Vi和邊eij所對應(yīng)的DNA片段混合在一起，加入緩沖溶液，DNA連接酶使之進(jìn)行連接反應(yīng)?？梢酝ㄟ^考慮各種生物實(shí)驗(yàn)的影響因素，進(jìn)行相應(yīng)的調(diào)節(jié)使之達(dá)到最優(yōu)的反應(yīng)速度。經(jīng)過反應(yīng)，相應(yīng)節(jié)點(diǎn)和相應(yīng)邊的核苷酸片段會連接起來。形成了包含所有或者一些節(jié)點(diǎn)和邊的DNA片段。

步驟2：以V1為引物，用PCR放大技術(shù)，使以V1為起始并以V1為終點(diǎn)的DNA鏈進(jìn)行放大。因?yàn)樵诘谝徊竭€有其他的DNA鏈生成，所有需要對所求的DNA鏈進(jìn)行放大，第一次用V1作引物放大，在第二次用PCR進(jìn)行放大時用V1的補(bǔ)鏈作引物。然后加熱使DNA雙鏈變性生成相應(yīng)的DNA單鏈。

步驟3：親和純化第二步得到的產(chǎn)物，為了分離出我們所需的DNA鏈，我們可以用各個邊eij或eji的補(bǔ)鏈作探針，將含有eij或eji邊的DNA鏈經(jīng)過濾池從數(shù)據(jù)池中分離。然后再把分離出的DNA鏈進(jìn)行相同的操作，直到分離出含有每邊至少一次的所有DNA鏈。得到問題的可行解。

步驟4：對步驟3得到的DNA鏈用凝膠電泳，由于長的DNA鏈的移動速度小于短的DNA鏈，所以分離出移動速度最快的DNA鏈。步驟5：對步驟4得到的DNA鏈用下列方法確定邊的訪問順序。（1）得到的DNA單鏈固定到表面上。

（2）?eij是圖中的一條從 vi到 vj的邊，eji是從 vj到 vi的邊，將邊的補(bǔ)連接上不同的熒光素。

（3）將加上不同熒光素的邊的補(bǔ)鏈加到表面上。

（4）重復(fù)上述操作直到DNA單鏈變?yōu)镈NA雙鏈，利用激光共聚顯微鏡觀察表面上的DNA雙鏈的熒光素的顏色，就可以確定其對應(yīng)的路徑中包含的各條邊的訪問順序。

2 實(shí)例分析

我們根據(jù)圖1給出中國郵遞員問題的DNA算法的詳細(xì)解答，v1是郵

圖1 6個頂點(diǎn)的完全圖

步驟1：對上圖可記作 G＝（V，E），其中 V＝{v1，v2，…，v6}，E＝{e1，e2，…，e}。其中邊權(quán)為1，2，3.我們對圖的頂點(diǎn)和邊進(jìn)行編碼，具體情況如下表：

步驟5：對步驟4得到的DNA鏈利用熒光加到表面的方法來測序，得到我們所需的路線。

表1 頂點(diǎn)及權(quán)長的編碼

其中任一邊長，如e23的編碼為AATTGGCAGCattagcaacgGGGAAA CGTG，然后在試管中大量生產(chǎn)頂點(diǎn)和邊的DNA片段，加入緩沖溶液，加入鏈接酶，使得頂點(diǎn)和邊的DNA片段鏈接在一起生成包含所有節(jié)點(diǎn)或部分節(jié)點(diǎn)的路的DNA片段。

步驟2：用V1作引物用PCR放大技術(shù)，使以V1為起始并以V1為終點(diǎn)的DNA鏈進(jìn)行放大。第一次用V1作引物放大，在第二次用PCR進(jìn)行放大時用V1的補(bǔ)鏈作引物。然后加熱使DNA雙鏈變性生成相應(yīng)的DNA單鏈。

步驟3：親和純化第二步得到的產(chǎn)物，直到分離出含有每邊至少一次的所有DNA鏈。得到問題的可行解。本例題中的可能的可行解有如：V1-V2-V3-V4-V5-V6-V

步驟4：對步驟3得到的DNA鏈用凝膠電泳，由于長的DNA鏈的移動速度小于短的DNA鏈，所以分離出移動速度最快的DNA鏈。

3 結(jié)論

中國郵遞員問題是困難計(jì)算問題中的一個，電子計(jì)算機(jī)的存儲量小，運(yùn)算速度慢，對于解這樣的難題是非常困難的。DNA計(jì)算具有很好的并行性，因此在解決這類難題時，具有電子計(jì)算機(jī)無法比擬的優(yōu)勢在本文中主要是運(yùn)用了PCR放大技術(shù)和凝膠電泳技術(shù)得到我們所需的DNA鏈，然后再用在表面加上熒光素來檢測序列，最終確定我們郵遞員所經(jīng)過的路線。

具有方法簡單，易于解讀到結(jié)果的特點(diǎn)。

［1］Leonard M.Adleman.Molecular Computation of Solutions to Combinatorial Problems[J].Science，1994，266（5187）：1021-1024.

［2］Wang Hao.Dominoes and theSEA case of the decision problem[C].Proceedings of the Symposium in the Mathematical Theory of Automata.Brooklyn，1962：23-55.

［3］Winfree E，Liu F，Wenzler LA，eta1.Design and self-assembly of two-dimensional DNA crystals[J].Nature，l998，394（6693）：539-544.

［4］LagoudakisMG，LaBeanTH.2DDNA self-assembly for satisfiability[Z].In DNA BasedComputers V：DIMACS Workshop.Providence，2000，139·152.

［5］Zhu Jin hao， Wei Bryan，i YuanYuan， et a.l Uuniquimer3D， asoftware system for structuralDNAnanotechnologydesign，analy sisand evaluation[J].NucleicAcids Research，2009，37（7）：2164-2175.

［6］宋勃升，殷志祥，甄誠，華程.DNA自組裝的可滿足性問題模型[J].小型微型計(jì)算機(jī)系統(tǒng)，2011，9（32）：1872-1875.

［7］張成，楊靜，許進(jìn).自組裝DNA/納米顆粒分子邏輯計(jì)算模型[J].科學(xué)通報(bào)，2011，27（57）：2276-2282.

［8］李瑋，王雷.中國郵遞員問題的 DNA 計(jì)算[J].計(jì)算機(jī)應(yīng)用，2009，29（7）：1880-1883.