基于DNA計(jì)算的最大權(quán)團(tuán)問題設(shè)計(jì)

張 喆，殷志祥

(安徽理工大學(xué)理學(xué)院，安徽 淮南 232000)

對于給定的無向圖G=(V，E)。如果U?V，且對任意u，v∈U有(u，v)∈E，則稱U是G的完全子圖。G的完全子圖U是G的團(tuán)當(dāng)且僅當(dāng)U不包含在G的更大的完全子圖中。G的最大團(tuán)是指G中所含頂點(diǎn)數(shù)最多的團(tuán)。而最大權(quán)團(tuán)，就是指權(quán)值最大的最大團(tuán)。

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

其中V1 對應(yīng)權(quán)重為ω1，V2 對應(yīng)權(quán)重為ω2，……，V5 對應(yīng)權(quán)重為ω5。

1 DNA 計(jì)算的原理

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

比較經(jīng)典的實(shí)驗(yàn)方式是在試管中進(jìn)行DNA 計(jì)算操作。計(jì)算過程中可能要用到一個(gè)或者多個(gè)試管，可根據(jù)需要在試管中加入引物、緩沖液、酶等反應(yīng)物。本實(shí)驗(yàn)過程即是在試管中進(jìn)行的。

2 質(zhì)粒及粘貼模模型

質(zhì)粒是游離于染色體之外的具有自行復(fù)制子的DNA 雙鏈分子，實(shí)驗(yàn)中運(yùn)用的質(zhì)粒通常具有復(fù)制子、選擇標(biāo)志、克隆位點(diǎn)等特征。質(zhì)粒最大的特點(diǎn)是質(zhì)粒上任一子段不會(huì)重復(fù)出現(xiàn)在質(zhì)粒的另一位置。這樣，對于質(zhì)粒的修改就只會(huì)在特定的位置進(jìn)行，而不會(huì)在其他位置進(jìn)行。

粘貼模型擁有一個(gè)由存儲(chǔ)合成物構(gòu)成的可以隨機(jī)訪問的存儲(chǔ)區(qū)。每個(gè)存儲(chǔ)合成物由存儲(chǔ)鏈和粘貼鏈的DNA 單鏈分子組成，存儲(chǔ)鏈和粘貼鏈都是由不同的堿基構(gòu)成，存儲(chǔ)鏈含有K個(gè)不重疊的子鏈，而任一粘貼鏈按堿基互補(bǔ)配對原則恰于存儲(chǔ)鏈中的任一子鏈配對。當(dāng)粘貼鏈可以與存儲(chǔ)鏈結(jié)合時(shí)，此位置視為“開”，在二進(jìn)制中可以用1 表示;反之，視為“關(guān)”，在二進(jìn)制中用0 表示。

利用質(zhì)粒以及粘貼模型各自的優(yōu)勢，將二者結(jié)合起來用于解決最大權(quán)團(tuán)問題。

3 DNA 算法步驟

以圖1 為例來說明算法的實(shí)現(xiàn)過程，設(shè)計(jì)的模型如圖2所示。

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

將圖2所示的DNA 鏈進(jìn)行擴(kuò)增，并將其產(chǎn)生的質(zhì)粒試管稱為T0。對于一個(gè)圖的頂點(diǎn)集V={V1，V2，…，Vn}，從中任取i≥2 的頂點(diǎn)，如Vk1，Vk2，…Vki，對于輔鏈1，保留位段(Vr，Vt)，其中r、t任取k1，…，ki中的任意兩個(gè)，且取遍所有可能。對于輔鏈2，只保留Vk1，Vk2，…Vki所對應(yīng)的權(quán)值子段。

在圖1 中任取3 點(diǎn){V1，V2，V3}，經(jīng)過上述操作，可以得到存儲(chǔ)合成物(見圖3a)。

在圖2 中任取3 點(diǎn){V1，V2，V5}，經(jīng)過上述操作，可以得到存儲(chǔ)合成物(見圖3b)。

由圖3 可以看出，圖3a 中的輔鏈1 并不完全是雙鏈，而圖3b 中的輔鏈1 完全是雙鏈，{V1，V2，V5}對應(yīng)的完全子圖就是圖1 的一個(gè)最大團(tuán)。

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

4 小結(jié)

最大團(tuán)以及最大權(quán)團(tuán)問題是著名的組合優(yōu)化問題，它在市場分析、方案選擇、信號傳輸、計(jì)算機(jī)視覺、信息恢復(fù)、容錯(cuò)能領(lǐng)域都有著廣泛的應(yīng)用。另外，許多NP—完全問題都可以轉(zhuǎn)化成為MCP，如可滿足性問題、獨(dú)立集問題、頂點(diǎn)覆蓋問題等。而DNA 計(jì)算具有納米級、超強(qiáng)并行操作能力以及特異性雜交識(shí)別等天然優(yōu)勢，使其非常適合用來解決最大團(tuán)問題。

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

［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，F(xiàn)RUTOS A G，et al.DNA computing on surface［J］.Nature，2000，403(13):175－179.

［5］許進(jìn)，譚鋼軍，范月科，等.論DNA 計(jì)算機(jī)模型［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30(6):881－893.

［6］周康，劉朔.基于粘貼模型的最大團(tuán)問題算法［J］.華中科技大學(xué)學(xué)報(bào):自然科學(xué)版，2010，38(9):89－92.

［7］張成，楊靜，許進(jìn)，等.縮短法計(jì)算模型求解最大獨(dú)立集問題［J］.科學(xué)通報(bào)，2011，54(24):3 913.

［8］周炎濤，李肯力，羅興，等.一種基于DNA 自組裝模型求解最大團(tuán)問題的算法［J］.湖南大學(xué)學(xué)報(bào)，2012，39(9):39－44.

［9］CHEN J，WOOD D H.Computation with biomolecules［J］.Commentary，2000，97(4):1 328－1 330.

［10］許進(jìn)，李三平，董亞非，等.粘貼DNA 計(jì)算機(jī)模型(II)應(yīng)用［J］.科學(xué)通報(bào)，2004，49(4):299－307.

［11］殷志祥，張鳳月，許進(jìn).基于分子信標(biāo)的DNA 計(jì)算［J］.生物數(shù)學(xué)學(xué)報(bào)，2003，18(4):497－501.