DNA自組裝計(jì)算模型求解二部圖完美匹配問題

藍(lán)雯飛 邢志寶 黃 俊 強(qiáng)小利

(中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 武漢 430074) (lanwenfei1@163.com)

?

DNA自組裝計(jì)算模型求解二部圖完美匹配問題

藍(lán)雯飛 邢志寶 黃 俊 強(qiáng)小利

(中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 武漢 430074) (lanwenfei1@163.com)

針對(duì)二部圖完美匹配問題，提出了一種基于DNA計(jì)算自組裝模型的算法.首先，通過該算法求解了一個(gè)具有10個(gè)頂點(diǎn)的二部圖完美匹配問題的實(shí)例,實(shí)例中給出DNA計(jì)算自組裝模型算法所涉及到的DNA Tile的編碼設(shè)計(jì)方案、自組裝計(jì)算步驟及結(jié)果分析;然后，給出了任意二部圖完美匹配問題的求解方案;最后，針對(duì)DNA計(jì)算自組裝模型算法解決任意二部圖完美匹配問題的時(shí)間和空間消耗進(jìn)行了討論.結(jié)果表明:對(duì)任意二部圖只需14種Tile類型就能夠得到完美匹配.

完美匹配；二部圖；DNA計(jì)算；自組裝；瓦片

在計(jì)算面臨的三大類問題(即容易、困難和不可計(jì)算)中，對(duì)于容易問題，傳統(tǒng)電子計(jì)算機(jī)可以輕松地處理，但是對(duì)于困難問題(一般指NP-完全問題)，計(jì)算時(shí)間將會(huì)隨著計(jì)算規(guī)模的增大而呈指數(shù)增長(zhǎng).針對(duì)這個(gè)問題，很多科學(xué)家將目光轉(zhuǎn)向?qū)ζ渌愋偷挠?jì)算機(jī)結(jié)構(gòu)研究上，從而類似于神經(jīng)網(wǎng)絡(luò)計(jì)算機(jī)[1-2]、量子計(jì)算機(jī)[3-4]以及DNA計(jì)算機(jī)模型[5-11]等應(yīng)運(yùn)而生.DNA計(jì)算機(jī)模型，憑借其高度的并行計(jì)算能力和海量的存儲(chǔ)能力在各種新型計(jì)算機(jī)中脫穎而出,在很多領(lǐng)域(比如生物、物理、數(shù)學(xué)及計(jì)算機(jī)科學(xué))中都得到了廣泛的應(yīng)用，并成為解決NP難問題的一種潛在的方案.

早在20世紀(jì)60年代，F(xiàn)eynman[12]就已經(jīng)提出了在分子水平上進(jìn)行計(jì)算的概念，但是這種觀念真正引起各個(gè)領(lǐng)域科學(xué)家的興趣是在Adleman[13]提出利用DNA計(jì)算解決有向Hamilton路徑問題之后.Aldeman不但解決了Hamilton路徑問題，還成功地利用現(xiàn)代生物技術(shù)進(jìn)行了實(shí)驗(yàn).自此，DNA計(jì)算引起各領(lǐng)域科學(xué)家的極大興趣以及社會(huì)各界的廣泛的關(guān)注和支持.1998年，Winfree[14]提出了一種既具有Seeman的分支DNA結(jié)構(gòu)又具有Wang Tiling理論的可以自組裝的DNA結(jié)構(gòu).2009年張勛才[15]通過編碼Tile粘性末端，將待運(yùn)算的信息與Tile的結(jié)合域相結(jié)合，建立了基于DNA計(jì)算的減法和除法運(yùn)算模型,其中除法模型中包含了比較、復(fù)制和減法3個(gè)子系統(tǒng).作者利用DAN計(jì)算模型實(shí)現(xiàn)了這3個(gè)子系統(tǒng)并將其合并最終成為了一個(gè)完整的除法模型.此外，還利用自組裝DNA計(jì)算模型解決了0-1規(guī)劃問題和圖著色問題.在解決0-1規(guī)劃問題時(shí)，作者將0-1規(guī)劃問題中的約束機(jī)制分成了“與”操作和“比較”操作2個(gè)基本操作，并利用DNA自組裝模型實(shí)現(xiàn)了這2種操作.通過這2種操作的組合，可以自動(dòng)判斷任意可行解是否滿足給定的約束條件.在圖著色上，作者引入了非確定性算法，利用DNA自組裝的高度并行的特性，驗(yàn)證所有可能的著色方案，在多項(xiàng)式時(shí)間內(nèi)就可以解決圖著色問題.2009年，陳智華[16]利用DNA自組裝模型提出了一次一密密碼系統(tǒng).該系統(tǒng)由4個(gè)子系統(tǒng)組成：加密子系統(tǒng)、密碼提取子系統(tǒng)、秘鑰計(jì)算子系統(tǒng)和解密子系統(tǒng)，同時(shí)利用生物技術(shù)實(shí)現(xiàn)了秘鑰的安全傳輸.另外，通過對(duì)DNA Tile的編碼實(shí)現(xiàn)了破譯Diffie-Hellman算法的DNA自組裝模型.通過生物技術(shù)(PCR和凝膠電泳)讀出素?cái)?shù)原根的離散對(duì)數(shù)值，從而威脅Diffie-Hellman密鑰交換安全.但是由于Tile的種類與輸入位數(shù)呈線性關(guān)系，限制了該方案對(duì)大規(guī)模輸入的應(yīng)用.2008年，Brun[17]基于DNA自組裝計(jì)算模型提出了2個(gè)系統(tǒng)，解決了NP-完全問題——k-SAT，并以3-SAT為例進(jìn)行了說明.作者提出的第1個(gè)Tile系統(tǒng)用了Θ(n2)種不同的Tile表示布爾方程式中n個(gè)不同的變量;第2個(gè)Tile系統(tǒng)僅用64=Θ(1)種不同的Tile表示具有n個(gè)變量的布爾方程式，大大降低了自組裝運(yùn)算的空間消耗.運(yùn)算時(shí)，根據(jù)Tile的編碼及運(yùn)算規(guī)則隨機(jī)形成解空間，再通過解空間中的每個(gè)解對(duì)布爾方程中的每個(gè)變量進(jìn)行掃描，確定解空間的正確性.同年，他又用49種不同的Tile，建立了用于求解子集和問題的DNA自組裝計(jì)算模型[18].

