基于DNA計算的最大權團問題設計

張喆++殷志祥

摘要：介紹了最大團和最大權團的概念和國內外學者運用DNA計算解決最大團的研究成果；結合前人運用質粒、二進制、粘貼模型等方式進行DNA計算操作的原理，設計了新的用于解決最大權團問題的算法步驟，大大提高了算法效率，實現了最大團和最大權團的同步求解，對市場分析、方案選擇等領域有一定的意義。

關鍵詞：DNA計算；質粒；粘貼模型；最大權團；凝膠電泳

中圖分類號：TP301.6文獻標志碼：A

文章編號：1672-1098（2015）01-0075-03

對于給定的無向圖G=（V，E）。如果UV，且對任意u，v∈U有（u，v）∈E，則稱U是G的完全子圖。G的完全子圖U是G的團當且僅當U不包含在G的更大的完全子圖中。G的最大團是指G中所含頂點數最多的團。而最大權團，就是指權值最大的最大團。

1994年，文獻[1]提出了用DNA分子解決7節點的Hamilton路徑問題，這是有關DNA計算的開山之作。之后文獻[2]在Adleman思想的啟發下，通過構造一個接觸網絡圖G，將可滿足性問題（SAT）的解空間，映射成通過接觸網絡G的始點到終點的所有Hamilton路徑，然后對有向圖中的頂點和邊進行編碼，用DNA計算解決了3—變量的可滿足性問題。1997年，文獻[3]提出了用DNA計算求解最大環問題的方法，為DNA計算解決NP問題提供了又一佐證。2000年，文獻[4]提出了在固體表面進行DNA計算的方法，改變了過去在試管溶液中進行DNA計算的生物操作的方法，進一步提高了DNA計算的可靠性和效率，近些年，文獻[5]2009年解決了閉環求解最大團問題的算法；文獻[6]于2010年解決了基于粘貼模型的最大團問題算法；文獻[7]于2011年結合Aunp自組裝聚合色變與DNA計算相結合，構建了系列基本邏輯計算模型；文獻[8]于2012年設計出了結合DAE塊的DNA自組裝模型求解最大團問題的算法，并在2013年進一步改進，等等。本文將用圖1所示的頂點圖來進行實驗，利用DNA計算的算法求出其最大權團。

圖1頂點圖

其中V1對應權重為ω1，V2對應權重為ω2，……，V5對應權重為ω5。

1DNA計算的原理

DNA計算的基本思想是以DNA鏈作為信息載體，將原始問題映射為DNA分子鏈（包括單鏈、雙鏈、帶有粘性末端的單雙混合鏈），對設計出的DNA分子進行擴增，在實驗室中對這些DNA分子進行諸如退火、雜交、連接[9] 等生化操作，最后采用電泳技術[10] 、層析分析技術、分子純化技術[11] 、激光技術等方式檢測DNA計算的最后結果。

比較經典的實驗方式是在試管中進行DNA計算操作。計算過程中可能要用到一個或者多個試管，可根據需要在試管中加入引物、緩沖液、酶等反應物。本實驗過程即是在試管中進行的。

2質粒及粘貼模模型

質粒是游離于染色體之外的具有自行復制子的DNA雙鏈分子，實驗中運用的質粒通常具有復制子、選擇標志、克隆位點等特征。質粒最大的特點是質粒上任一子段不會重復出現在質粒的另一位置。這樣，對于質粒的修改就只會在特定的位置進行，而不會在其他位置進行。

粘貼模型擁有一個由存儲合成物構成的可以隨機訪問的存儲區。每個存儲合成物由存儲鏈和粘貼鏈的DNA單鏈分子組成，存儲鏈和粘貼鏈都是由不同的堿基構成，存儲鏈含有K個不重疊的子鏈，而任一粘貼鏈按堿基互補配對原則恰于存儲鏈中的任一子鏈配對。當粘貼鏈可以與存儲鏈結合時，此位置視為“開”，在二進制中可以用1表示；反之，視為“關”，在二進制中用0表示。

利用質粒以及粘貼模型各自的優勢，將二者結合起來用于解決最大權團問題。

3DNA算法步驟

以圖1為例來說明算法的實現過程，設計的模型如圖2所示。

圖2新鏈

