地圖著色問題的DNA計(jì)算

馬　瑩，方　歡

安徽理工大學(xué)理學(xué)院,安徽淮南，232001

?

地圖著色問題的DNA計(jì)算

馬瑩，方歡

安徽理工大學(xué)理學(xué)院,安徽淮南，232001

提出了將地圖著色問題轉(zhuǎn)化為頂點(diǎn)著色問題，然后把頂點(diǎn)著色問題轉(zhuǎn)化為求最大獨(dú)立集問題。最大獨(dú)立集問題的解法采用改進(jìn)的粘貼DNA計(jì)算，即全信息化的DNA粘貼計(jì)算。DNA粘貼計(jì)算設(shè)計(jì)了主鏈和存儲鏈，而且在生物計(jì)算中采用并行處理。最后給出了一個(gè)實(shí)例,詳細(xì)說明了地圖著色問題的解法，得出了最終的解。

DNA計(jì)算；粘貼計(jì)算；地圖著色問題；頂點(diǎn)著色；最大獨(dú)立集

1994年，Adleman首次用DNA計(jì)算解決有向圖的哈密頓問題[1]，此后許多研究者對DNA計(jì)算進(jìn)行研究。粘貼模型是由Roweis等人于1996年提出的一種DNA計(jì)算模型[2]，給出了圖的最大團(tuán)與最大獨(dú)立集粘貼DNA計(jì)算模型[3]，特別是許進(jìn)教授的文獻(xiàn)[4-5]對DNA粘貼計(jì)算的研究有很大的意義。文獻(xiàn)[6]把地圖著色問題轉(zhuǎn)化成可滿足性問題，并采用多級分離裝置來實(shí)現(xiàn)，文獻(xiàn)[7]采用分子信標(biāo)表面技術(shù)實(shí)現(xiàn)地圖著色問題的DNA計(jì)算，文獻(xiàn)[8]給出了圖的最小頂點(diǎn)覆蓋問題的DNA計(jì)算，文獻(xiàn)[9] 給出了最大匹配問題的粘貼DNA算法。文獻(xiàn)[10] 用微流控DNA計(jì)算解決圖著色問題的DNA算法。本文提出了全信息化的DNA粘貼計(jì)算模型。

1　基于DNA計(jì)算的粘貼模型

1.1粘貼模型

粘貼模型的DNA分子的編碼是一種單鏈和雙鏈混合的序列，存儲混合物由兩種類型的單鏈組成：一種是存儲鏈，另一種是粘貼鏈。一個(gè)存儲鏈含有K個(gè)不重疊區(qū)域的單鏈DNA分子，其中不重疊區(qū)域有M個(gè)堿基；粘貼鏈也是單鏈DNA分子，可以設(shè)計(jì)M個(gè)堿基的粘貼鏈與存儲鏈中的DNA單鏈分子恰好構(gòu)成互補(bǔ)。存儲混合物由粘貼鏈和存儲鏈混合構(gòu)成，如果每個(gè)粘貼鏈的M個(gè)堿基恰與上述存儲區(qū)中的一個(gè)互補(bǔ)，設(shè)其對應(yīng)位為“1”；如果沒有粘貼鏈與匹配位互補(bǔ)，則設(shè)其存儲復(fù)合物表示二進(jìn)制數(shù)的對應(yīng)位為“0”。假設(shè)存儲復(fù)合物的DNA分子編碼如下：

這個(gè)存儲混合共有5位，每位含5個(gè)堿基。DNA單鏈ATTAC GCCCC CATGT CCGTA AAAAT是存儲鏈，較短的DNA單鏈TAATG和單鏈GTACA是粘貼鏈，則這個(gè)存儲物由單鏈和雙鏈混合而成。如果用二進(jìn)制數(shù)來表示位點(diǎn)，則雙鏈表示數(shù)字“1”，單鏈表示數(shù)字“0”，這個(gè)存儲復(fù)合物可以用二進(jìn)制數(shù)表示為10100。

1.2生物操作

對于DNA計(jì)算，首先要對研究對象編碼，其次進(jìn)行一系列生物操作生成解，最后檢測解。在粘貼計(jì)算中，一般把初始試管記為輸入試管，常用四種基本生物操作。

合并把兩個(gè)試管的溶液倒入一個(gè)試管中。兩個(gè)輸入試管T1和T2中的存儲復(fù)合物被合并成一個(gè)新的輸出試管T0。

