馬瑩++殷志祥

摘要：圖的著色問題是著名的NP問題，有著重要的實際意義。比如通訊系統(tǒng)的頻道分配、考試排考場問題等方面有直接應用。圖的著色問題采用DNA計算方法很多，有表面DNA計算，粘貼DNA計算。本文提出質(zhì)粒DNA計算，首先把頂點著色問題轉(zhuǎn)化為求最大獨立集問題，然后給出了圖頂點著色問題的質(zhì)粒DNA分子生物實驗，利用限制性內(nèi)切酶的特性切割有邊相連的頂點，得到最大獨立集，在試驗中特別引入了一個備用試管，最后給出一個具體的實例。實例給出具體的著色方案，證明了該質(zhì)粒DNA算法有效并且是可行的。

關(guān)鍵詞：DNA計算；頂點著色；最大獨立集；質(zhì)粒

中圖分類號：TP301 文獻標志碼：A

文章編號：1672-1098（2015）01-0000-00

1994年，Adleman首次用DNA計算解決有向圖的哈密頓問題[1]；1995年P(guān)rinceton大學的Lipton在Adleman思想的啟發(fā)下，解決了可滿足性問題[2]；1997年，Ouyang等利用DNA計算解決了另一個NP完全問題，圖的最大團問題[3]；2000年，Head提出了用質(zhì)粒DNA分子來解決可滿足性問題[4]；2004年，高琳，許進提出了基于質(zhì)粒DNA匹配問題的分子算法[5]。

圖頂點著色問題是著名的NP問題。2003年，高琳討論了圖的3-頂點著色的DNA算法[6]；2005年，王淑棟提出了先 把 著色 問 題分 解 成 頂 點 獨 立 集 問題 和 頂 點 劃 分問 題 并 給 出 這兩 個問 題的 D N A 粘貼算法，并調(diào)用這兩個算法解決了圖頂點著色問題[7]；2006年，馬季蘭提出將圖的頂點著色問題轉(zhuǎn)化為SAT-問題來解，并且利用粘貼DNA計算來解決[8]；2009年，強小利建立了一種基于酶切技術(shù)和PCR技術(shù)的圖頂點著色DNA計算模型，給出了實現(xiàn)該模型的雙編碼的編碼方案[9]。

本文提出基于質(zhì)粒的DNA計算求解圖的頂點著色問題，從圖頂點著色問題的本質(zhì)出發(fā)，把圖的頂點著色問題轉(zhuǎn)化成圖的頂點劃分問題。

1質(zhì)粒

質(zhì)粒是染色體外小型的共價、閉合、環(huán)狀的雙鏈DNA分子，是含有復制功能的遺傳結(jié)構(gòu)的DNA分子。目前DNA計算中采用的質(zhì)粒是閉環(huán)狀的雙鏈DNA分子，常用人工構(gòu)建的質(zhì)粒作為載體。常用的人工質(zhì)粒運載體有pBR322、pSC101，必須包含三個特征：復制子、選擇性標志和克隆位點?？寺∥稽c是限制性內(nèi)切酶切割位點，外源性DNA可由此插入質(zhì)粒內(nèi)，而且并不影響質(zhì)粒的復制能力。用限制性核酸內(nèi)切酶和DNA鏈接酶可以對質(zhì)粒進行剪切和重組。每位與唯一的限制性酶相對應，每位都以它對應的限制性酶為識別位點。

11質(zhì)粒編碼

給一個質(zhì)粒 DNA 環(huán)狀分子進行編碼，設P是一個質(zhì)粒載體，k是正整數(shù)，s1，s2，…，sk是P的k個相互不重疊的子段。對于每個i，核苷酸序列si不能出現(xiàn)在質(zhì)粒P的其余位置上，并稱si是質(zhì)粒P的“位置”。通過切割和粘貼，質(zhì)粒在“位置”處不斷地修改，相應的核苷酸序列si要么在質(zhì)粒上，要么不在，分別用1和0表示。質(zhì)粒DNA的位為1表示這個位對應的頂點在質(zhì)粒DNA對應的頂點集中，質(zhì)粒DNA的位為0表示這個位對應的頂點不在對應的頂點集中。 例如： 質(zhì)粒111111表示頂點集{v1，v2，v3，v4，v5，v6}， 質(zhì)粒 100001 表示頂點集{v1，v6}。

12限制性內(nèi)切酶

