圖的最小頂點(diǎn)覆蓋問題的鏈置換模型①

，

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

0 引 言

計(jì)算機(jī)技術(shù)突飛猛進(jìn)，但由于計(jì)算機(jī)的一些限制，很多NP問題仍是解決不了的難題。1994年Aldeman[1]博士將DNA技術(shù)引入到NP問題的解決中，首次提出用DNA編碼解決7個(gè)頂點(diǎn)有向圖的Hamilton路徑問題，進(jìn)而有了DNA計(jì)算方法，將生物分子技術(shù)運(yùn)用到計(jì)算機(jī)NP問題中。后續(xù)大量學(xué)者采用DNA計(jì)算方法解決了可滿足性問題、最大匹配問題、最小頂點(diǎn)問題等。2004年，王淑棟[2]等提出運(yùn)用質(zhì)粒來解決圖的最小頂點(diǎn)覆蓋問題，不需要復(fù)雜的DNA鏈進(jìn)行退火反應(yīng)。2006年，周康[3]等采用閉環(huán)DNA計(jì)算模型，用刪除解的實(shí)驗(yàn)，構(gòu)建頂點(diǎn)覆蓋的補(bǔ)集來求解的空間，以解決圖的最小定點(diǎn)覆蓋問題。2009年，羊四清[4]等采用熒光標(biāo)記的方法，提出一種最小頂點(diǎn)覆蓋的DNA的表面計(jì)算模型。2013年，聶曉艷[5]等對(duì)經(jīng)典的粘貼模型和全信息化的粘貼模型進(jìn)行研究，提出一種用粘貼DNA計(jì)算方法，來解決圖的最小頂點(diǎn)覆蓋問題的DNA計(jì)算模型。

利用鏈置換技術(shù)具有自發(fā)性反應(yīng)，節(jié)省時(shí)間的優(yōu)點(diǎn)來優(yōu)化圖的最小頂點(diǎn)覆蓋問題的DNA計(jì)算過程，構(gòu)建圖的最小頂點(diǎn)覆蓋的鏈置換模型。

圖1為需要采用的基本鏈置換反應(yīng)過程。

1 最小頂點(diǎn)覆蓋

在簡(jiǎn)單無向圖G=(V,E)中，如圖2所示，其中具有頂點(diǎn)集V={ν1，ν2，ν3……νn}，邊集E={e1,e2,e3……em}，其中n為頂點(diǎn)數(shù),m為邊數(shù)。對(duì)于V′,滿足V′?V,且圖G的每條邊都至少有一個(gè)頂點(diǎn)在V′中，則稱V′為G的一個(gè)覆蓋。若圖G中不存在另一個(gè)覆蓋VP′,使得|VP′|≥|V′|，稱V′為圖G的最小頂點(diǎn)覆蓋。

圖1 鏈置換基本反應(yīng)過程

圖2

最小頂點(diǎn)覆蓋問題是計(jì)算復(fù)雜度大的NP問題之一，近幾年各個(gè)學(xué)者用改進(jìn)的DNA計(jì)算方法或其他方法去解決最小頂點(diǎn)覆蓋問題。然而關(guān)于DNA鏈置換解決最小頂點(diǎn)覆蓋問題的研究不算多，而DNA鏈置換反應(yīng)與其他分子生物技術(shù)操作相比，具有獨(dú)特的優(yōu)勢(shì)，鏈置換反應(yīng)有計(jì)算單元簡(jiǎn)單、容易實(shí)現(xiàn)、產(chǎn)率高、耗時(shí)短等特點(diǎn)，在解決最小頂點(diǎn)覆蓋中，有很重大的意義。而最小頂點(diǎn)覆蓋問題是找出包含所有邊的最小點(diǎn)集，是NP完全問題，算法的關(guān)鍵是把復(fù)雜的數(shù)學(xué)問題進(jìn)行轉(zhuǎn)化，轉(zhuǎn)換到DNA鏈上，對(duì)所求問題的每條邊進(jìn)行DNA編碼，利用DNA鏈置換反應(yīng)的高效性和高度并行性，及相應(yīng)的生物操作，產(chǎn)生最長(zhǎng)鏈，使最終鏈的分離，給出基于鏈置換的最小頂點(diǎn)覆蓋問題的優(yōu)化計(jì)算方法。所以在DNA鏈置換的基礎(chǔ)上，提出以DNA鏈置換技術(shù)解決最小頂點(diǎn)覆蓋問題的DNA計(jì)算模型。

