一種基于DNA自組裝模型求解最大團問題的算法＊

周炎濤，李肯立，羅 興，黎福海，朱 青

（1.湖南大學 電氣與信息工程學院，湖南 長沙 410082； 2.湖南大學 信息科學與工程學院，湖南 長沙 410082）

最大團問題（Maximum clique problem，MCP）又稱為最大獨立集問題，是圖論中的一個經典組合優化問題，也是一類NP完全問題[1].求解MCP算法主要有二類：確定性算法和啟發式算法，前者有回溯法、分支限界法等 .隨著問題規模的增大（頂點增多和邊密度變大），求解問題的時間復雜度越來越高，確定性算法顯得無能為力，不能有效地解決這些NP完全問題 .后者有蟻群算法、順序貪婪算法、DLS－MC算法和智能搜索算法等，大部分確定性算法所不能解決的圖，用啟發式算法都能得到有效解決，但啟發式算法不一定能找到最優解，有時只能找到近似值[2].近年來，常借鑒算法之間優勢互補策略，形成新的混合啟發式算法來求解最大團問題[3].

DNA計算是應用分子生物技術進行計算的新方法，具有高度并行性、大容量、低能耗等特點，為解決NP完全問題開辟了一條新途徑[4].自Adleman首次運用DNA計算來解決NP問題以來[5]，研究者對最大團問題的分子求解方法進行了很多有益的嘗試，如基于粘貼模型的最大團問題算法[6]、質粒DNA算法[7]、閉環求解最大團問題算法[8]等，但這些方法均存在實驗操作步驟過多、活體內不易操作以及環化效率不高等弊端.此外，Brun采用自組裝DNA計算給出了路徑尋找問題[9]，以及可滿足性問題的自組裝計算模型的解決方案[10].文獻[11]在分布式系統中建立自組裝模型解決自由等待一致性問題 .文獻[12]將AuNP自組裝聚合色變與DNA計算相結合，構建了系列基本邏輯計算模型，等等.

在DNA計算機研究中，所建模型的好壞直接影響著DNA計算中諸多問題，如編碼的難易程度、整個生物操作或生化反應的設計、解空間的大小、計算時間多少、應用范圍以及通用性的程度等.目前DNA計算模型有很多[13]，其中自組裝DNA計算模型是通過DNA分子間的相互作用形成特定的構型來完成計算過程 .它組合了DNA計算、Ting理論和DNA納米技術，成為目前備受關注的模型之一[14－15].在計算過程中，它避免了其他DNA計算模型所需要的眾多實驗操作次數，減少了操作帶來的時間消耗和誤差傾向.分子自組裝體系是一個高度組織、高度有序、結構化、功能化和信息化的復雜系統，對研究分子自組裝特性并求解最大團問題極有價值.本文采用DNA自組裝模型，設計出相應的DNA tiles分子，利用基因工程的生物操作，提出一種基于DNA自組裝模型求解最大團問題的算法.該算法實驗操作復雜度為常數級，既大大減少了因為人為實驗操作所帶來的誤差，又保證了實驗結果的準確性.

1 DNA自組裝模型

DNA的自組裝可形成一維、二維、三維結構.本文主要利用其形成的二維平面結構來解決最大團問題.1998年，根據 Wang的tiles理論，Winfree設計了雙交叉分子DX[16]，這個DX就充當了tiles的作用，通過自組裝就能實現所需的計算.理論上有5種可能的DX結構，但通過大量實驗證明，只有DAO和DAE這2種結構是穩定的[16].抽象的DAO和DAE結構如圖1所示.

圖1 DAO，DAE抽象結構Fig.1 Abstractive structures of DAO and DAE

觀察圖1可知，DAO結構包含4條DNA鏈，其中有2條鏈分布在2條雙螺旋上，另外2條分布在一條雙螺旋上 .相比之下，DAE結構包含5條DNA鏈，其中有3條鏈分布在2條雙螺旋上，另外2條鏈分布在一條雙螺旋上.由于DX可有4個粘性末端，故可利用這些粘性末端來實現所需要的計算.Winfree使用了帶顏色的tiles來模擬雙交叉分子的計算過程，規定只有具有相同顏色的邊才能夠結合形成較大的格局，其反應過程如圖2所示.

圖2 DX計算過程模擬Fig.2 Process simulation of DX computing

根據Wang的tiles理論模型的形式化描述以及Yuriy Brun引入DNA 的tiles自組裝模型[17]，結合最大團問題的特點可將基于DAE結構的自組裝模型表示為S＝〈T，g，τ〉，其中T為DAE塊的集合，g為能量函數，τ為常數.相應的符號描述如下：

