馬瑩++殷志祥

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

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

中圖分類號：TP301 文獻(xiàn)標(biāo)志碼：A 文章編號：1672-1098（2015）02-0064-04

DNA Computing Model for the Graph Vertex Coloring Problem by Plasmids

MA Ying， YIN Zhi-xiang

（School of Science，Anhui University of Science and Technology，Huainan Anhui 232001， China）

Abstract：Graph coloring is a famous NP-problem， which has important practical significance， which applies in channel allocation of communication system， examination room arrangement and so on. There are a lot of DNA computing methods for graph coloring problem， such as surface DNA computing， pasting DNA computing. In the paper the plasmid DNA computing for the graph vertex coloring problem was presented. At first， the graph vertex coloring problem was transformed into a vertex of maximum independent set problem. Then the plasmid DNA molecular biological experiment of graph vertex coloring problem was conducted. The vertexes connected with edges were cut by using the feature of restriction enzymes， and the maximum independent set was obtained. In the experiment a spare tube was introduced. At last， the method was illustrated by an example. In the example the final coloring schemes were given. It was verified that the plasmid DNA algorithm is effective and feasible.

Key words：DNA computing； vertex coloring problem； maximum independent set； plasmid

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

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

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

1 質(zhì)粒

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

11 質(zhì)粒編碼

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

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

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

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

2 圖頂點著色問題的算法設(shè)計

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

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

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

21 圖頂點著色的算法

圖頂點著色算法：

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

具體算法步驟如下：

步驟1：從頂點V中選取頂點，不妨設(shè)為v1，記k=1，Vk={v1}。刪除與頂點v1相鄰的頂點，剩余的頂點假設(shè)記為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） 頂點編碼。每個頂點用寡聚核苷酸片段進(jìn)行編碼，每段的兩端都有特殊酶切位點的序列。例如，頂點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生物算法。對應(yīng)的質(zhì)粒DNA算法具體步驟如下：

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

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

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

步驟4：找到最大獨立集。測序而且記錄DNA分子片段，找到該分子片段所對應(yīng)的頂點，令其記為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所示頂點著色問題來詳細(xì)討論上述算法生物實現(xiàn)步驟。

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

圖2 6個頂點10條邊的圖endprint

步驟2：擴(kuò)增。將合成的DNA分子片段鏈插入到已經(jīng)開口的質(zhì)粒中，這樣形成閉環(huán)狀的質(zhì)粒，再轉(zhuǎn)入大腸桿菌進(jìn)行擴(kuò)增，容易得到數(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中用對應(yīng)的酶Eco RI切掉v1所表示的粘性末端DNA分子片段，并且把切割下來的DNA分子片段和質(zhì)粒分離，使T1中的質(zhì)粒重新環(huán)化，這時T1中質(zhì)粒表示位為011111，即點集{v2，v3，v4，v5，v6}。在試管T2中用對應(yīng)的酶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對應(yīng)頂點v1和v3，在試管T1中用限制性酶Eco RI切割掉v1頂點所表示的粘性末端DNA分子片段，把切割下來的DNA分子片段和質(zhì)粒分離，并且使T1中的質(zhì)粒重新環(huán)化，這時T1中含質(zhì)粒為011111和001111，在T2試管中加入BamH I切割掉e2對應(yīng)頂點v3，并使T2中的顆粒重新環(huán)化，此時T2中質(zhì)粒表示011111和100111。把試管T1和T2合成一新的試管，仍記為T0。T0中含有三種新的質(zhì)粒對應(yīng)的為表示為011111和001111以及100111。

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

再切割和頂點v2相連的頂點（v1除外），依次切割和v3相連的頂點（v1和v2除外），經(jīng)過反復(fù)切割，最終可得試管中的質(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-著色。endprint