生物體內(nèi)能識別并切割特異的雙鏈DNA序列的一種內(nèi)切核酸酶。限制酶的名字根據(jù)最初分離出限制酶的生物體所命名，第一個字母取自屬名的第一個字母，隨后的兩個字母取自種名的前兩個字母，第四個字母表示菌株（品系）。例如Bam H，表示從Bacillus amylolique faciens H中分離出來的限制內(nèi)切酶。通常，限制性內(nèi)切酶僅剪切雙鏈DNA分子，而且只在一些特定的位置上剪切。下表1列出常用的限制性內(nèi)切酶的識別位點，其中箭頭表示切割位點。

表1限制性內(nèi)切酶識別位點

2圖頂點著色問題的算法設計

設G是一個圖，分別用V，E，ψv（G），Δ（v），p和q表示圖G的頂點集，邊集，G的點色數(shù)，頂點v的度，頂點數(shù)和邊數(shù)。

定義1設G為任意圖且C代表顏色集合，如果存在映射σ∶V（G）→C使得對任意uv∈E（G），σ（u）≠σ（v），則稱σ為G的頂點著色法，即對G的每個頂點用C中的某種顏色著色使得每個頂點只染一種顏色，且相鄰兩個頂點不能染同種顏色。

定義2對圖G的頂點著色需要的最少顏色數(shù)稱為G的點色數(shù)，簡稱為G的色數(shù)，并用ψv（G）來表示。

定義3對圖G=（V，E）的結(jié)點子集SV，如果

1） S中的任意兩個結(jié)點均不相鄰，則稱S為G的一個獨立集。

2） 若S是G的獨立集，且不存在G的另一獨立集S′滿足|S′|>|S|，則稱S為G的最大獨立集。

定義4對于無向圖G（V，E），將其頂點集V劃分為互不相交的多個非空子集V1，V2，…，Vm，使得V1∩V2∩…∩Vm=V，且Vi∩Vj=，其中i，j=1，2，…，m，i≠j，則V1，V2，…，Vm稱為G=（V，E）的頂點一個劃分。

定理1對任意圖G，有ψv（G）≤Δ+1。

證：對圖的結(jié)點數(shù)n作歸納證明，當n=1時，即圖只有一個結(jié)點，ψv（G）=1，定理顯然成立。設結(jié)點數(shù)為n-1時定理成立，現(xiàn)增加一個結(jié)點v0，則與v0鄰接的結(jié)點最多有Δ個，即使這些結(jié)點都著不同顏色，也不會超過Δ種顏色，則給v0著不同顏色，色數(shù)不會超過Δ+1，定理亦成立。

由于獨立集內(nèi)的所有結(jié)點可著同一顏色，如果將圖的頂點進行劃分，使每一結(jié)點子集都是獨立集，即最小劃分數(shù)即是圖的點色數(shù)。

21圖頂點著色的算法

圖頂點著色算法：endprint

先求圖G的一個最大獨立集V1，然后求G-V1的最大獨立集V2，然后再求G-（V1∪V2）的最大獨立集V3，如此繼續(xù)直到最后一個最大獨立集Vk，則所需色數(shù)ψv（G）=k，即求G的獨立數(shù)I（G）。

具體算法步驟如下：

步驟1：從頂點V中選取頂點，不妨設為v1，記k=1，Vk={v1}。刪除與頂點v1相鄰的頂點，剩余的頂點假設記為vi，vj加入Vk={v1，vi，vj}集合中，Vk即為所有頂點中的最大獨立集。n為Vk中元素的個數(shù)。

步驟2：如果n=|V（G）|，則k為頂點著色數(shù)；否則執(zhí)行下一步。

步驟3：把k換成k+1，繼續(xù)找剩下頂點中最大獨立集Vk，按順序找出頂點記為vm（vm為不在Vk中的頂點），記Vk={vm}，刪除與vm相鄰的頂點，剩下的頂點加入到Vk，n為V1，V2，…Vk中所有元素的個數(shù)，轉(zhuǎn)步驟2。

22圖頂點著色問題的DNA計算模型系統(tǒng)

1） 頂點編碼。每個頂點用寡聚核苷酸片段進行編碼，每段的兩端都有特殊酶切位點的序列。例如，頂點v1 用A，T，C，G隨意編碼，長度為50 bp，其兩端含有限制酶Eco RI的識別序列為5′-GAATTC，其分割點在G與A之間，這樣通過Eco RI作用就可以將v1從鏈上切除。Station2表示頂點v2所在的位置，其兩端含有Pst I的識別序列式5′-CTGCAG，類似通過Pst I作用可將v2從鏈上切除。頂點編碼成質(zhì)粒形式見圖1。