1）Σ：DAE塊中所有粘性末端所表示符號的集合（即所要參與計算的符號的集合）；

2）D′＝ ｛UL，DL，UR，DR｝：分別表示DAE塊的左上角、左下角、右上角和右下角4個位置；

3）｛σUL，σDL，σUR，σDR｝∈Σ4：DAE塊的形式化描述，代表DAE塊4個位置分別所表示的符號；

4）（x，y）∈Z2：表示位置；

5）D＝｛N，E，S，W｝：表示4個方向函數，且滿足：

●?（x，y）∈Z2，N（x，y）＝（x，y＋1），E（x，y）＝（x＋1，y），S（x，y）＝（x，y－1），W （x，y）＝（x－1，y）；

●若位置（x，y）與（x’，y’）相鄰，則?d∈D，使得d（x，y）＝ （x’，y’）.

6）bdd（t）∈Σ，其中t∈T，d∈D’：表示t的位置d所表示的符號；

7）函數g：Σ×Σ→R，此函數定義如下：

●?σ∈Σ，則g（null，σ）＝0；

●若g（σ，σ’）＝0（其中σ，σ’∈Σ），則σ≠σ’；

●?σ≠null，有g（σ，σ）＝1；

●?σ≠σ’，有g（σ，σ’）＝0.

8）函數A：Z×Z→T，此函數有如下特點：

●若A（x，y）≠empty，則（x，y）∈A；

●若只有有限個不同的（x，y）∈A，則A為一個有限集.

9）A是一個格局，若一個DAE塊t能在位置（x，y）產生一個新的格局A’，需要滿足以下條件：

●（x，y）?A；

●Σd∈D’，d’∈Dg（bdd（t），bdd－1（A（d’（x，y））））≥τ，其中d與d－1為相對的方向，如：UR與DL相對.

●?（u，v）∈Z2，（u，v）≠ （x，y），則A’（u，v）＝A（u，v）；

●A（x，y）＝t.

2 算法設計步驟

2.1 算法設計思路

基于DNA自組裝模型的算法設計利用的是“堆積木”的思想，其具體算法設計思路如下：

1）設計初始分子，使之組裝成所有可能結果；

2）分析問題，找出問題正確結果所需滿足的條件；

3）根據2）條件限制，設計規則分子，判定1）中結果正確性；

4）搜索正確結果，得到所需答案.

本文按照上述步驟設計相應的DAE塊，然后通過基因工程的相應生物操作，利用凝膠電泳和熒光標記技術提取得到最終結果.相應生物操作描述[18]如下：

1）合并（merge）：給定試管P1和P2，操作∪（P1，P2）＝P1∪P2表示將試管P1和P2合并到一個試管中而不改變P1和P2中的任何鏈.

2）提取（extract）：給定試管P1和P2，操作P2＝extract（P1）表示提取試管P1中具有某種特征的DNA分子到試管P2.

3）退火（anneal）：給定試管P，操作Anneal（P）將試管P中的所有DNA單鏈變成雙鏈.

4）熒光標記（fluorescence labeling）：給定試管P，該操作將具有某種特征的DNA分子作標記.

5）凝膠電泳（gel electrophoresis）：給定試管P，該操作將試管中DNA分子按照分子大小進行分離.

2.2 設計初始分子

設G＝｛V，E｝，其中V＝｛v1，v2，… ，vn｝，則任何頂點子集都可能是圖G的團，則初始分子設計如圖3所示.其中，s和e是控制自組裝反應的始端和終端，與圖G無關；i，j∈｛1，2，…，n｝，且i＜j.分析可知：所有初始分子的種類為2n2－7n＋8.

若頂點子集為｛1，2｝，則退火反應之后則形成如圖4所示結構.若頂點子集為｛1，2，3｝，則退火后反應之后形成如圖5所示結構.

圖3 初始分子Fig.3 Initial moleculars

圖4 頂點子集｛1，2｝形成的結構Fig.4 Forming structure of vertex subset｛1，2｝

圖5 頂點子集｛1，2，3｝形成的結構Fig.5 Forming structure of vertex subset｛1，2，3｝

引理1 若Σ1＝｛s，e，v1，v2，…，vn｝，T1為按上述方式設計的初始分子DAE塊的集合，τ＝1，則形成的自組裝系統S1＝〈T1，g，τ〉.不失一般性，比如頂點子集為｛v1，v2，… ，vk｝，經過退火反應后則會形成如下格局A1：