2 DNA鏈置換算法

將圖2中各個(gè)頂點(diǎn)的編碼成DNA鏈,編碼好的DNA鏈形成一個(gè)初始的數(shù)據(jù)池，將這些數(shù)據(jù)池均分成兩個(gè)數(shù)據(jù)池，分別進(jìn)行數(shù)據(jù)刪除操作，然后將兩個(gè)數(shù)據(jù)池成一個(gè)新的數(shù)據(jù)池，將一個(gè)數(shù)據(jù)池重新分成兩個(gè)數(shù)據(jù)池，置換刪除并連接一個(gè)數(shù)據(jù)池中所有位中的第k位，每個(gè)數(shù)據(jù)池的操作都有一個(gè)對(duì)應(yīng)的DNA表示如下：

a. 將兩個(gè)數(shù)據(jù)池合成一個(gè)新的數(shù)據(jù)池是每個(gè)環(huán)節(jié)必備的操作，這個(gè)操作產(chǎn)生一個(gè)含有兩個(gè)輸入結(jié)果的數(shù)據(jù)池并。

b. 一個(gè)數(shù)據(jù)池分成兩個(gè)相同的數(shù)據(jù)數(shù)據(jù)。保證每個(gè)數(shù)據(jù)集包含輸入集中的所有原始數(shù)據(jù)，并且每個(gè)數(shù)據(jù)池都包含所有的元素。

c. 切割刪除并連接一個(gè)數(shù)據(jù)池中所有數(shù)據(jù)的第m位是先后兩個(gè)密不可分并且每個(gè)環(huán)節(jié)重復(fù)的的操作，數(shù)據(jù)池中的DNA在第m位處,被置換并重新連接成一個(gè)環(huán)形單鏈DNA,在原始DNA數(shù)據(jù)池中剔除第m位后得新的環(huán)形單鏈DNA。

DNA算法：

步驟一，對(duì)DNA編碼，自動(dòng)生成一個(gè)環(huán)狀單鏈DNA,即一個(gè)解為空集的初始數(shù)據(jù)池，試管T0;

步驟二，圖G中每條邊ei=vjvm,將T0兩個(gè)相等的，添加頂點(diǎn)集V的所有包含vj或vm的補(bǔ)鏈；

步驟三，重復(fù)步驟二，得到所求問題對(duì)應(yīng)所有解對(duì)應(yīng)的集合，若初始數(shù)據(jù)池T0對(duì)應(yīng)的解是空集，那么所求圖形的頂點(diǎn)集合便是此圖的最小頂點(diǎn)覆蓋集,否則進(jìn)行步驟四；

步驟四，比較最后產(chǎn)物中對(duì)應(yīng)每個(gè)補(bǔ)集中元素的個(gè)數(shù)，找到問題的最優(yōu)解。

先生成解的空集，通過分離刪除解的操作，找出所求問題最優(yōu)解的補(bǔ)集，來求解問題。特別指出，對(duì)于某頂點(diǎn)DNA存在為1，表示這個(gè)位的頂點(diǎn)不在所求的頂點(diǎn)覆蓋集中。例如DNA鏈111111表示解為空集。

3 DNA鏈置換算法分析

圖3

步驟一、將所有編碼好的DNA鏈，加入到緩沖液中，在一定的溫度下，使其生成一條長(zhǎng)鏈，對(duì)反應(yīng)得到的結(jié)果提取、純化、PCR擴(kuò)增得到初始數(shù)據(jù)池T0。即用鏈{a1,a2……am}將表示邊的線性DNA{e1,e2……en}首尾相連而成的閉環(huán)鏈DNA。

對(duì)T2試管同樣的操作，把邊a2的核苷酸補(bǔ)鏈加入到試管中，得到?jīng)]有邊a2DNA鏈，將試管T1和T2合為初始數(shù)據(jù)池T0試管,那么中不含有DNA鏈a1和a2，表示解{a1}和{a2}。

步驟三、檢測(cè)圖中是否還有頂點(diǎn)相互關(guān)聯(lián)，若有則重步驟二，最后的試管中得到含有所求的解的補(bǔ)集。