二部圖匹配問題是圖論中的熱點(diǎn)問題，在解決各個(gè)領(lǐng)域的問題中也得到了廣泛的應(yīng)用.在二部圖匹配問題中,除了匈牙利算法之外,還有分層網(wǎng)絡(luò)算法[19]、最大流算法以及基于量子協(xié)同的智能優(yōu)化算法[20]等.在DNA計(jì)算產(chǎn)生之后，2002年高琳等人[21]提出了一種基于質(zhì)粒DNA的計(jì)算模型,并將其用于求解二部圖的匹配問題.同年Wang[22]提出了一種用于求解二部圖最大匹配的DNA算法.2003年董亞非[23]利用肽核酸(PNA)提出粘貼模型的完美匹配問題的分子算法.該算法首先將問題映射到DNA存儲(chǔ)鏈，利用PNA分子在無鹽狀態(tài)下比DNA分子更容易與DNA分子結(jié)合并穩(wěn)定存在的特性，設(shè)計(jì)編碼DNA存儲(chǔ)鏈的補(bǔ)鏈(PNA粘貼鏈),以達(dá)到計(jì)算的目的.2011年，周旭等人[24]給出了一種最大匹配問題的DNA計(jì)算算法，該方法在保持多項(xiàng)式操作時(shí)間的條件下，將解空間從O(2m)減少到O(1.618m).

本文則是利用DNA自組裝模型的高度并行性,結(jié)合二部圖本身的特征,建立了一種用于求解二部圖完美匹配的一種自組裝計(jì)算模型,對(duì)任意二部圖只需14種Tile類型就能夠得到完美匹配.

1 DNA計(jì)算自組裝模型

文獻(xiàn)[14-16]中對(duì)自組裝模型的定義及相關(guān)符號(hào)描述如下：

定義1. 一個(gè)DNA計(jì)算自組裝系統(tǒng)S是一個(gè)3元組〈T,g,τ〉，其中T為DNA Tile集合，g為結(jié)合強(qiáng)度函數(shù)，τ為熱力學(xué)溫度.

DNA Tile是帶有4個(gè)粘性末端的分子元件，它可以和帶有與其互補(bǔ)的粘性末端的DNA Tile相結(jié)合，形成規(guī)模龐大的帶有唯一結(jié)果的二維結(jié)構(gòu).一個(gè)Tile是一個(gè)四元組〈σN,σE,σS,σW〉∈Σ4,這里Σ是具有粘性末端集合.Σ是一個(gè)有限的字母(結(jié)合域)集合，包括空集null，如果沒有特別指出，empty=〈null,null,null,null〉是一個(gè)特殊的Tile，表示不與任何Tile相結(jié)合的Tile.

結(jié)合強(qiáng)度函數(shù)g:Σ×Σ→，?σ∈Σ,g(null,σ)=0,表示粘貼域強(qiáng)度為0.

對(duì)于方向集D={N,E,S,W}來講，對(duì)于所有點(diǎn)的坐標(biāo)(x,y)∈2,都有N(x,y)=(x,y+1),E(x,y)=(x+1,y),S(x,y)=(x,y-1),和W(x,y)=(x-1,y).如果?d∈D，使d(x,y)=(x′,y′),那么就說位置(x,y)和位置(x′,y′)相鄰.對(duì)于一個(gè)Tilet,d∈D,則用bdd(t)表示Tilet在邊d上的結(jié)合域.

若T是一個(gè)包含emptyTile的一個(gè)集合，A:×→T是T的一個(gè)配置.A是有限的，即A(x,y)≠empty,(x,y)∈T.A(x,y)=t表示Tilet在位置(x,y)處與配置A結(jié)合.

定義2. 在一個(gè)Tile系統(tǒng)中，A是部分Tile集T?Σ4的一個(gè)配置，那么要使Tilet∈T能夠在位置(x,y)上結(jié)合到A上，從而產(chǎn)生一個(gè)新的配置A′，必須滿足4個(gè)條件：

1) (x,y)∈A;

2)Σd∈Dg(bdd(t),bdd-1(A(d(x,y))))>τ且d-1表示和d在方向上對(duì)應(yīng)的邊;

3) ?(u,v)∈2,(u,v)≠(x,y)?A′(u,v)=A(u,v);

4)A(x,y)=t.

即要使一個(gè)Tile能夠穩(wěn)定結(jié)合到一個(gè)配置上，當(dāng)且僅當(dāng)它與相鄰的Tile的結(jié)合域強(qiáng)度之和大于或等于熱力學(xué)溫度τ.對(duì)所有結(jié)合域σ,g(σ,σ)=1,τ=2，那么一個(gè)Tilet要想結(jié)合到某位置上，它至少要和2個(gè)Tile結(jié)合.

定義3. 在一個(gè)Tile系統(tǒng)S中,A是Tile集T′?Σ4的一個(gè)配置，那么一個(gè)Tilet∈T能在位置(x,y)上從配置A上分離下來并產(chǎn)生一個(gè)新的配置A′，當(dāng)且僅當(dāng)其滿足4個(gè)條件:

1) (x,y)∈A;

2)Σd∈Dg(bdd(t),bdd-1(A(d(x,y))))<τ;

3) ?(u,v)∈2,(u,v)≠(x,y)?A′(u,v)=A(u,v);

4) (x,y)?A′.

即當(dāng)一個(gè)Tile和與它相鄰Tile的結(jié)合域強(qiáng)度之和小于熱力學(xué)溫度τ，它就能從所在配置上分離下來.例如，對(duì)所有的σ，g(σ,σ)=1并且τ=2，如果少于2個(gè)Tile在與Tilet相鄰的位置與之結(jié)合，那么Tilet就會(huì)從其位置上分離下來.