證 根據T1中的DAE塊的特點可知，起始端為｛null，null，s，s｝，所以bdUR（A1（x0，y0））＝s.已知τ＝1，所以只需要一邊能夠結合就能夠產生新的格局.又已知頂點子集為｛v1，v2，… ，vk｝，所以?DAE塊｛∞，s，v1，v1｝，所以｛null，null，s，s｝與｛∞，s，v1，v1｝能夠結合產生新的格局.則此時bdUL（A1（x2，y0））＝∞，bdUR（A1（x2，y0））＝v1.

同理可知：當k為偶數時，bdUL（A1（x4，y0））＝v2，bdUR（A1（x4，y0））＝v3，…，bdUL（A1（xk＋2，y0））＝vk，bdUR（A1（xk＋2，y0））＝e，bdUL（A1（xk＋4，y0））＝e.

當k為奇數時，bdUL（A1（x4，y0））＝v2，bdUR（A1（x4，y0））＝v3，…，bdUL（A1（xk＋1，y0））＝vk－1，bdUR（A1（xk＋1，y0））＝vk，bdUL（A1（xk＋3，y0））＝e.

（2）要根據運行方式來調整好繼電保護裝置的保護功能、保護范圍以及相關的定制等等，對電網中所有有關的信息進行綜合，再實時修正好保護定值。

證畢.

2.3 設計規則分子

我們把規則分子的DAE塊設計成如圖6所示.

圖6 兩頂點鄰接時DAE塊Fig.6 DAE block with adjoining vertexes

若輸入頂點a，b在圖中是鄰接的，則存在上述DAE塊，使其輸出時交換頂點變成b，a.考慮到邊界條件，則可以把規則分子設計成如圖7.

圖7 規則分子Fig.7 Regular moleculars

其中s為始端，e為終端，與圖G無關.節點a，b鄰接，且a，b，c，d∈｛v1，v2，…，vn－1，vn，∞｝，所需DAE塊種類為｜E｜＋2n＋1.

引理2 在格局A1的基礎上，若T2為按上述方式設計的規則分子的集合，并且τ＝2，則形成的自組裝系統S2＝〈T2，g，τ〉.若G對于生成的格局A1中的所有頂點都相鄰，則系統S2會生成格局A2，其中bdUR（A2（xk＋1，yk＋1））＝∞，bdUL（A2（xk＋3，yk＋1））＝e.若G對于生成的格局A1中存在兩個頂點不相鄰，則系統S2不會生成上述格局A2.

證k為偶數且圖G對于生成的格局A1中的所有的頂點都相鄰，則形成的A1如引理1中所述.由于τ＝2，所以需要兩邊能夠結合才能產生新的格局.又因為所有的頂點都相鄰，所以對于任意兩個頂點vi，vj都存在 DAE 塊｛vj，vi，vi，vj｝，即每經過一輪比較∞都會向后移動，所以∞終會移動到末尾，即bdUR（A2（xk＋1，yk＋1））＝ ∞，且bdUL（A2（xk＋3，yk＋1））＝e.同理可知：若k為奇數時，bdUR（A2（xk＋1，yk＋1））＝∞，bdUL（A2（xk＋2，yk＋1））＝e.故系統S2會生成格局A2.

反之，若A1中存在兩個頂點不相鄰.不失一般性，假設存在兩個頂點vi，vj不相鄰，則不會存在DAE塊｛vj，vi，vi，vj｝.由于τ＝2，當反應進行到此后，格局就不會再增高，∞也就不會移動到末尾.故不能形成格局A2.

證畢.

2.4 設計檢測分子

圖8 檢測分子Fig.8 Detected moleculars

i，j∈｛1，2，…，n－1，n｝，并且利用熒光標記技術在上圖中最左邊的DNA分子加上與其他DAE塊不同顏色的熒光.則這些DAE塊種類共計n2＋1種.

若加入規則分子后能夠形成格局A2，則加入檢測分子后就能夠形成一個完整的格局，否則就不能形成一個完整穩定的格局（即該格局沒有粘性末端可提供給其他DAE塊結合，并且該格局中擁有帶有熒光標記的檢測分子）.

綜上所述，設計初始分子所需的DAE塊種類為2n2－7n＋8；設計規則分子所需的DAE塊種類為｜E｜＋2n＋1；設計檢測分子所需的DAE塊的種類為n2＋1.總共需要的DAE塊種類為3n2－5n＋｜E｜＋10.所以需要的DAE塊的種類為Θ（n2＋｜E｜），說明設計這些DAE塊是可行的.

3 基于DNA自組裝模型求解最大團問題

3.1 算法步驟

算法基于自組裝模型的最大團問題DNA算法.

輸入：圖G＝｛V，E｝，以及根據圖G并按上述方式設計的tiles集T1，T2，T3.