步驟四、利用凝膠電泳等相關(guān)技術(shù)檢測(cè)出最長(zhǎng)的DNA鏈，再進(jìn)行PCR擴(kuò)增純化后，提取這些鏈，采用非放射性標(biāo)記的方法檢測(cè)DNA鏈的堿基排序，對(duì)檢測(cè)結(jié)果分析，得到所求圖形的最小頂點(diǎn)覆蓋的補(bǔ)集的DNA鏈，便對(duì)應(yīng)圖的最小頂點(diǎn)覆蓋的最優(yōu)解，問題得以解決。

圖4

4 案例分析

以圖5為例

圖5

5 結(jié) 語

而在求解圖的問題過程中，各種算法的復(fù)雜程度都有圖形的點(diǎn)和邊有直接關(guān)系，給出一個(gè)有n個(gè)頂點(diǎn)和m條邊的無向圖形，利用DNA鏈置換反應(yīng)來優(yōu)化計(jì)算它的最小頂點(diǎn)覆蓋問題，相應(yīng)的會(huì)出現(xiàn)DNA編碼多而復(fù)雜問題，防止出現(xiàn)DNA雜交等問題，而生物操作的復(fù)雜度，也會(huì)隨著頂點(diǎn)和邊的增加而增加表現(xiàn)出線性關(guān)系。并在生物操作過程中，出現(xiàn)產(chǎn)生錯(cuò)解或偽解的可能，隨著生物技術(shù)不斷的發(fā)展，這些問題應(yīng)該會(huì)很快得到解決。并隨著分子生物學(xué)技術(shù)的發(fā)展，這種DNA計(jì)算模型的生物操作、此解法更具簡(jiǎn)單操作及通用性。

參考文獻(xiàn):

[1] Pawlak Z.Rough sets-theoretical Aspects of Reasoning About Data[M].Boston:Kluwer Academic Publishers,1991:9-70.

[2] 王淑棟, 劉文斌, 許進(jìn).圖的最小頂點(diǎn)覆蓋問題的質(zhì)粒DNA計(jì)算模型[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2004, 32(11):59-61.

[3] 周康, 許進(jìn).最小頂點(diǎn)覆蓋問題的閉環(huán)DNA算法[J].計(jì)算機(jī)工程與應(yīng)用, 2006, 42(20):7-9.

[4] 羊四清, 李小龍, 袁輝勇.圖的最小頂點(diǎn)覆蓋問題的DNA表面計(jì)算模型[J].計(jì)算機(jī)工程與應(yīng)用, 2009, 45(6):69-72.

[5] 聶曉艷, 耿俊, 湯建鋼.圖的最小頂點(diǎn)覆蓋的粘貼DNA計(jì)算模型[J].首都師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013, 34(1):7-12.

[6] 張惠玲, 謝邱敏, 李煒.最少頂點(diǎn)覆蓋問題的研究[J].中國(guó)新通信, 2014(13):51-52.

[7] 郭洪敏, 殷志祥.基于DNA自組裝模型解決圖的最小頂點(diǎn)覆蓋問題[J].安徽理工大學(xué)學(xué)報(bào)(自科版), 2015(3):17-20.

[8] 周康,同小軍,劉文斌.排課表問題的閉環(huán)DNA計(jì)算模型的算法[J].計(jì)算機(jī)應(yīng)用,2007.37(4):991-993.

[9] 郭洪敏.最小頂點(diǎn)覆蓋問題的幾種DNA算法研究[D].安徽理工大學(xué), 2016.

[10] 周金鳳.圖的最小頂點(diǎn)覆蓋問題的幾種DNA計(jì)算模型[D].安徽理工大學(xué), 2013.

[11] 高琳, 許進(jìn).最小頂點(diǎn)覆蓋問題的DNA分子算法[J].系統(tǒng)工程與電子技術(shù), 2004, 26(4):544-548.

[12] 董亞非, 張家秀, 殷志祥,等.最小頂點(diǎn)覆蓋問題的改進(jìn)粘貼模型[J].電子與信息學(xué)報(bào), 2005, 27(4):556-560.

[13] Zhang Z, Fan T W, Hsing I M.Integrating DNA Strand Displacement Circuitry to the Nonlinear Hybridization Chain Reaction.[J].Nanoscale, 2017, 9(8):2748.

[14] Chen L, Peng J, Zhang B, et al.Uncertain Programming Model for Uncertain Minimum Weight Vertex Covering Problem[J].Journal of Intelligent Manufacturing, 2017, 28(3):625-632.

[15] Rezvanian A, Meybodi M R.Finding Minimum Vertex Covering in Stochastic Graphs: A Learning Automata Approach[M].Taylor & Francis, Inc.2015..