經(jīng)過連續(xù)不斷的組裝后得到的最后結(jié)果，稱為最終配置.如果在所有操作下得到的最終配置相同，則稱系統(tǒng)產(chǎn)生唯一的最終配置.

2 求解完美匹配問題的DNA自組裝計(jì)算模型

2.1 完美匹配問題

在無向圖G=(V,E)中，邊集E的任意一個(gè)子集M?E，若M中的任意2條邊都沒有公共端點(diǎn)，則稱M為圖G的一個(gè)匹配.若匹配M中的所有與匹配邊相關(guān)聯(lián)的頂點(diǎn)稱為關(guān)于M飽和點(diǎn)，否則稱為M非飽和點(diǎn)[24].

M是二部圖G中任意一個(gè)匹配，若G的任意一個(gè)互補(bǔ)點(diǎn)集V1和V2中的所有點(diǎn)都是M飽和點(diǎn)，則M就是一個(gè)完美匹配[24-26].如圖1所示，G是一個(gè)具有10個(gè)頂點(diǎn)的二部圖.其中M1={e1,e4,e8,e11,e12},M2={e1,e5,e7,e11,e12}都是圖G的完美匹配.

Fig. 1 Bipartite graph G.圖1 二部圖G

2.2 算法模型實(shí)例

本文結(jié)合完美匹配的概念及圖中各頂點(diǎn)間的鄰接關(guān)系，給出了一個(gè)基于DNA計(jì)算自組裝模型的系統(tǒng)，并為該系統(tǒng)設(shè)計(jì)編碼DNA Tile以及種子配置.在這個(gè)系統(tǒng)中，DAN Tile在一定的控制條件下執(zhí)行自組裝運(yùn)算，整個(gè)運(yùn)算過程從種子配置開始自右向左、自下向上進(jìn)行，最終將會(huì)計(jì)算出一個(gè)組裝體.若自組裝得到的結(jié)果是完美匹配，將會(huì)在模塊的左上角出現(xiàn)一個(gè)Success標(biāo)志的DNA Tile，否則模塊將會(huì)在下一步的升溫過程中溶解掉.

本文將這個(gè)系統(tǒng)定義為完美匹配自組裝系統(tǒng)Spm=〈Tpm,gpm,τpm〉,其中：Tpm為自組裝模型獲得完美匹配所使用的所有Tile的集合;gpm是Spm的結(jié)合函數(shù)，Spm的結(jié)合域?yàn)棣瞤m={null,χ,r,-,=,v}，χ={a,b,c,d,e,a′,b′,c′,d′,e′}.結(jié)合函數(shù)定義如下：

1) ?σ∈Σpm,gpm(σ,null)=gpm(null,σ)=0;

2) ?σ∈Σpm{null,=,v},gpm(σ,σ)=1;

3)gpm(v,v)=2;

4)gpm(=,=)=2;

5) ?σ,σ′∈Σpm, ifσ≠σ′, thengpm(σ,σ′)=0.

任意結(jié)合域與null的結(jié)合強(qiáng)度為0.除結(jié)合域=,v外,其余結(jié)合域與其自身的結(jié)合強(qiáng)度都為1.=,v與其自身結(jié)合強(qiáng)度為2.任何結(jié)合域與非自身結(jié)合域的結(jié)合強(qiáng)度為0.設(shè)定系統(tǒng)溫度τ=2，也就是說只有當(dāng)一個(gè)Tile的結(jié)合域強(qiáng)度之和大于或等于2時(shí)，它才能穩(wěn)定地結(jié)合到已有的集合上.

2.3 DNA Tile編碼設(shè)計(jì)

根據(jù)上述算法及完美匹配概念，本文對(duì)完美匹配自組裝系統(tǒng)中的DNA Tile的編碼設(shè)計(jì)如圖2所示：

Fig. 2 Compute Tile.圖2 運(yùn)算Tile

圖2(a)～(g)所示為完美匹配自組裝系統(tǒng)Spm的所有組裝都必須用到邊界Tile.

圖2(a)中的StartTile是組裝開始的標(biāo)志，自組裝計(jì)算從StartTile開始向左執(zhí)行.由圖2(a)可知Start=〈v,null,v,-〉，即只有滿足bdS(t)=v,bdN(t)=v,或bdE(t)=-(其中-表示Tile的結(jié)合域)的Tile才能與之結(jié)合.圖2(b)中的Tile記為EndTile是第1行組裝完成的標(biāo)志，它控制自組裝計(jì)算的方向，使其只能向上增長(zhǎng).End=〈r,-,r,null〉，只有滿足bdS(t)=r,bdN(t)=r,或bdW(t)=-的Tile才能與之結(jié)合.圖2(c)和圖2(d)中的Tile都是輔助Tile，都在種子配置第0行.前者位于最右端，其北邊與StartTile結(jié)合，后者位于最左端，與EndTile相結(jié)合.圖2(e)中的Tile記為SuccessTile,是自組裝結(jié)束的標(biāo)志，也是組裝成功的標(biāo)志.當(dāng)自組裝得到的是正確的完美匹配時(shí)，將會(huì)在組裝體的左上角出現(xiàn)一個(gè)成功標(biāo)志，即SuccessTile.由圖2可知，Success=〈null,=,r,null〉,bdN(R)=null,bdE(R)==(第2個(gè)=表示結(jié)合域),bdS(R)=r,bdW(R)=null,其西邊和北邊的結(jié)合域均為null，因此它可使得自組裝運(yùn)算不能繼續(xù)向上和向左執(zhí)行，從而結(jié)束整個(gè)組裝過程.