輸出：圖G的最大團.

7）T’end＝ Extract（T），提取在6）中所觀測到的分子塊，將其放入試管T′end；

8）使用凝膠電泳技術將T中的分子塊按照大小進行分離，通過激光共焦距顯微鏡觀察分子塊最大的DNA塊；

9）Tend＝Extract（T′end），提取8）中所觀察的最大的DNA塊，將其放入試管Tend.

引理3 有a1，a2，a3，…，an個頂點，按照以下方式進行n輪比較，則這n個頂點每兩個頂點都會比較一次，即總共比較Cn2＝n（n－1）／2次.

證 當n為偶數時，奇數輪比較（n／2）－1次，偶數輪比較n／2次，則總共比較的次數為（n／2）（n／2－1）＋ （n／2）（n／2）＝n（n－1）／2＝Cn2.

同理可知：當n為奇數時，總共比較次數為n（n－1）／2＝Cn2.

證畢.

定理1 若算法中Tend不為空，則Tend中所代表的團即為所求圖的最大團；否則該圖的任意兩個頂點都不鄰接.

證 若Tend不為空，則Tend中的頂點集是按照引理1中的方式進行比較.由引理1可知：Tend中的頂點集共進行了Cn2次比較.又由于兩個頂點比較之后一個頂點向左移動，另外一個頂點向右移動，則這兩個頂點不會重復比較，所以每兩個頂點都比較過一次.說明這n個頂點兩兩鄰接，即此頂點子集的導出子圖就為此圖的一個團.又由算法1的8）可知Tend中所表示頂點集都規模最大，所以Tend中所代表的團即為所求圖的最大團.反之，若Tend為空，則說明圖G的任意頂點子集的導出子圖都不是團，即該圖的任意兩個頂點都不鄰接.

證畢.

3.2 算法復雜性

文中2.2設計初始分子所需的DAE塊種類為2n2－7n＋8；2.3設計規則分子所需的DAE塊種類為｜E｜＋2n＋1；2.4設計檢測分子所需的DAE塊的種類為n2＋1.則總共需要的DAE塊種類為3n2－5n＋｜E｜＋10.所以需要的DAE塊的種類為Θ（n2＋｜E｜），即算法設計tiles的種類為Θ（n2＋｜E｜）.算法1（基于自組裝模型的最大團問題DNA算法）生物操作為9步，即其生物操作復雜性為Θ（1）.

3.3 示 例

給定圖G＝｛V，E｝，其中V＝｛1，2，3，4，5｝，E＝｛（1，2），（2，3），（3，4），（4，5），（2，5），（2，4），（3，5）｝，如圖9所示.

圖9 5個頂點無向圖Fig.9 Graph of 5vertexes

結合3.1的算法步驟，則求得最大團的步驟為如圖10所示 .在試管T1中加入連接酶，并使用退火操作，使其初始分子充分反應，則會形成不同的頂點子集，如圖10（a）形成的頂點子集為｛2，3，4，5｝.

將試管T1，T2中的DAE塊合并到試管T，之后在試管T中加入連接酶，并使用退火操作.此步驟實際上是加入規則分子，用以判斷前面的頂點子集是否為團.如圖10（b）即為加入規則分子去判斷頂點子集｛2，3，4，5｝是否為團.

最后加入檢測分子，便于檢測頂點子集的導出子圖是否為團.經過上述步驟后，凡是能夠形成如圖10（c）所示的結構，則說明該導出子圖即為團，即該圖中存在有熒光標記的DNA分子.

圖10 圖G最大團計算Fig.10 Computing maximum clique of G

4 結 論

自組裝技術能最底層揭示DNA計算的本質，它是一種由簡單到復雜、從無序到有序、由多組分收斂到單一組分不斷自我修正、自我完善的過程.本文采用DNA自組裝模型，設計出相應的DNA tiles分子，利用基因工程的生物操作，提出一種基于DNA自組裝模型求解最大團問題的算法 .該算法實驗操作復雜度為常數級，既大大減少了因為人為實驗操作所帶來的誤差，又保證了實驗結果的準確性，對DNA計算和DNA計算機的研究來說，是一次有意義的實踐.目前DNA計算模型的DNA編碼已經從一維結構發展到了三維結構 .相對于其他的計算模型，從理論上已表明，使用三維DNA圖結構可以明顯減少解決最大團問題所需的時間和步驟，而且由于它能直觀地反映圖結構，用它建立計算模型可能會使一些傳統的難解問題得以解決.