分離一般通過設(shè)計(jì)探針來實(shí)現(xiàn)。對于輸入試管T0和整數(shù)i,1≤i≤K，如果執(zhí)行分離生物操作的話，將會(huì)產(chǎn)生兩個(gè)新的試管+(T0,i)和-(T0,i)。其中.tif，+(T0,i)表示試管T0中第i位為“1”的所有存儲復(fù)合物試管，即第i位為雙鏈的存儲復(fù)合物；-(T0,i)含有試管T0中第i位為“0”的所有存儲復(fù)合物，即第i位為單鏈的存儲復(fù)合物。分離操作破壞了原始的輸入試管。

設(shè)置通過雜交將原來位點(diǎn)為單鏈的所有存儲復(fù)合物設(shè)置成雙鏈。對于原來試管T0和整數(shù)i,1≤i≤K，設(shè)置操作產(chǎn)生一個(gè)新試管，即無論原來第i位為“1”還是“0”，它將原來試管中所有存儲復(fù)合物的第i位都置為“1”，得到的新試管第i位都為“1”。

清除通過加熱將將存儲復(fù)合物中位點(diǎn)“1”的雙鏈變?yōu)閱捂?。對于試管T0和整數(shù)i,1≤i≤K，清除操作產(chǎn)生新試管clear(T0,i)，試管T0中所有存儲復(fù)合物的第i位上的粘貼鏈都被去掉。

1.3改進(jìn)粘貼模型——全信息化粘貼DNA計(jì)算模型

根據(jù)全信息化的DNA粘貼計(jì)算內(nèi)容，將存儲區(qū)分為3個(gè)基本鏈區(qū)：主鏈區(qū)、輔鏈區(qū)和決策鏈區(qū)，其中主鏈功能是待解問題的數(shù)據(jù)庫，稱為輸入試管；輔鏈?zhǔn)歉鶕?jù)已知條件建立的“存儲庫”；而決策鏈?zhǔn)菣z測問題的解，如圖1所示。主鏈和輔鏈?zhǔn)潜赜?，輔鏈根據(jù)具體問題設(shè)計(jì)，可為多個(gè)輔鏈，決策鏈根據(jù)問題，可有也可能沒有，在本文中，決策鏈則無。

圖1　全信息粘貼DNA計(jì)算模型的存儲鏈

2　基于地圖著色問題改進(jìn)DNA粘貼算法

2.1地圖著色問題

地圖中最著名的問題之一，就是四色猜想問題。畫一張彩色地圖，在相鄰的兩個(gè)不同區(qū)域，應(yīng)當(dāng)涂上不同顏色。這里的相鄰，指的是兩個(gè)區(qū)域有公共邊，而不是只有一二個(gè)公共點(diǎn)。大量實(shí)踐證明，一幅地圖 最多有4種顏色就夠了。

定義1地圖著色是指給地圖的每個(gè)面指定一種顏色，使任意兩個(gè)有公共邊的面顏色不同。若著色時(shí)使用了k種顏色，這個(gè)著色稱為k-著色。

定義2使地圖有一個(gè)k-著色的最小的k稱為地圖的色數(shù)。

定理1地圖問題著色可以轉(zhuǎn)化為圖頂點(diǎn)著色問題。

證明將一幅地圖轉(zhuǎn)化為為一個(gè)無向圖，將地圖中每一個(gè)面記為圖中一個(gè)頂點(diǎn)。將所有相鄰兩個(gè)面用一條無向邊相連，這樣可以得到含有頂點(diǎn)和邊的平面圖G。在這里，假設(shè)平面圖G有n個(gè)頂點(diǎn)，分別記為x1,x2,…,xn，即一個(gè)頂點(diǎn)對應(yīng)一個(gè)面。用xi-xj≠0表示頂點(diǎn)xi和另一個(gè)頂點(diǎn)xj不能著相同顏色，即表示兩個(gè)面相鄰。在平面圖G中，xi和xj有邊連接。

顯然，地圖著色問題可以轉(zhuǎn)化為圖頂點(diǎn)著色問題。

2.2地圖著色算法

將地圖轉(zhuǎn)化為平面圖，即求頂點(diǎn)著色問題。先求圖的一個(gè)最大獨(dú)立集V1，然后求G-V1的最大獨(dú)立集V2，再求G-(V1∪V2)的最大獨(dú)立集V3，如此繼續(xù)，直到最后求出一個(gè)最大獨(dú)立集Vk，則所需色數(shù)ψv(G)=k，即求G的獨(dú)立數(shù)I(G)。由地圖四色理論可知，這里k≤4。生物算法如下：

