地圖著色問題的DNA計算

馬　瑩，方　歡

安徽理工大學理學院,安徽淮南，232001

?

地圖著色問題的DNA計算

馬瑩，方歡

安徽理工大學理學院,安徽淮南，232001

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

DNA計算；粘貼計算；地圖著色問題；頂點著色；最大獨立集

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

1　基于DNA計算的粘貼模型

1.1粘貼模型

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

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

1.2生物操作

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

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

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

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

清除通過加熱將將存儲復合物中位點“1”的雙鏈變為單鏈。對于試管T0和整數i,1≤i≤K，清除操作產生新試管clear(T0,i)，試管T0中所有存儲復合物的第i位上的粘貼鏈都被去掉。

1.3改進粘貼模型——全信息化粘貼DNA計算模型

根據全信息化的DNA粘貼計算內容，將存儲區分為3個基本鏈區：主鏈區、輔鏈區和決策鏈區，其中主鏈功能是待解問題的數據庫，稱為輸入試管；輔鏈是根據已知條件建立的“存儲庫”；而決策鏈是檢測問題的解，如圖1所示。主鏈和輔鏈是必有，輔鏈根據具體問題設計，可為多個輔鏈，決策鏈根據問題，可有也可能沒有，在本文中，決策鏈則無。

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

2　基于地圖著色問題改進DNA粘貼算法

2.1地圖著色問題

地圖中最著名的問題之一，就是四色猜想問題。畫一張彩色地圖，在相鄰的兩個不同區域，應當涂上不同顏色。這里的相鄰，指的是兩個區域有公共邊，而不是只有一二個公共點。大量實踐證明，一幅地圖 最多有4種顏色就夠了。

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

定義2使地圖有一個k-著色的最小的k稱為地圖的色數。

定理1地圖問題著色可以轉化為圖頂點著色問題。

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

顯然，地圖著色問題可以轉化為圖頂點著色問題。

2.2地圖著色算法

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

步驟1主鏈的設計。主鏈由平面圖G的n個頂點x1,x2,…,xn組成。初始時為單鏈，沒有粘貼鏈。

步驟2輔鏈的設計。在輔鏈上直接將圖的頂點相鄰關系粘貼上去。若圖中頂點xi和xj相鄰，則在輔鏈上對應的位段設置為單鏈，否則設為雙鏈。

步驟3尋找圖G的一個最大獨立集V1。

步驟4求G-V1的最大獨立集V2，依次類推，可以得到剩余頂點集中的最大獨立集。得到的獨立集個數即是地圖的著色數。

3　實 例

以下通過一個實例來詳細說明上述算法。

圖2　一幅地圖

如圖2所示，將1,2,3,4,5各個不同的地區分別標記為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。

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

圖3　圖2的平面圖表示

圖3中的頂點代表圖2中的區域。問題轉化為求圖頂點著色。解決此問題的關鍵是粘貼模型的建立，步驟如下：

步驟1主鏈的設計。主鏈由圖的頂點序列x1,x2,x3,x4,x5構成；輔鏈由頂點xixj的相鄰關系組成，這些相鄰關系確定了圖的全部信息。

步驟2粘貼鏈的設計。和以往粘貼計算不同的是，在輔鏈上直接將圖頂點相鄰關系粘貼上去。若圖中頂點xi和xj相鄰，則在輔鏈上對應的位段設置為單鏈；否則設為雙鏈，如圖4所示。

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

步驟3尋找圖G的一個最大獨立集V1。具體步驟如下：

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

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

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

圖5　輔鏈和主鏈實施設置操作后的示意圖

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

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

(4)對l(2≤l≤n)從大到小逐一進行操作，當第一個非空的子集出現時，這個非空集合{xi1,xi2,…，xil}就是圖G的一個最大獨立集。本例子中解出一個最大獨立集為{x1,x5}。

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

4　結束語

粘貼模型的優點是運算過程中一般不需要DNA鏈的延伸，不需要酶的參與，而且材科重復使用。本文是采用改進的全信息化的粘貼DNA計算模型,生物操作并行處理，理論上可以實現。

[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]范月科，強小利，許進.圖的最大團與最大獨立集粘貼DNA計算模型[J].計算機學報,2010,33(2):305-310

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

[5]許進，董亞非，魏小鵬.粘貼DNA計算和模型(II)：應用[J].科學通報,2004,49(3):299-307

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

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

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

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

[10]張勛才，?，?，郗方.基于微流控技術圖頂點著色問題的DNA計算模型[J].吉林大學學報學：工學版,2013,43(1):206-211

(責任編輯：汪材印)

10.3969/j.issn.1673-2006.2016.10.028

2016-07-11

安徽省自然科學基金項目(1608085QF149)。

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

TP301

A

1673-2006(2016)10-0110-04