圖2(f)中的Tile記為RTile,是自組裝最后一步的開始標(biāo)志，它只能在S向與Z′ Tile(圖2(h))相結(jié)合.由于bdN(R)=null，所以RTile的北邊不能與任何Tile相結(jié)合，從而控制整個(gè)組織運(yùn)算過程不能繼續(xù)向上執(zhí)行.圖2(g)中的Tile記為L(zhǎng)Tile,L=〈r,r,r,null〉，是標(biāo)志每行自組裝運(yùn)算結(jié)束的Tile.由于bdW(L)=null，所以沒有Tile能夠在其西邊與之結(jié)合，從而控制每行自組裝運(yùn)算使其不能繼續(xù)向左執(zhí)行.

本文對(duì)完美匹配自組裝系統(tǒng)Spm中運(yùn)算Tile的編碼設(shè)計(jì)如圖2(h)～(n)所示.其中，圖2(h)中的Z′ Tile是控制每行自組裝運(yùn)算向左執(zhí)行的右邊界運(yùn)算Tile，它的S和N可與其他Z′ Tile或RTile相結(jié)合構(gòu)成種子配置的第0列.圖2(i)中的Tile記為κ=〈κ,null,null,null〉,是按頂點(diǎn)度數(shù)大小從右向左排列形成種子系統(tǒng)第0行的Tile，它的N與圖2(n)中滿足條件的運(yùn)算Tile的S相結(jié)合.圖2(j)中的X′ Tile是上邊界Tile，是標(biāo)志每一列自組裝運(yùn)算終止的Tile，也是用于讀取完美匹配結(jié)果的Tile.其中，X′ Tile體上的X′ 是指當(dāng)前列的頂點(diǎn)信息.

圖2(k)中Tile 〈X′,r,X′,r,〉的作用是傳遞信息.X′將當(dāng)前列的頂點(diǎn)信息向上傳遞，r將前面已經(jīng)出現(xiàn)OKTile(圖2(m))的信息向左傳遞.圖2(l)中的 Tile 〈Y′,X′,Y′,X′〉，當(dāng)bdS(t)≠bdE(t)時(shí)，X′和Y′分別將當(dāng)前行和當(dāng)前列的頂點(diǎn)信息向左和向上傳遞.圖2(m)中的TileOK=〈X′,X′,X′,r〉，當(dāng)bdS(t)=bdE(t)時(shí)，西邊的r將已有OKTile的信息向左傳遞，同時(shí)其北邊X′ 將當(dāng)前列的頂點(diǎn)信息向上傳遞.圖2(n)所示Tileδ=〈δ,-,κ,-〉.對(duì)?i∈1,2,…,n/2,κi,δi∈χ，其中，κi是種子系統(tǒng)第0行第i列的Tile信息，枚舉了種子系統(tǒng)第0行中所有的Tile的信息(種子系統(tǒng)中所有Tile的N的結(jié)合域).δi枚舉了所有能與κiTile相結(jié)合的Tile的信息.κ是由κi組成的集合，δ是由δi組成的集合.不同的δTile間可以在E和W相互結(jié)合.

2.4 運(yùn)算Tile的設(shè)計(jì)算法

根據(jù)2.1節(jié)可知，二部圖的完美匹配作為一種特殊的匹配方式，它具有3個(gè)基本要求：1)必須包含圖中所有頂點(diǎn); 2)完美匹配中的任意2條邊都不能有公共頂點(diǎn)(任意2條邊都不相鄰); 3)完美匹配中每條邊的2個(gè)端點(diǎn)必須分別屬于二部圖的2個(gè)互補(bǔ)點(diǎn)集.根據(jù)以上3點(diǎn)可知，若圖中存在1度頂點(diǎn)，那么與這個(gè)1度頂點(diǎn)相關(guān)聯(lián)的邊有且只有這一條包含在完美匹配中.所以為了簡(jiǎn)化求解的復(fù)雜性，本文在編碼設(shè)計(jì)DNA Tile前，首先找出所有子圖中的1度頂點(diǎn)、1度頂點(diǎn)的鄰接點(diǎn)及與它們相關(guān)聯(lián)的邊，并根據(jù)這種關(guān)系設(shè)計(jì)編碼對(duì)應(yīng)的頂點(diǎn)Tile.具體算法如BigraphToTile(G,E,V)所示，其中V和E是圖G的頂點(diǎn)集和邊集.

算法1.BigraphToTile(G).

S←正偶數(shù)集合；

（1）焊接主梁桁架的上弦桿（采用￠48鋼管），上弦桿水平接頭處內(nèi)穿長(zhǎng)800mm的無縫鋼管，左右分別搭接400mm，上弦桿與無縫鋼管焊接牢固。

G=(V,E)；

TILE←?；

if |V|∈S

while (V′≠?)

ifv∈V′

TILE←TILE∪{Tv,Tv-1}；

designTv和Tv-1使得bdN(v)=bdS(v-1)；

E←E-{Ev,Ev-1}；

end if

G=(V,E)；

BigraphToTile(G)；

end while

while (V′=?且V(G)=?)

ifv∈V且v≠?

end if

end while

end if

returnTILE.

算法1中，G表示代求解的圖，V和E分別為G的頂點(diǎn)集合和邊集;V′ 表示圖G中所有1度頂點(diǎn)構(gòu)成的集合，v表示圖G中的頂點(diǎn)，v-1為v相鄰頂點(diǎn);Tv表示所設(shè)計(jì)的關(guān)于頂點(diǎn)v的所有Tile構(gòu)成的集合，Tv-1是關(guān)于頂點(diǎn)v-1所設(shè)計(jì)的所有Tile構(gòu)成的集合,Ev表示與頂點(diǎn)v相關(guān)聯(lián)的邊集.TILE是所有1度頂點(diǎn)和非1度頂點(diǎn)的頂點(diǎn)Tile的集合.

如算法1所示，本文的DNA Tile編碼設(shè)計(jì)步驟如下：首先找出原圖G中1度頂點(diǎn)v構(gòu)成的集合V′,若V′ 中存在1度頂點(diǎn)，那么設(shè)計(jì)DNA Tile使vTile只能與v-1Tile相結(jié)合;從原圖刪除頂點(diǎn)v和v-1，重置圖G;重復(fù)上述操作，直到圖G中頂點(diǎn)為0.若V′=?，即圖中沒有1度頂點(diǎn)，則為G中的每對(duì)相鄰的頂點(diǎn)設(shè)計(jì)頂點(diǎn)Tile，使G中每對(duì)相鄰的頂點(diǎn)所對(duì)應(yīng)Tile可以相互結(jié)合.