本文主要利用其形成的二維平面結構來解決最大團問題 .在技術層面上，將這種二維DNA分子組裝成三維DNA圖結構模型還存在很多需要解決的問題.目前對復雜三維DNA結構進行普通的實驗操作還少有研究，且與它相關聯的酶處理操作也容易發生錯誤.隨著DNA計算研究的深入，三維DNA計算也將會有更好的發展 .此外，將分子計算與量子計算緊密地結合在一起，為未來的新型計算技術提供了發展的可能.伴隨分子操控技術的發展，相信DNA計算在信息處理、密碼技術、納米智能機器和納電子學等多個領域將會有更多的潛在應用.

[1] OUYANG Q，KAPLAN P D ，LIU S，et al.DNA solution of the maximal clique problem[J].Science，1997，278：446－449.

[2] PULLAN W，HOOS H H.Dynamic local search for the maximum clique problem[J].Journa l of Artificial Intelligence Research，2006，25：159－185.

[3] KATAYAMA K，KOHMURA A，KOHMOTO K，et al.Memetic algorithm with strategic controller for the maximum clique problem[C]∥Taiwan：TaiChung：Proceedings of the 2011ACM Symposium on Applied Computing，2011：1062－1069.

[4] SHARRMA J，CHHABRA R，CHENG A，et al.Control of self－assembly of DNA tubules through integration of gold nanoparticles[J].Science，2009，323：112－116.

[5] ADLEMAN L M.Molecular computation of solutions to combinatorial problems[J].Science，1994，266（11）：1021－1024.

[6] 周康，劉朔，覃磊，等.基于粘貼模型的最大團問題算法[J].華中科技大學學報：自然科學版，2010，38（9）：89－92.ZHOU Kang，LIU Shuo，QIN Lei，et al.Sticker model－based DNA algorithm of maximum clique problem[J].Huazhong Univ of Sci ＆Tech：Natural Science Edition，2010，38（9）：89－92.（In Chinese）

[7] HEAD T，ROZENBERG G，BLADERGROEN R B，et al.Computing with DNA by operating on plasmids[J].Bio Systems，2000，57：87－93.

[8] 張成，楊靜，許進，等.DNA縮短法計算模型求解最大獨立集問題[J].科學通報，2009，54（24）：3913－3919.ZHANG Cheng，YANG Jing，XU Jin，et al.A DNA length reducing computing model for maximum independent set problem[J].Chinese Sci Bull，2009，54（24）：3913－3919.（In Chinese）

[9] BRUN Y，REISHUS D.Path finding in the tile assembly model[J].Theoretical Computer Science，2009，410（15）：1461－1472.

[10] BRUN Y.Solving satisfiability in the tile assembly model with a constant－size tileset[J].Journal of Algorithma，2008，63（4）：151－166.

[11] STERLING A.Distributed agreement in tile self－assembly[J].Natural Computing：an International Journal，2011，10（1）：337－355.

[12] 張成，楊靜，許進.自組裝DNA／納米顆粒分子邏輯計算模型[J].科學通報，2011，56（27）：2276－2282.ZHANG Cheng，YANG Jing，XU Jin.Molecular logic computing model based on self－assembly of DNA nanoparticles[J].Chinese Sci Bull，2011，56（27）：2276－2282.（In Chinese）

[13] XU Jin，TAN Gang－jun，FAN Yue－ke，et al.DNA computer principle，advances and difficulties（Ⅳ）：on the models of DNA computer[J].Chinese Journal of Computers，2007，30（6）：881－893.

[14] 張勛才.自組裝DNA計算模型的研究及應用[D].武漢：華中科技大學計算機工程與技術學院，2009.5.ZHANG Xun－cai.The reserch and applications of DNA computing by self－assembly[D].Wuhan：Huazhong Univ of Sci＆Tech，2009.5.（In Chinese）

[15] HE Yu，MAO Cheng－de，et al.Hierarchical self－assembly of DNA into symmetric supramolecular polyhedral[J].Nature，2008，452：198－202.

[16] WINFREE E.Design and self－assembly of two－dimensional DNA crystals[J].Nature，1998，394：1223－1226.

[17] YURIY B.Solving NP－complete problems in the tile assembly model[J].Theoretical Computer Science，2008，395（1）：31－46.

[18] 李肯立，姚鳳娟，許進，等.子集和問題的O（1.414n）鏈數DNA計算機算法[J].計算機學報，2007，30（11）：1948－1953.LI Ken－li，YAO Feng－juan，XU Jin，et al.An O（1.414n）volume molecular solutions for the subset－sum problem on DNA－based supercomputing [J].Chinese Journal of Computers，2007，30（11）：1948－1953.（In Chinese）