步驟1主鏈的設(shè)計(jì)。主鏈由平面圖G的n個(gè)頂點(diǎn)x1,x2,…,xn組成。初始時(shí)為單鏈，沒有粘貼鏈。

步驟2輔鏈的設(shè)計(jì)。在輔鏈上直接將圖的頂點(diǎn)相鄰關(guān)系粘貼上去。若圖中頂點(diǎn)xi和xj相鄰，則在輔鏈上對應(yīng)的位段設(shè)置為單鏈，否則設(shè)為雙鏈。

步驟3尋找圖G的一個(gè)最大獨(dú)立集V1。

步驟4求G-V1的最大獨(dú)立集V2，依次類推，可以得到剩余頂點(diǎn)集中的最大獨(dú)立集。得到的獨(dú)立集個(gè)數(shù)即是地圖的著色數(shù)。

3　實(shí) 例

以下通過一個(gè)實(shí)例來詳細(xì)說明上述算法。

圖2　一幅地圖

如圖2所示，將1,2,3,4,5各個(gè)不同的地區(qū)分別標(biāo)記為x1,x2,x3,x4,x5，則可以得到以下的約束條件(1)：

x1-x2≠0，x1-x3≠0，x1-x4≠0，x2-x3≠0，x2-x4≠0，x2-x5≠0，x3-x4≠0，x4-x5≠0。

這個(gè)地圖k-著色問題可以轉(zhuǎn)化為如圖3的一個(gè)無向圖的k-著色問題，即找出滿足(1)式條件的解。由定理可知，圖2可以轉(zhuǎn)化為平面3的平面圖。

圖3　圖2的平面圖表示

圖3中的頂點(diǎn)代表圖2中的區(qū)域。問題轉(zhuǎn)化為求圖頂點(diǎn)著色。解決此問題的關(guān)鍵是粘貼模型的建立，步驟如下：

步驟1主鏈的設(shè)計(jì)。主鏈由圖的頂點(diǎn)序列x1,x2,x3,x4,x5構(gòu)成；輔鏈由頂點(diǎn)xixj的相鄰關(guān)系組成，這些相鄰關(guān)系確定了圖的全部信息。

步驟2粘貼鏈的設(shè)計(jì)。和以往粘貼計(jì)算不同的是，在輔鏈上直接將圖頂點(diǎn)相鄰關(guān)系粘貼上去。若圖中頂點(diǎn)xi和xj相鄰，則在輔鏈上對應(yīng)的位段設(shè)置為單鏈；否則設(shè)為雙鏈，如圖4所示。

把這個(gè)含有主鏈、輔鏈和粘貼鏈的試管稱為初始試管，記為T0。復(fù)制一個(gè)與T0相同的試管，記為T0′。T0′稱為備用試管，在步驟4使用。

步驟3尋找圖G的一個(gè)最大獨(dú)立集V1。具體步驟如下：

(1)從圖G的頂點(diǎn)集V={x1,x2,x3,x4,x5}中隨機(jī)選取l≥2個(gè)頂點(diǎn)子集。為了具有一般性，假設(shè)為xi1,xi2,…，xil；復(fù)制一個(gè)與T0相同的試管，并從中刪除輔鏈中位段xixj，其中xixj或j?{i1,i2,…,il}或i,j?{i1,i2,…,il}，并將操作后的試管仍記為T0。如在圖4中，設(shè)l=3，假設(shè)所取的頂點(diǎn)為x1,x2,x5，則應(yīng)從輔鏈中刪除位段為x1x3,x1x4,x2x3,x2x4,x3x4,x3x5,x4x5。若l=2，假設(shè)選取的頂點(diǎn)為x1,x5，則應(yīng)從輔鏈中刪除位段除x1,x5的所有位段。

(2)在主鏈上并行對l個(gè)頂點(diǎn)所對應(yīng)的主鏈并行實(shí)施設(shè)置操作：Set(T0,xi1,xi2,…，xil)。于是，假設(shè)對頂點(diǎn)子集{x1,x2,x5}和頂點(diǎn)子集{x1,x5}實(shí)施設(shè)置操作，操作后所得的試管仍記為T0。