對(duì)于一個(gè)具有10個(gè)頂點(diǎn)的二部圖(如圖1所示)，其完美匹配自組裝系統(tǒng)的種子配置如圖3所示:

根據(jù)算法1，將5個(gè)頂點(diǎn)Tile按度數(shù)從小到大、從右向左排列，形成種子配置的第0行.剩下的5個(gè)頂點(diǎn)Tile構(gòu)成自組裝運(yùn)算所需的Tile集T.同時(shí)將T中的所有Tile通過S和N的相互結(jié)合，由下至上排列形成種子系統(tǒng)第0列.

在τ=2的條件下，按照編碼規(guī)則，在自組裝的第1步結(jié)合上去的t∈T將會(huì)形成一個(gè)計(jì)算結(jié)果，本文將其稱為結(jié)果序列.根據(jù)DNA自組裝計(jì)算的高度并行性及海量的存儲(chǔ)能力可知，若自組裝運(yùn)算數(shù)量足夠大，最終一定能夠得到完美匹配.但由于結(jié)合的隨機(jī)性，結(jié)果序列中可能會(huì)出現(xiàn)重復(fù)的頂點(diǎn)Tile，很顯然這種結(jié)果序列不是完美匹配.

為了將完美匹配從眾多的結(jié)果序列中分離出來，本文同時(shí)在種子配置中設(shè)計(jì)了結(jié)果序列檢測(cè)部分，檢測(cè)結(jié)果序列中是否有重復(fù)的頂點(diǎn)Tile.若沒有，說明結(jié)果序列是完美匹配，將在組裝體左上角出現(xiàn)一個(gè)SuccessTile，從而分離出完美匹配；否則，組裝體將在下一步升溫過程中溶解.T中所有Tile的S和N相互結(jié)合，形成種子配置的第0列，即種子配置的結(jié)果序列檢測(cè)部分.這里稱結(jié)果序列檢測(cè)部分的每個(gè)Tile叫檢測(cè)Tile.

2.5 算法步驟

在τ=2的條件下，二部圖G的完美匹配自組裝過程如下：

Step1. ?i=0,1,…,4，位置(xs-i,ys)∈Q1,bdW(S0(xs-i,ys))=-,bdN(S0(xs-i-1,ys-1))=κi.只有滿足結(jié)合域?yàn)閎dE(S0(xs-i,ys))=-,bdS(S0(xs-i,ys))=κi的Tilet,t∈U1,才能穩(wěn)定地結(jié)合到S0上.在位置(xs-6,ys)∈Q1,bdW(S0(xs-5,ys))=-,bdN(S0(xs-6,ys-1))=r，U1中只有結(jié)合域bdS(t)=r,bdE(t)=r的EndTile滿足條件.EndTile結(jié)合到配置上形成新的配置S1.Step1完成后，所產(chǎn)生的組裝體如圖4(a)所示.

Fig. 4 Perfect matching self-assembly model of the bipartite graph G shown in Fig.1.圖4 圖1二部圖G的完美匹配自組裝模型

在此過程中，aTile一旦在結(jié)果序列中掃描到自身，將不會(huì)繼續(xù)掃描，而是將信號(hào)r繼續(xù)向左傳遞.在位置(xs-6,ys+1)上，因?yàn)閎dW(S1(xs-5,ys+1))=r，bdN(S1(xs-6,ys))=r，故在t∈U2中，只有滿足結(jié)合域?yàn)閎dS(t)=r和bdE(t)=r的LTile才能穩(wěn)定地結(jié)合到配置上，形成配置S2,如圖4(b)所示.

Step3.重復(fù)Step2，分別對(duì)對(duì)應(yīng)位置上b′ Tile，c′ Tile，d′ Tile和e′ Tile進(jìn)行檢測(cè).檢測(cè)結(jié)果如圖4(c)～(f)所示.在檢測(cè)完e′ Tile之后，形成配置S6，如圖4(g)所示.

Step4. 完成自組裝.由圖4(g)可知，?i=1,2,…,5，配置S6中的位置(xs-i,ys+6)∈Q7，暴露在外面的結(jié)合域?yàn)閎dW(S6(xs-i+1,ys+6))==，bdN(S6(xs-i,ys+5))=κi.故在此步驟中，只有滿足結(jié)合域bdS(t)=κi和bdE(t)==的Tile才能穩(wěn)定地結(jié)合到配置上.當(dāng)i=6時(shí)，即在位置(xs-6,ys+6)處，由于暴露在外面的結(jié)合域?yàn)閎dW(S6(xs-5,ys+6))==，bdN(S6(xs-6,ys+5))=r，只有結(jié)合域?yàn)閎dS(t)=r和bdE(t)==的SuccessTile才能穩(wěn)定地結(jié)合到配置上，進(jìn)而完成整個(gè)組裝過程.如圖4(h)所示.

記ti j∈Ui是能夠在第i步中在位置(xs-j,ys-i)∈Qj處結(jié)合到配置Si上并能穩(wěn)定存在的Tile，Δ=Σd∈Dg(bd(t),bdd-1(A(d(x,y))))≥τ是tTile能夠穩(wěn)定存在于配置上的條件.具體的自組裝算法記為TileCompute(S0,n).

算法2.TileCompute(S0,n).

Sn←S0；

fori←0 ton

Sn←PerStep(Si-1,i)；

end for

ifSn(xs-n,ys+n)=Success

returnSn；

else

return failure；

end if

PerStep(Si-1,i)；

forj←0 tom

Si(xs-j,ys+i)=ti j；

end for

returnSi.

2.6 計(jì)算結(jié)果

