圖頂點(diǎn)著色問(wèn)題的質(zhì)粒DNA計(jì)算

馬瑩++殷志祥

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

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

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-1098（2015）01-0000-00

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

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

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

1質(zhì)粒

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

11質(zhì)粒編碼

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

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

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

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

2圖頂點(diǎn)著色問(wèn)題的算法設(shè)計(jì)

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

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

定義2對(duì)圖G的頂點(diǎn)著色需要的最少顏色數(shù)稱為G的點(diǎn)色數(shù)，簡(jiǎn)稱為G的色數(shù)，并用ψv（G）來(lái)表示。

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

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

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

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

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

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

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

21圖頂點(diǎn)著色的算法

圖頂點(diǎn)著色算法：endprint

先求圖G的一個(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）。

具體算法步驟如下：

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

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

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

22圖頂點(diǎn)著色問(wèn)題的DNA計(jì)算模型系統(tǒng)

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

圖1頂點(diǎn)編碼

2） 圖頂點(diǎn)著色問(wèn)題的DNA生物算法。對(duì)應(yīng)的質(zhì)粒DNA算法具體步驟如下：

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

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

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

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

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

3一個(gè)實(shí)例

下面對(duì)圖1所示頂點(diǎn)著色問(wèn)題來(lái)詳細(xì)討論上述算法生物實(shí)現(xiàn)步驟。

步驟1：編碼輸入。對(duì)圖1中的每個(gè)頂點(diǎn)進(jìn)行編碼。

圖26個(gè)頂點(diǎn)10條邊的圖

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

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

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

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

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

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

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

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

4結(jié)束語(yǔ)

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

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

參考文獻(xià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]高琳， 馬潤(rùn)年， 許進(jìn)，基于質(zhì)粒DNA匹配問(wèn)題的分子算法[J]. 生物化學(xué)與生物物理進(jìn)展， 2002， 29（5）： 820-823.

[6]高 琳， 許 進(jìn)， 圖的頂點(diǎn)著色問(wèn)題的DNA算法[J]. 電子學(xué)報(bào)， 2004， 31（4）： 494-497.

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

[8]馬季蘭，楊玉星. 基于粘貼模型的圖頂點(diǎn)著色問(wèn)題的DNA算法[J].計(jì)算機(jī)應(yīng)用，200626（12）： 2 998-3 000.

[9]強(qiáng)小利. 圖頂點(diǎn)著色問(wèn)題的DNA計(jì)算模型. 計(jì)算機(jī)學(xué)報(bào)， 2009， 32（12）： 2 332-2 336

（責(zé)任編輯：）endprint