對頂點(diǎn)子集{x1,x2,x5}所實(shí)施步驟(1)(2)操作后得存儲合成物如圖5(a)所示，操作后所得的試管仍記為T0。圖5(a)中得到的試管混合物{x1,x2,x5}用二進(jìn)制數(shù)可以表示為11001，而試管混合物圖5(b)中得到的試管混合物{x1,x5}可以表示為10001。

圖5　輔鏈和主鏈實(shí)施設(shè)置操作后的示意圖

(3)檢測所得到的解是否是所求問題的解。對試管T0中的存儲鏈并行實(shí)施分離操作，通過設(shè)計(jì)探針來實(shí)現(xiàn)。即對于試管T0和頂點(diǎn)xi1,xi2,…，xil實(shí)施+(T0,xixj)和-(T0,xixj)，其中i,j∈{i1,i2,…,il}且i≠j，若試管T0中的輔鏈全為雙鏈，則{xi1,xi2,…，xil}是圖G的一個(gè)獨(dú)立集，否則不是圖G的一個(gè)獨(dú)立集。

圖6　刪除最大獨(dú)立集后試管中初始鏈

(4)對l(2≤l≤n)從大到小逐一進(jìn)行操作，當(dāng)?shù)谝粋€(gè)非空的子集出現(xiàn)時(shí)，這個(gè)非空集合{xi1,xi2,…，xil}就是圖G的一個(gè)最大獨(dú)立集。本例子中解出一個(gè)最大獨(dú)立集為{x1,x5}。

步驟4求G-V1的最大獨(dú)立集V2。T0′試管中刪除步驟3中最大獨(dú)立集包含的位段，即在主鏈和輔鏈中刪除含有x1,x5的位點(diǎn)，試管仍記為T0。T0中初始鏈的設(shè)計(jì)如圖6所示。

4　結(jié)束語

粘貼模型的優(yōu)點(diǎn)是運(yùn)算過程中一般不需要DNA鏈的延伸，不需要酶的參與，而且材科重復(fù)使用。本文是采用改進(jìn)的全信息化的粘貼DNA計(jì)算模型,生物操作并行處理，理論上可以實(shí)現(xiàn)。

[1]AdlemanLM.MolecularComputationofSolutionstoCombinatorialproblems[J].Science,1994,266(11):1021-1023

[2]Roweis S,Winfree E,Burgoyne R，et al.A sticker-based model for DNA computation[J]. Journal of Computational Biology,1998,5(4):615-629

[3]范月科，強(qiáng)小利，許進(jìn).圖的最大團(tuán)與最大獨(dú)立集粘貼DNA計(jì)算模型[J].計(jì)算機(jī)學(xué)報(bào),2010,33(2):305-310

[4]許進(jìn)，董亞非，魏小鵬，等.粘貼DNA計(jì)算機(jī)模型(I)：理論[J].科學(xué)通報(bào),2004,49(3):205-212

[5]許進(jìn)，董亞非，魏小鵬.粘貼DNA計(jì)算和模型(II)：應(yīng)用[J].科學(xué)通報(bào),2004,49(3):299-307

[6]王麗娜，仲國強(qiáng).基于生物芯片技術(shù)的地圖四著色問題的DNA算法[J].湖北師范學(xué)院學(xué)報(bào)：自然科學(xué)版, 2008, 28(2):26-30

[7]馬季蘭，楊玉星.基于粘貼模型的圖頂點(diǎn)著色問題的DNA算法[J].計(jì)算機(jī)應(yīng)用,2006,26(12):2998-3000

[8]聶曉艷，耿俊，湯建鋼. 圖的最小頂點(diǎn)覆蓋的粘貼DNA計(jì)算模型[J].首都師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2013,34(1):8-12

[9]吳雪，宋晨陽，張陽，等.最大匹配問題的粘貼DNA算法[J].計(jì)算機(jī)科學(xué),2013,40(12):127-140

[10]張勛才，牛瑩，郗方.基于微流控技術(shù)圖頂點(diǎn)著色問題的DNA計(jì)算模型[J].吉林大學(xué)學(xué)報(bào)學(xué)：工學(xué)版,2013,43(1):206-211

(責(zé)任編輯：汪材印)

10.3969/j.issn.1673-2006.2016.10.028

2016-07-11

安徽省自然科學(xué)基金項(xiàng)目(1608085QF149)。

馬瑩(1981-),女,安徽靈璧人,碩士，講師，主要研究方向：圖論、DNA計(jì)算。

TP301

A

1673-2006(2016)10-0110-04