圖1頂點編碼

2） 圖頂點著色問題的DNA生物算法。對應的質(zhì)粒DNA算法具體步驟如下：

步驟1：編碼。給頂點進行DNA編碼，每個頂點用A，T，G，C進行編碼，長度可以在40 kb至50 kb之間，在每個頂點的兩端連接限制性內(nèi)切酶。將編碼好的DNA片段放入試管中。將編碼好的DNA片段鏈插入到已開口質(zhì)粒中，這樣可以形成環(huán)狀的雙鏈DNA質(zhì)粒。

步驟2：擴增。將細菌質(zhì)粒轉(zhuǎn)化到大腸桿菌中進行擴增，可以得到數(shù)量足夠多的新質(zhì)粒，用試管T0表示。

步驟3：切割。檢查試管T0中任意兩條邊之間是否有頂點連接。如果都沒有頂點相連，轉(zhuǎn)入步驟4，否則假設有邊ei和邊ej相連對應的頂點為vm，將步驟2所產(chǎn)生的新的質(zhì)粒的試管T0分成相等的三個試管，一個試管單獨放置（步驟4使用），然后檢查所有和vm相連的邊，另外兩個試管中分別加入切割有邊相連的兩個頂點所對應內(nèi)切酶，然后把切割下小的DNA片段和質(zhì)粒分離，最后使質(zhì)粒重新環(huán)化，合成一個試管。返回步驟2。

步驟4：找到最大獨立集。測序而且記錄DNA分子片段，找到該分子片段所對應的頂點，令其記為Vk（k=1，2…）。如果V1，V2，…，Vk中總的頂點數(shù)恰好等于圖G的頂點數(shù)，則轉(zhuǎn)步驟5；否則，再用試管T0（步驟2中的初始試管）切割V1，V2，…，Vk頂點，把切割下小來的DNA分子片段和質(zhì)粒分離，使質(zhì)粒重新環(huán)化，合成一個試管，轉(zhuǎn)步驟2。

步驟5：k即為著色數(shù)，則V1，V2，…，Vk中的頂點集為同一種顏色。

3一個實例

下面對圖1所示頂點著色問題來詳細討論上述算法生物實現(xiàn)步驟。

步驟1：編碼輸入。對圖1中的每個頂點進行編碼。

圖26個頂點10條邊的圖

步驟2：擴增。將合成的DNA分子片段鏈插入到已經(jīng)開口的質(zhì)粒中，這樣形成閉環(huán)狀的質(zhì)粒，再轉(zhuǎn)入大腸桿菌進行擴增，容易得到數(shù)量足夠多的實驗所需要的新質(zhì)粒，仍用用試管T0表示。

步驟3：剪切。將試管T0分成三個相同的試管T′0、T1和T2。T′0為備用試管，在步驟4中使用。此時試管中質(zhì)粒位為111111，即點集{v1，v2，v3，v4，v5，v6}。首先，對頂點v1所有連接的點全部切割掉，則剩下的點即與v1不連接。對邊e1頂點v1與其相鄰的頂點v2，在試管T1中用對應的酶Eco RI切掉v1所表示的粘性末端DNA分子片段，并且把切割下來的DNA分子片段和質(zhì)粒分離，使T1中的質(zhì)粒重新環(huán)化，這時T1中質(zhì)粒表示位為011111，即點集{v2，v3，v4，v5，v6}。在試管T2中用對應的酶Pst I切掉v1所表示的粘性末端DNA分子片段，把切割下來的DNA分子片段和質(zhì)粒分離，并且使T1中的顆粒重新環(huán)化，這時T2中質(zhì)粒表示位為101111，即點集{v1，v3，v4，v5，v6}。把試管T1和T2合成一新的試管，仍記為T0。若圖中無邊則表示圖可劃分為{v1，v3，v4，v5，v6}和{v2}，或者{v2，v3，v4，v5，v6}和{v1}，圖為2-可著色。

將試管T0分成兩個相同的試管T1和T2。對于邊e2對應頂點v1和v3，在試管T1中用限制性酶Eco RI切割掉v1頂點所表示的粘性末端DNA分子片段，把切割下來的DNA分子片段和質(zhì)粒分離，并且使T1中的質(zhì)粒重新環(huán)化，這時T1中含質(zhì)粒為011111和001111，在T2試管中加入BamH I切割掉e2對應頂點v3，并使T2中的顆粒重新環(huán)化，此時T2中質(zhì)粒表示011111和100111。把試管T1和T2合成一新的試管，仍記為T0。T0中含有三種新的質(zhì)粒對應的為表示為011111和001111以及100111。