此模型結合粘貼模型以及質粒模型：由主鏈、輔鏈1、輔鏈2三個部分組成，其中輔鏈2與輔鏈1相連，輔鏈1與主鏈相連；主鏈表示頂點對應的DNA鏈，輔鏈1表示頂點間邊的關系，頂點間有邊相連設置為雙鏈DNA分子，無邊設為單鏈，輔鏈2代表權值，不同頂點對應的每個子鏈中都含有可以被限制性內切酶特異識別的DNA序列（這樣可以被限制性內切酶所識別，進而進行剪切），同時根據權值的大小將各個子鏈設置成不同的長度。m1 是權值除以各個權值的最大公約數n得到的結果，即有ω1=nm1；對于整條鏈，將其插入質粒1中（質?？蛇x取pOK12質粒）。

將圖2所示的DNA鏈進行擴增，并將其產生的質粒試管稱為T0。對于一個圖的頂點集V={V1，V2，…，Vn}，從中任取i≥2的頂點，如Vk1 ，Vk2 ，…Vki ，對于輔鏈1，保留位段（ Vr，Vt），其中r、t任取k1，…，ki中的任意兩個，且取遍所有可能。對于輔鏈2，只保留Vk1，Vk2 ，…Vki 所對應的權值子段。

在圖1中任取3點{V1，V2，V3}，經過上述操作，可以得到存儲合成物（見圖3a）。

在圖2中任取3點{V1，V2，V5}，經過上述操作，可以得到存儲合成物（見圖3b）。

（b）圖3存儲合成物

由圖3可以看出，圖3a中的輔鏈1并不完全是雙鏈，而圖3b中的輔鏈1完全是雙鏈，{V1，V2，V5}對應的完全子圖就是圖1的一個最大團。

i的取值不斷增加（2≤i≤n），不斷的復制T0 來進行上述操作，然后篩選出輔鏈1全為雙鏈的合成物，其對應的頂點集即為圖的最大團。對于圖1來說，可以篩選出最大團為{V1，V2，V5}，{V3，V4，V5}。利用限制性內切酶切下篩選出的合成物各自的輔鏈2，由于各自的權值不同，所以各自的輔鏈2長度也不同，此時可以利用凝膠電泳篩選出長度最長的合成物，在利用探針照明技術確定頂點組成，此時即可求出最大權團。endprint

4小結

最大團以及最大權團問題是著名的組合優化問題，它在市場分析、方案選擇、信號傳輸、計算機視覺、信息恢復、容錯能領域都有著廣泛的應用。另外，許多NP—完全問題都可以轉化成為MCP，如可滿足性問題、獨立集問題、頂點覆蓋問題等。而DNA計算具有納米級、超強并行操作能力以及特異性雜交識別等天然優勢，使其非常適合用來解決最大團問題。

本文運用DNA計算可以有效的解決最大權團問題，使得最大權團問題更好的運用于生產實踐中，具有一定的實踐意義。在解決最大權團問題中，還有一些待解決的問題，比如DNA的合成與編碼、如何運用盡量簡單的方式形成解空間等，同時如何剔除“偽解”和“錯解”，篩選出最優解也是非常重要的。今后的研究將著重于以上幾個方面。

參考文獻：

[1]ADLEMAN L M. Molecular computation of solutions to combination problems[J]. Science，1994，266（5 187）：1 021-1 024.

[2]LIPTON R J.DNA solutions of hard computational problems[J].Science，1995，268（5 210）：542-545.

[3]OUYANG Q，KAPLAN P D，LIU S，et al.Solution of the maximal clique problem [J].Science，1997，278（17）：446-449.

[4]LIU Q， WANG L， FRUTOS A G，et al.DNA computing on surface[J]. Nature，2000， 403（13）：175-179.

[5]許進，譚鋼軍，范月科，等.論DNA 計算機模型[J].計算機學報，2007，30（6）：881-893.

[6]周康，劉朔.基于粘貼模型的最大團問題算法[J].華中科技大學學報：自然科學版，2010，38（9）：89-92.

[7]張成，楊靜，許進，等.縮短法計算模型求解最大獨立集問題[J].科學通報，2011，54（24）：3 913.

[8]周炎濤，李肯力，羅興，等.一種基于DNA自組裝模型求解最大團問題的算法[J].湖南大學學報，2012，39（9）：39-44.

[9]CHEN J，WOOD D H.Computation with biomolecules[J].Commentary，2000，97（4）：1 328-1 330.

[10]許進，李三平，董亞非，等.粘貼DNA計算機模型（II）應用[J].科學通報，2004，49（4）：299-307.

[11]殷志祥， 張鳳月，許進.基于分子信標的DNA計算[J].生物數學學報，2003，18（4）： 497-501.

（責任編輯：何學華）endprint