基于自組裝納米顆粒的頂點著色問題的DNA計算模型

陳芳，殷志祥

（安徽理工大學 數學與大數據學院，淮南 232001）

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

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

1 頂點著色問題

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

圖1 6個頂點的簡單圖

2 計算模型

2.1 基本算法

步驟1 利用自組裝的金屬顆粒對應每個頂點；

步驟2 利用DNA堿基互補配對生成數據池；

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

步驟4 輸出著色方案。

2.2 生物算法

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

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

步驟2 將納米金屬顆粒同連接探針加入到溶液中進行生化反應，根據堿基互補配對會生成串珠狀結構，即初始數據池。

步驟3 在數據池中，含有非解，需要進行篩選。構造刪除探針，刪除探針結構與頂點的結構相同，主體部分為納米金屬顆粒，兩端連接有單鏈DNA，兩端的單鏈DNA分別是相鄰頂點的連接DNA的補鏈。這樣將刪除探針加入到數據池中后，如果相鄰兩個頂點著相同顏色，刪除探針會與代表該方案的串珠進行雜交反應，串珠的質量與結構會發生改變。

步驟4 借助凝膠電泳技術來對非解進行剔除，因為數據池中的非解在加入刪除探針過后，質量與體積都會增大，在進行電泳分離的過程中，非解的移動速度慢，因此可以通過分離來得到解。最后采用非放射性標記DNA測序的方法進行測序，可以具體得到每個頂點的著色方案。

3 算法實例

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

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

圖2 部分頂點的設計

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

圖3 連接探針的設計

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

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

圖4 數據池的生成

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

圖5 刪除探針的設計

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

圖6 刪除探針雜交過程

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

4 復雜度分析

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

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

5 結論

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