將試管T0分成兩個相同的試管T1和T2。對于邊e3對應頂點v1和v4，在試管T1中用相應的限制性酶Eco RI切割掉v1所代表的粘性末端DNA片段，把切下來的DNA片段和質(zhì)粒分離，并使T1中的顆粒重新環(huán)化，此時T1中含質(zhì)粒為011111， 001111和000111，在T2試管中加入Sal I切割掉e3對應頂點v4，并使T2中的顆粒重新環(huán)化，此時T2中質(zhì)粒表示011111，001111和100011。把試管T1和T2合成一新的試管，仍記為T0。T0中含有四種新的質(zhì)粒對應的為表示為011111，001111和000111以及1000111。endprint

再切割和頂點v2相連的頂點（v1除外），依次切割和v3相連的頂點（v1和v2除外），經(jīng)過反復切割，最終可得試管中的質(zhì)粒表示為000001，000010，001001，000110，10000，011001，即表示頂點集{v6}，{v5}，{v3，v6}，{v4，v5}，{v1，v6}，{v2，v3，v6}，即最大獨立集為{v2，v3，v6}。

步驟4：測序。通過凝膠電泳實驗找出鏈長最長的質(zhì)粒，用分子克隆技術(shù)確定長度最大的質(zhì)粒，它所代表的編碼就是最大頂點獨立集{v2，v3，v6}。

步驟5：從剩余頂點中求最大頂點獨立集。在步驟2中備用試管T′0中切割v2，v3，v6，則試管T′0中仍含有頂點v1，v4，v5，轉(zhuǎn)入步驟2，尋找T′0的最大獨立集，可求得{v4，v5}為最大獨立集。

從剩余頂點中求最大頂點獨立集。在步驟2中備用試管T′0中切割v4，v5，則試管T′0中只含有頂點v1，顯然，圖可劃分為{v2，v3，v6}，{v4，v5}，{v1}，即圖可3-著色。

4結(jié)束語

文獻[7]求頂點著色時求的是最大獨立集問題和圖劃分問題，采用的是粘貼DNA計算而且需要單獨進行兩個實驗；而本文求解圖的最大獨立集問題和圖劃分問題只需要一個實驗，而且實驗時引入了三個試管，在質(zhì)粒進行分離操作時，引入了一個備用試管，這大大簡化了實驗的操作，盡可能減少了實驗的誤差，最后本文給出實例驗證算法的可行性。

本文在試驗時，采用的是質(zhì)粒的切割、環(huán)化和分離過程，質(zhì)粒始終保持了DNA雙鏈形式，避免了DNA退火以及PCR擴增。但是，由于內(nèi)切酶的種類有限，也限制了圖的規(guī)模不宜太大，還有頂點對應不同的邊需要酶切，酶切的過程可能會產(chǎn)生非特異性酶，這是今后的研究中需要改進的方面。

參考文獻：

[1]Adleman L. Molecular computation of solution to combinatorial problems[J]. Science， 1994， 266（11）：1 021-1 024.

[2]Lipton R J. DNA solution of computation problems.[J]. Science，1995， 268 （4）：542-545.

[3]Quyang Q，Kaplan P D. Liu S et al. Solution of the maximal clique problem[J]. Science，1997， 278（17）： 446-449.

[4]Head T， Rozenberg G. Computing with DNA by operating on plasmids[J]. Biosystems[J]， 2000（57）： 87-93.

[5]高琳， 馬潤年， 許進，基于質(zhì)粒DNA匹配問題的分子算法[J]. 生物化學與生物物理進展， 2002， 29（5）： 820-823.

[6]高 琳， 許 進， 圖的頂點著色問題的DNA算法[J]. 電子學報， 2004， 31（4）： 494-497.

[7]王淑棟， 劉文斌， 許進. 圖頂點著色問題的DNA粘貼算法[J]. 系統(tǒng)工程與電子技術(shù)， 2005， 27（3）： 568-572.

[8]馬季蘭，楊玉星. 基于粘貼模型的圖頂點著色問題的DNA算法[J].計算機應用，200626（12）： 2 998-3 000.

[9]強小利. 圖頂點著色問題的DNA計算模型. 計算機學報， 2009， 32（12）： 2 332-2 336

（責任編輯：）endprint