本文提出的完美匹配自組裝模型經(jīng)2.5節(jié)的Step1自組裝產(chǎn)生結(jié)果序列的過程中，對(duì)每個(gè)位置(x,y)∈Q1，U1中可能會(huì)有多個(gè)Tile能夠結(jié)合到該位置上.而對(duì)于同一個(gè)Tilet,t∈U1，可能也能夠結(jié)合到不同的位置(x,y)∈Q1上.也就是說位置(x,y)∈Q1和Tilet∈U1是多對(duì)一的關(guān)系.所以，在結(jié)果序列中可能會(huì)出現(xiàn)重復(fù)的頂點(diǎn)Tile，而這樣的結(jié)果序列顯然不是完美匹配.為了將完美匹配的結(jié)果序列與這些非完美匹配的結(jié)果序列分離開來，本文設(shè)計(jì)了結(jié)果序列檢測(cè)部分.若結(jié)果序列是完美匹配，最終將在組裝體的左上角出現(xiàn)一個(gè)標(biāo)記Tile——SuccessTile；若不是完美匹配，組裝體將在下一步升溫過程中溶解，如圖5(a)所示:

Fig. 5 Self-assembly model for perfect matching.圖5 完美匹配自組裝模型

圖5(a)是種子配置經(jīng)Step1自組裝后形成的結(jié)果序列.由圖5(a)可知，在結(jié)果序列中b′ Tile重復(fù)出現(xiàn)，而c′ Tile沒有出現(xiàn)，顯然這個(gè)結(jié)果序列不是完美匹配.圖5(b)是種子配置的檢測(cè)部分對(duì)結(jié)果序列進(jìn)行檢測(cè)的自組裝模型.

由圖5(b)可知，在對(duì)c′ Tile進(jìn)行檢測(cè)時(shí)，由于沒有在結(jié)果序列中掃描到自身，故bdW(c′)=c將會(huì)一直向左傳遞.在位置(xs-6,ys+3)上，暴露在W和N的結(jié)合域bdW(S2(xs-5,ys+3))=c′，bdN(S2(xs-6,ys+2))=r，而U3中沒有結(jié)合域?yàn)閎dS(t)=r和bdE(t)=c′的Tile能夠結(jié)合到該位置上，從而終止自組裝運(yùn)算.檢測(cè)完成后，使τ=3.由結(jié)合函數(shù)的定義可知?σ∈Σpm{null,=,v},gpm(σ,σ)=1.根據(jù)定義3可知，在τ=3的條件下，TileS2(xs-5,ys+3)會(huì)從組裝體上分離下來.同樣地，其他Tile最終也將分離下來，從而使整個(gè)組裝體溶解掉.

3 算法分析

本文根據(jù)完美匹配概念及圖中頂點(diǎn)間的鄰接關(guān)系，編碼完美匹配自組裝系統(tǒng)用到的計(jì)算Tile.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的二部圖來說，首先利用算法1根據(jù)圖1中各頂點(diǎn)間的鄰接關(guān)系，編碼DNA Tile并形成種子系統(tǒng).編碼后的DNA Tile通過2.5節(jié)中的組裝過程進(jìn)行自組裝.若組裝成功，將在組裝體左上角出現(xiàn)紅色的SuccessTile；否則，組裝體將在下一步升溫過程中溶解.

定理1. 完美匹配自組裝系統(tǒng)Spm=〈Tpm,gpm,τpm〉計(jì)算終止時(shí)返回的自組裝結(jié)構(gòu)是一個(gè)完美匹配.

D0=〈X′,r,X′,r〉,

D1=〈Y′,X′,Y′,X′〉,

D2=〈X′,X′,X′,r〉,

D3=〈δ,-,κ,-〉,

D4=〈v,null,v,-〉,

D5=〈r,-,r,null〉,

D6=〈v,null,null,null〉,

D7=〈r,null,null,null〉,

D8=〈null,=,r,null〉,

D9=〈null,null,v,=〉,

D10=〈r,r,r,null〉,

D11=〈v,null,v,Z′〉,

D12=〈κ,null,null,null〉,

D13=〈null,=,X′,=〉.

由2.4節(jié)可知：1)種子系統(tǒng)中第0行的D12與第0列的D11(或者D3Tile)是二部圖中的頂點(diǎn)Tile，且兩者交集為空;2)只有當(dāng)D3Tile與D12Tile所代表的頂點(diǎn)相鄰，D3Tile和D12Tile才能在自組裝運(yùn)算中穩(wěn)定結(jié)合.由1)和2)和完美匹配的3個(gè)基本要求可知，若自組裝計(jì)算2.5節(jié)的Step1完成后形成結(jié)果序列中沒有重復(fù)的頂點(diǎn)Tile，則這個(gè)自組裝結(jié)果就是一個(gè)完美匹配.在該系統(tǒng)中，除Step1之外，其余所有步驟都是在檢測(cè)Step1產(chǎn)生的結(jié)果中沒有重復(fù)序列.

接下來證明檢測(cè)步驟中能夠把不成功的計(jì)算結(jié)果檢測(cè)出來而不被留在最終計(jì)算結(jié)果里.

對(duì)于任意含有重復(fù)Tile的S1,根據(jù)2.4節(jié)描述的檢測(cè)過程中 ，?i∈{1,2,…,k-1},i表示S1的橫坐標(biāo)，結(jié)合到位置(-i,d-1)上的S1是D1Tile.當(dāng)i=k時(shí)，對(duì)于位置(-k,d-1)，只有E的結(jié)合域是Zd-1、S的結(jié)合域?yàn)閞的Tilet才能穩(wěn)定地結(jié)合上去，但Γ+中沒有滿足條件的Tilet.若假設(shè)在位置(-k+1,d-1)處的Tile為Tilet′，那么根據(jù)2.2節(jié)中g(shù)pm的定義，此時(shí)Tilet′的結(jié)合域強(qiáng)度和為2(E結(jié)合域強(qiáng)度為1，S結(jié)合域強(qiáng)度為1，N和W的結(jié)合域強(qiáng)度為0).在自組裝運(yùn)算過程中，系統(tǒng)溫度τpm=2. Tilet′能夠穩(wěn)定結(jié)合在配置Sd上，但當(dāng)系統(tǒng)溫度升高到τpm=3時(shí)，根據(jù)定義3可知Tilet′將會(huì)從Sd上分離下來.

