基于自組裝納米顆粒的頂點(diǎn)著色問題的DNA計(jì)算模型

陳芳，殷志祥

（安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，淮南 232001）

頂點(diǎn)著色問題是圖論中一個(gè)經(jīng)典的組合優(yōu)化問題，屬于NP完全問題，傳統(tǒng)的算法無法有效的解決此類NP問題。隨著分子生物學(xué)的發(fā)展，人們將DNA計(jì)算引入到NP問題中，著手利用DNA分子的高并行性和高信息儲存量的優(yōu)勢來求解NP問題。1994年，Adleman教授[1]首次提出了使用生物分子來求解NP問題，并成功的求解了一個(gè)7個(gè)頂點(diǎn)的有向Hamilton路問題，開創(chuàng)了DNA計(jì)算的先河；文獻(xiàn)[2]將圖的頂點(diǎn)及顏色進(jìn)行適當(dāng)編碼，借助生物酶的作用，實(shí)現(xiàn)了著色方案的生成與篩選；文獻(xiàn)[3]建立了一種基于酶切技術(shù)和PCR技術(shù)的圖頂點(diǎn)著色的DNA計(jì)算模型，使得模型實(shí)現(xiàn)充分的自動化操作；文獻(xiàn)[4]將問題進(jìn)行了轉(zhuǎn)化，利用求解最大獨(dú)立集的思想來進(jìn)行編碼，利用質(zhì)粒DNA分子來進(jìn)行試驗(yàn)，有效的得到了圖的著色方案；文獻(xiàn)[5]提出了一種基于微流控制來求解圖頂點(diǎn)著色的DNA計(jì)算模型，實(shí)現(xiàn)了模型的自動化，提高了DNA計(jì)算的可靠性；文獻(xiàn)[6]利用分子自組裝，構(gòu)建瓦片粘貼模型來求解圖頂點(diǎn)著色問題，著色方案清晰易讀；文獻(xiàn)[7]構(gòu)造了一個(gè)發(fā)夾結(jié)構(gòu)探針，將頂點(diǎn)進(jìn)行適當(dāng)編碼，直接生成解空間，利用常規(guī)生物操作即可獲得著色方案。

DNA自組裝是指DNA分子通過分子間的相互作用力，形成的一種較為穩(wěn)定、結(jié)構(gòu)更復(fù)雜的分子結(jié)構(gòu)的過程。20世紀(jì)80年代，Seeman[8]就提出DNA能通過堿基互補(bǔ)配對產(chǎn)生穩(wěn)定的連接結(jié)構(gòu)，并且可以精確組裝復(fù)雜多維空間對象，并稱之為結(jié)構(gòu)DNA納米技術(shù)。在自組裝技術(shù)誕生以來，人們利用該方法，求解了許多圖論中的問題[9-16]。文獻(xiàn)[17]結(jié)合3維的DNA自組裝模型求解了圖頂點(diǎn)著色問題，利用DNA分子的巨大并行性，在線性時(shí)間內(nèi)求得了最佳方案。納米材料作為一種新材料，已經(jīng)被廣泛應(yīng)用于生物學(xué)領(lǐng)域，具有制備便宜、生物穩(wěn)定性好等天然優(yōu)勢。結(jié)合自組裝納米材料，文獻(xiàn)[13]求解了最大團(tuán)問題，在生成和刪除非解只需操作一次即可，簡化了傳統(tǒng)模型的操作過程。該文借助納米金屬顆粒來求解圖的頂點(diǎn)著色問題，利用DNA自組裝，將納米顆粒組裝成所需要的結(jié)構(gòu)，通過堿基的互補(bǔ)配對原則生成和篩選著色方案。由于DNA分子的巨大并行性，將會有效的減少運(yùn)算的時(shí)間和空間復(fù)雜度。

1 頂點(diǎn)著色問題