證畢.

定理2. 完美匹配自組裝系統(tǒng)Spm=〈Tpm,gpm,τpm〉的組裝時(shí)間是O(n)的.

?w∈W0,S1(w)∈Uw，

證畢.

定理3. 完美匹配自組裝系統(tǒng)Spm=〈Tpm,gpm,τpm〉所需的Tile個(gè)數(shù)是Θ(n2).

證畢.

4 結(jié) 論

本文針對(duì)二部圖完美匹配問題提出了一種基于DNA計(jì)算自組裝模型的算法.根據(jù)二部圖完美匹配的概念及二部圖中頂點(diǎn)間的鄰接關(guān)系，設(shè)計(jì)編碼DNA Tile及種子系統(tǒng)，并利用DNA計(jì)算自組裝模型本身所具有的高度并行性、海量存儲(chǔ)能力、低能耗和組裝的自治性等特性，使運(yùn)算DNA Tile在一定控制條件下執(zhí)行自治的組裝運(yùn)算.

本文以一個(gè)具有10個(gè)頂點(diǎn)的二部圖(如圖1所示)為例,介紹了該算法的步驟：1) 給出DNA Tile的編碼設(shè)計(jì)方案，該方案對(duì)所有子圖中的 1度頂點(diǎn)t及與其相鄰的頂點(diǎn)t-1進(jìn)行編碼，使tTile只能與t-1Tile相結(jié)合.由于這種處理方法避免了除t之外與t-1相鄰的其他頂點(diǎn)的Tile的設(shè)計(jì)，故降低了DNA Tile的個(gè)數(shù).同時(shí)，由于tTile是t-1Tile唯一能夠結(jié)合的DNA Tile，所以在2.5節(jié)的Step1之后，生成的結(jié)果序列中沒有其他DNA Tile與t-1Tile爭(zhēng)奪與tTile結(jié)合的機(jī)會(huì)，從而提高了結(jié)果序列的準(zhǔn)確率.另外，本文還設(shè)計(jì)了結(jié)果序列檢測(cè)部分，通過對(duì)結(jié)果序列進(jìn)行掃描，檢測(cè)結(jié)果序列中是否存在重復(fù)的頂點(diǎn)Tile，從而判斷結(jié)果序列是否是完美匹配.若不存在重復(fù)的頂點(diǎn)Tile，則說明結(jié)果序列是完美匹配，那么最終將會(huì)在組裝體的左上角出現(xiàn)紅色的SuccessTile，結(jié)果在組裝體的最上面一行讀取;否則，結(jié)果序列不是完美匹配.

在本系統(tǒng)中，在編碼過程中的每一步都需要從子圖G(V,E)中找出所有度數(shù)為1的頂點(diǎn)，并將1度頂點(diǎn)以及與1度頂點(diǎn)相鄰的頂點(diǎn)和與它們相關(guān)聯(lián)的邊從圖G中除去，并重置圖G.

利用DNA自組裝進(jìn)行計(jì)算是一種新的計(jì)算理念，通過設(shè)計(jì)具有不同功能的DNA Tile，進(jìn)而形成代表問題的解結(jié)構(gòu)，從理論上展現(xiàn)了自組裝模型應(yīng)用于復(fù)雜問題的計(jì)算.

[1]Xu Jin, Bao Zheng. Neural networks and graph theory[J]. Scientia Sinica: Technologiea, 2001, 31(6): 533-555 (in Chinese)

(許進(jìn), 保錚. 神經(jīng)網(wǎng)絡(luò)與圖論[J]. 中國(guó)科學(xué): 技術(shù)科學(xué), 2001, 31(6): 533-555)

[2]Azadeh A, Faiz Z S, Asadzadeh S M, et al. An integrated artificial neural network-computer simulation for optimization of complex tandem queue systems[J]. Mathematics and Computers in Simulation, 2011, 82(4): 666-678

[3]Liu Yang. Database processing in quantum computers[D]. Beijing: Tsinghua University, 2008 (in Chinese)

(劉洋. 量子計(jì)算機(jī)中的數(shù)據(jù)庫處理[D]. 北京: 清華大學(xué), 2008)

[4]Colnaghi T D, Ariano G M, Facchini S, et al. Quantum computation with programmable connections between gates[J]. Physics Letters A, 2012, 376(45): 2940-2943

[5]Rahman M O, Hussain A, Scavino E, et al. DNA computer based algorithm for recyclable waste paper segregation[J]. Applied Soft Computing, 2015, 31: 223-240

[6]Sun Y H, Chen M Y. A DNA-based solution to the graph isomorphism problem using Adleman-Lipton model with stickers[J]. Applied Mathematics and Computation, 2008, 197(2): 672-686

[7]Ouyang Q, Kaplan P D, Liu S, et al. DNA solution of the maximal clique problem[J]. Science, 1997, 278(17): 446-449

[8]Xu J, Qiang X, Yang Y, et al. An unenumerative DNA computing model for vertex coloring problem[J]. IEEE Trans on Nanobioscience, 2011, 10(2): 94-98

[9]Beneson Y, Tamar P, Adar R, et al. Programmable and autonomous computing machine made of biomolecules[J]. Nature, 2001, 414(22): 430-434

[10]Shi X, Chen C, Li X, et al. Size-controllable DNA nanoribbons assembled from three types of reusable brick single-strand DNA tiles[J]. Soft Matter, 2015, 11(43): 8484-8492

[11]Shi X, Lu W, Wang Z, et al. Programmable DNA tile self-assembly using a hierarchical sub-tile strategy[J]. Nanotechnology, 2014, 25(7): 075602

[12]Feynman R P. There’s plenty of room at the bottom[J]. Engineering and Science, 1960, 23(5): 22-36

[13]Adleman L. Molecular computation of solution to combinatorial problems[J]. Science, 1994, 266(5187): 1021-1024

[14]Winfree E. Algorithmic self-assembly of DNA[D]. Los Angeles: California Institute of Technology, 1998

[15]Zhang Xuncai. The research and applications of DNA computing by self-assembly[D]. Wuhan: Huazhong University of Science and Technology, 2009 (in Chinese)

(張勛才.自組裝DNA計(jì)算模型的研究及應(yīng)用[D]. 武漢: 華中科技大學(xué), 2009)

[16]Chen Zhihua. Researches on several cryptological problems based on DNA computing by self-assembly[D]. Wuhan: Huazhong University of Science and Technology, 2009 (in Chinese)

(陳智華. 基于DNA計(jì)算自組裝模型的若干密碼問題研究[D]. 武漢: 華中科技大學(xué), 2009)

[17]Brun Y. Solving satisfiability in the tile assembly model with a constant-size tiletset[J]. Journal of Algorithms, 2008, 63(4): 151-166

[18]Brun Y. Solving NP-complete problems in the tile assembly model[J]. Theoretical Computer Science, 2008, 395(1): 31-46

[19]Tang Min, Guan Jian, Deng Guoqiang, et al. A new algorithm and application of solving maximum matching problem of bipartite graph[J]. Computer Systems Applications, 2012, 21(3): 72-75 (in Chinese)

(唐敏, 關(guān)鍵, 鄧國(guó)強(qiáng), 等. 一種求解二部圖最大匹配問題新算法及其應(yīng)用[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用, 2012, 21(3): 72-75)

[20]Ying Guisheng, Cui Xiaohui, Dong Hongbin, et al. Quantum-cooperative method for maximum weight perfect matching problem of bipartite graph[J]. Journal of Computer Research and Development, 2014, 51(11): 2573-2584 (in Chinese)

(印桂生, 崔曉暉, 董紅斌, 等. 量子協(xié)同的二分圖最大權(quán)完美匹配求解方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(11): 2573-2584)

[21]Gao Lin, Ma Runnian, Xu Jin. The molecular algorithm of the matching problem based on plasmid DNA[J]. Progress in Biochemistry and Biophysics, 2002, 29(5): 820-823 (in Chinese)

(高琳, 馬潤(rùn)年, 許進(jìn). 基于質(zhì)粒DNA匹配問題的分子算法[J]. 生物化學(xué)與生物物理進(jìn)展, 2002, 29(5): 820-823)

[22]Wang Shiying. DNA computing of bipartite graphs for maximum matching[J]. Journal of Mathematical Chemistry, 2002, 31(3): 271-279

[23]Dong Yafei. The study of some DNA computing sticker models[D]. Wuhan: Huazhong University of Science and Technology, 2003 (in Chinese)

(董亞非. 若干DNA計(jì)算粘貼模型的研究[D]. 武漢: 華中科技大學(xué), 2003)

[24]Zhou Xu, Li Kenli, Yue Guangxue, et al. A volume molecular solution for maximum matching problem on DNA-based computing[J]. Journal of Computer Research and Development, 2011, 48(11): 2147-2154 (in Chinese)

(周旭, 李肯利, 樂光學(xué), 等. 一種最大匹配問題DNA計(jì)算算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(11): 2147-2154)

[25]Buckley F, Lewinter M. A Friendly Introduction to Graph Theory[M]. Upper Saddle River, NJ: Prentice Hall, 2005: 42-43

[26]Lü Zongwei, Lin Zhenghui, Zhang Lei. Boolean mapping algorithm based on perfect matching of bipartite graph[J]. Journal of Computer-Aide Design & Computer Graphics, 2001, 13(11): 961-965 (in Chinese)

(呂宗偉, 林爭(zhēng)輝, 張鐳. 基于二部圖完美匹配的布爾匹配算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2001, 13(11): 961-965)

Lan Wenfei, born in 1966. Master and professor. Her main research interests include databases, software technology.

Xing Zhibao, born in 1987. Master candidate. Her main research interests include DNA computing.

Huang Jun, born in 1991. Master candidate. His main research interests include DNA computing.

Qiang Xiaoli, born in 1979. PhD and associate professor. Her main research interests include molecular computing and bioinformatics.

The DNA Self-Assembly Computing Model for Solving Perfect Matching Problem of Bipartite Graph

Lan Wenfei, Xing Zhibao, Huang Jun, and Qiang Xiaoli

(CollegeofComputerScience,South-CentralUniversityforNationalities,Wuhan430074)

Biological systems are far more complex and robust than systems we can engineer today, and Because of its advantages of stability and specificity, DNA molecules have been used for the construction of nano-scale structures. With the development of DNA molecule self-assembly strategy, lots of programmable DNA tiles are constructed and used for solving NP problems. The tile assembly model, a formal model of crystal growth, is a highly distributed parallel model of nature’s self-assembly with the traits of highly distributed parallel, massive storage density and low power consumption. In the system, a function can be computed by deterministic assembly and identified two important quantities: the number of tile types and the assembly speed of the computation. Here a DNA self-assembly model for perfect matching problem of bipartite graph is demonstrated, and a 10-vertices bipartite graph is used as an example to illustrate this model. The computation is nondeterministic and each parallel assembly is executed in time linear in the input. The result shows that the successful solutions can be found among the many parallel assemblies, and it requires only a constant number of different tile types: 14.

perfect matching; bipartite graph; DNA computing; self-assembly; tile

2015-04-22；

2016-04-28

國(guó)家自然科學(xué)基金項(xiàng)目(61379059)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金項(xiàng)目(CZZ13003);2015年中南民族大學(xué)研究生優(yōu)秀學(xué)位論文培育項(xiàng)目

強(qiáng)小利(qiangxl@mail.scuec.edu.cn)

TP301.6

This work was supported by the National Natural Science Foundation of China (61379059), the Fundamental Research Funds for the Central Universities (CZZ13003), and the Master Candidate Excellent Thesis Cultivation Project of South-Central University for Nationalities in 2015.