在本文中提到的圖均是指有限、無環(huán)、無重邊的無向簡單圖。通常用V(G)和E(G)分別表示圖的頂點(diǎn)集和邊集。圖G的頂點(diǎn)著色問題就是指給圖G的每一個(gè)頂點(diǎn)進(jìn)行著色，并且使得任意相鄰的兩個(gè)頂點(diǎn)分配到不同的顏色。而求頂點(diǎn)著色問題又可以轉(zhuǎn)化為求最大獨(dú)立集問題，也就是說，簡單圖G的一個(gè)k-頂點(diǎn)著色，就是將頂點(diǎn)集V(G)劃分成k個(gè)獨(dú)力集的分類{v1,v2…vk}，其中vi(i=1,2…k)是G的獨(dú)立集，滿足v(G)=v1?v2?…?vk，vi≠? ，vi?vj=?，i,j=1,2…k。如果用集合C(k)表示k種顏色，則有C(k)={1,2…k}。更確切地說，求解圖頂點(diǎn)著色問題就是尋找從頂點(diǎn)集v(G)到顏色集C(k)的一個(gè)映射f:v(G)→C(k)，并且映射f滿足u,v∈V(G),uv∈E(G)，f(u)≠f(v)。記全體G的k-著色f構(gòu)成的集合為Ck(G)，當(dāng)集合Ck(G)≠?的時(shí)候，稱圖G是k-頂點(diǎn)著色的。在本文中，僅考慮圖的3-頂點(diǎn)著色，圖1為一個(gè)具有6個(gè)頂點(diǎn)的簡單圖。

圖1 6個(gè)頂點(diǎn)的簡單圖

2 計(jì)算模型

2.1 基本算法

步驟1 利用自組裝的金屬顆粒對應(yīng)每個(gè)頂點(diǎn)；

步驟2 利用DNA堿基互補(bǔ)配對生成數(shù)據(jù)池；

步驟3 刪除不滿足條件的解；

步驟4 輸出著色方案。

2.2 生物算法

步驟1（1）構(gòu)造代表頂點(diǎn)的納米金屬顆粒：納米金屬顆粒由兩部分組成，主體結(jié)構(gòu)為納米金屬顆粒，并且每個(gè)金屬顆粒都帶有連接DNA。在圖1的3-著色問題中每個(gè)頂點(diǎn)有三種方案可選擇，因此針對于每個(gè)頂點(diǎn)，需要設(shè)計(jì)3種不同的納米金屬顆粒。在n個(gè)頂點(diǎn)的圖中，一共需要構(gòu)造3n個(gè)納米金屬顆粒。

（2）構(gòu)造連接探針：根據(jù)步驟（1）中的連接DNA，構(gòu)造連接探針，連接探針由兩部分組成，第一部分與前面相接的納米金屬顆粒的連接DNA互補(bǔ)，第二部分與后面相接的納米金屬顆粒的連接DNA互補(bǔ)。在具有n個(gè)頂點(diǎn)圖的3-著色問題中，需要個(gè)3×3×(n-1)=9(n-1)個(gè)連接探針。

步驟2 將納米金屬顆粒同連接探針加入到溶液中進(jìn)行生化反應(yīng)，根據(jù)堿基互補(bǔ)配對會生成串珠狀結(jié)構(gòu)，即初始數(shù)據(jù)池。

步驟3 在數(shù)據(jù)池中，含有非解，需要進(jìn)行篩選。構(gòu)造刪除探針，刪除探針結(jié)構(gòu)與頂點(diǎn)的結(jié)構(gòu)相同，主體部分為納米金屬顆粒，兩端連接有單鏈DNA，兩端的單鏈DNA分別是相鄰頂點(diǎn)的連接DNA的補(bǔ)鏈。這樣將刪除探針加入到數(shù)據(jù)池中后，如果相鄰兩個(gè)頂點(diǎn)著相同顏色，刪除探針會與代表該方案的串珠進(jìn)行雜交反應(yīng)，串珠的質(zhì)量與結(jié)構(gòu)會發(fā)生改變。

步驟4 借助凝膠電泳技術(shù)來對非解進(jìn)行剔除，因?yàn)閿?shù)據(jù)池中的非解在加入刪除探針過后，質(zhì)量與體積都會增大，在進(jìn)行電泳分離的過程中，非解的移動速度慢，因此可以通過分離來得到解。最后采用非放射性標(biāo)記DNA測序的方法進(jìn)行測序，可以具體得到每個(gè)頂點(diǎn)的著色方案。

3 算法實(shí)例

結(jié)合圖1為例，求解圖的3-著色問題。

步驟1（1）將圖1的每一個(gè)頂點(diǎn)對應(yīng)自組裝為納米金屬顆粒，因?yàn)槊總€(gè)頂點(diǎn)都有三種可著色的情況，因此針對于每個(gè)頂點(diǎn)，需要設(shè)計(jì)三種不同的帶有特定單鏈的DNA納米金屬顆粒。并且為了方便后續(xù)對解的檢測，所選取的每個(gè)納米顆粒的分子量都是相同的，這使得他們在凝膠電泳中的遷移速度是相同的。當(dāng)頂點(diǎn)為紅色（R）時(shí)，對應(yīng)于納米金顆粒，記為Rn；當(dāng)頂點(diǎn)為綠色（G）時(shí)，對應(yīng)于納米銀顆粒，記為Gn；當(dāng)頂點(diǎn)為黃色（Y）時(shí)，對應(yīng)于納米銅顆粒，記為Yn。（其中n表示的是頂點(diǎn)編號，如R1代表頂點(diǎn)1為紅色，G2代表頂點(diǎn)2為綠色）。每一個(gè)代表頂點(diǎn)的納米顆粒都有一個(gè)線性的單鏈DNA與其連接，稱它為連接DNA（這樣自組裝可以使得代表頂點(diǎn)的納米顆粒與其他的納米顆粒能夠相連接）。并且應(yīng)該注意到，為了使代表頂點(diǎn)的納米顆粒能夠按照順序進(jìn)行連接，需要將序號位于首尾的頂點(diǎn)組裝一條連接DNA，序號位于中間的頂點(diǎn)組裝兩條連接DNA。在此設(shè)計(jì)納米金屬顆粒的連接DNA：納米金顆粒上的連接DNA用Sn來表示；納米銀顆粒上的連接DNA用Mn來表示；納米銅顆粒上的連接DNA用Ln來表示。（其中n表示的是頂點(diǎn)編號，如S1代表頂點(diǎn)1為紅色的連接DNA，M1代表頂點(diǎn)1為綠色時(shí)的連接DNA，也可更進(jìn)一步表示為R1-S1和G1-M1）。通過觀察圖1可知，頂點(diǎn)1、5，頂點(diǎn)2、4，頂點(diǎn)1、6也是有邊連接的，為了后面對這些不是通過鄰邊連接的頂點(diǎn)進(jìn)行篩選操作，需要加上可對頂點(diǎn)1、2、4、5、6進(jìn)行識別的探針，并將其記為d。部分頂點(diǎn)的設(shè)計(jì)如圖2[13]所示。

圖2 部分頂點(diǎn)的設(shè)計(jì)

（2）以上設(shè)計(jì)了代表頂點(diǎn)的納米顆粒以及連接DNA，現(xiàn)在為了使每個(gè)頂點(diǎn)能夠進(jìn)行有序連接，需要設(shè)計(jì)能夠?qū)㈨旤c(diǎn)進(jìn)行連接的探針。探針共由兩部分組成：第一部分與前面所連接的納米顆粒的連接DNA互補(bǔ)，第二部分與后面所連接的納米顆粒的連接DNA互補(bǔ)。在圖1中，所要研究的是3-頂點(diǎn)著色問題，因此每個(gè)頂點(diǎn)有三種連接DNA。由于圖1具有6個(gè)頂點(diǎn)，要滿足依次相連，需要5個(gè)連接探針，因此一共需要設(shè)計(jì)(3×3×5=45)種連接探針，連接探針的具體設(shè)計(jì)見圖3。

圖3 連接探針的設(shè)計(jì)

在依次相鄰的頂點(diǎn)中，若要滿足頂點(diǎn)著色的定義，兩個(gè)相鄰的頂點(diǎn)一定不能連接相同的顏色，所以不需要設(shè)計(jì)相鄰頂點(diǎn)顏色相同的連接探針，即無需設(shè)計(jì)圖3中虛線框中的連接探針。

步驟2 將代表頂點(diǎn)的納米金顆粒和連接探針同時(shí)加入到溶液中進(jìn)行生化反應(yīng)，由于連接探針的設(shè)計(jì)，納米金顆粒會按照頂點(diǎn)的序號依次進(jìn)行排列，即生成了初始的數(shù)據(jù)池，并且該數(shù)據(jù)池滿足依次排列的頂點(diǎn)著不同的顏色。部分結(jié)果圖4所示。

圖4 數(shù)據(jù)池的生成

步驟3（1）在按照上面的方法，生成了所有可能的三著色情況，并且滿足了在序號依次排列時(shí)，每相鄰的兩個(gè)頂點(diǎn)為不同的顏色。現(xiàn)在需要對其他相鄰的兩個(gè)頂點(diǎn)的顏色進(jìn)行檢驗(yàn)，即刪除部分不滿足條件的解。結(jié)合圖1來看，除了依次相鄰的頂點(diǎn)連接，還有頂點(diǎn)2、4，頂點(diǎn)1、5，頂點(diǎn)1、6相連，為了滿足這個(gè)三組相鄰的頂點(diǎn)也互相為不同的顏色，需要設(shè)計(jì)相應(yīng)的刪除探針，記為探針Dn-m（其中n、m分別指在圖中有被鄰邊之外的邊所連接的頂點(diǎn)）。刪除探針的主體結(jié)構(gòu)為納米金顆粒，兩端連接有單鏈DNA。刪除探針的結(jié)構(gòu)如圖5所示。

圖5 刪除探針的設(shè)計(jì)

（2）在初始數(shù)據(jù)池中，加入刪除探針，如果相鄰的兩個(gè)頂點(diǎn)著相同的顏色，可以對其進(jìn)行檢測。由于刪除探針兩端所連接的單鏈DNA與頂點(diǎn)上的識別探針互補(bǔ)配對，通過雜交反應(yīng)可以形成新的結(jié)構(gòu)。如果數(shù)據(jù)池中的解滿足頂點(diǎn)著色的條件，那么，加入的刪除探針不會與納米顆粒串珠發(fā)生反應(yīng)，游離在溶液中。假設(shè)頂點(diǎn)2、4著相同的顏色，在遇到刪除探針D2-4時(shí)，兩者會進(jìn)行雜交反應(yīng)，形成新的結(jié)構(gòu)，形成過程如圖6所示。

圖6 刪除探針雜交過程

步驟4 在數(shù)據(jù)池中加入刪除探針后，含有非解的串珠鏈會同刪除探針進(jìn)行配對雜交，形成新的結(jié)構(gòu)，加入了刪除探針后的串珠鏈總的分子量變大，在凝膠電泳中的遷移速度會變慢。通過凝膠電泳技術(shù)，觀察串珠鏈的運(yùn)動速度，回收運(yùn)動速度較快的串珠鏈，此時(shí)所得到的串珠鏈都是滿足相鄰點(diǎn)為不同顏色的串珠鏈。最后采用非放射性標(biāo)記DNA測序的方法進(jìn)行測序，得到頂點(diǎn)著色問題對應(yīng)的解。

4 復(fù)雜度分析

時(shí)間復(fù)雜度：在本文中討論的是3-頂點(diǎn)著色，而每一個(gè)頂點(diǎn)的著色顆粒需要一個(gè)單位的操作時(shí)間，所以需要3n個(gè)操作時(shí)間；為了檢測著色方案，需要設(shè)計(jì)刪除探針，假設(shè)在圖中有m條邊不是通過鄰邊所連接的，因此共需要設(shè)計(jì)3m個(gè)刪除探針，消耗了3m個(gè)操作時(shí)間；在生成和刪除解時(shí)各占用一個(gè)時(shí)間單位。因此該模型的時(shí)間復(fù)雜度為ο(3n+3m+2)。

空間復(fù)雜度：每個(gè)頂點(diǎn)的需要3個(gè)不同的納米金顆粒來代表不同的顏色選擇，所以占據(jù)了3n個(gè)空間單位；同理于時(shí)間復(fù)雜度，刪除探針也占據(jù)3m個(gè)空間單位；在生成和刪除解也各需要占用一個(gè)空間，因此該模型的空間復(fù)雜度也是ο(3n+3m+2)。

5 結(jié)論

本文通過自組裝納米顆粒來求解圖的3-頂點(diǎn)著色問題。將圖的頂點(diǎn)和邊分別轉(zhuǎn)化為納米顆粒和DNA片段，利用生物分子的巨大并行性來生成數(shù)據(jù)池。在刪除非解時(shí)，直接使用凝膠電泳技術(shù)即可，避免了在加熱、解鏈、退火過程中產(chǎn)生偽解的可能，與以往借助限制性內(nèi)切酶刪除解的模型相比，自組裝模型更具有通用性，應(yīng)用范圍更廣。