藍雯飛 邢志寶 黃 俊 強小利

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

?

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

藍雯飛 邢志寶 黃 俊 強小利

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

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

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

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

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

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

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

1 DNA計算自組裝模型

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

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

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

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

對于方向集D={N,E,S,W}來講，對于所有點的坐標(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′)相鄰.對于一個Tilet,d∈D,則用bdd(t)表示Tilet在邊d上的結(jié)合域.

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

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

1) (x,y)∈A;

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

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

4)A(x,y)=t.

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

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

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)一個Tile和與它相鄰Tile的結(jié)合域強度之和小于熱力學(xué)溫度τ，它就能從所在配置上分離下來.例如，對所有的σ，g(σ,σ)=1并且τ=2，如果少于2個Tile在與Tilet相鄰的位置與之結(jié)合，那么Tilet就會從其位置上分離下來.

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

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

2.1 完美匹配問題

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

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

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

2.2 算法模型實例

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

本文將這個系統(tǒng)定義為完美匹配自組裝系統(tǒng)Spm=〈Tpm,gpm,τpm〉,其中：Tpm為自組裝模型獲得完美匹配所使用的所有Tile的集合;gpm是Spm的結(jié)合函數(shù)，Spm的結(jié)合域為Σpm={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é)合強度為0.除結(jié)合域=,v外,其余結(jié)合域與其自身的結(jié)合強度都為1.=,v與其自身結(jié)合強度為2.任何結(jié)合域與非自身結(jié)合域的結(jié)合強度為0.設(shè)定系統(tǒng)溫度τ=2，也就是說只有當(dāng)一個Tile的結(jié)合域強度之和大于或等于2時，它才能穩(wěn)定地結(jié)合到已有的集合上.

2.3 DNA Tile編碼設(shè)計

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

Fig. 2 Compute Tile.圖2 運算Tile

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

圖2(a)中的StartTile是組裝開始的標(biāo)志，自組裝計算從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)志，它控制自組裝計算的方向，使其只能向上增長.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)自組裝得到的是正確的完美匹配時，將會在組裝體的左上角出現(xiàn)一個成功標(biāo)志，即SuccessTile.由圖2可知，Success=〈null,=,r,null〉,bdN(R)=null,bdE(R)==(第2個=表示結(jié)合域),bdS(R)=r,bdW(R)=null,其西邊和北邊的結(jié)合域均為null，因此它可使得自組裝運算不能繼續(xù)向上和向左執(zhí)行，從而結(jié)束整個組裝過程.

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

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

圖2(k)中Tile 〈X′,r,X′,r,〉的作用是傳遞信息.X′將當(dāng)前列的頂點信息向上傳遞，r將前面已經(jīng)出現(xiàn)OKTile(圖2(m))的信息向左傳遞.圖2(l)中的 Tile 〈Y′,X′,Y′,X′〉，當(dāng)bdS(t)≠bdE(t)時，X′和Y′分別將當(dāng)前行和當(dāng)前列的頂點信息向左和向上傳遞.圖2(m)中的TileOK=〈X′,X′,X′,r〉，當(dāng)bdS(t)=bdE(t)時，西邊的r將已有OKTile的信息向左傳遞，同時其北邊X′ 將當(dāng)前列的頂點信息向上傳遞.圖2(n)所示Tileδ=〈δ,-,κ,-〉.對?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 運算Tile的設(shè)計算法

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

算法1.BigraphToTile(G).

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

（1）焊接主梁桁架的上弦桿（采用￠48鋼管），上弦桿水平接頭處內(nèi)穿長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的頂點集合和邊集;V′ 表示圖G中所有1度頂點構(gòu)成的集合，v表示圖G中的頂點，v-1為v相鄰頂點;Tv表示所設(shè)計的關(guān)于頂點v的所有Tile構(gòu)成的集合，Tv-1是關(guān)于頂點v-1所設(shè)計的所有Tile構(gòu)成的集合,Ev表示與頂點v相關(guān)聯(lián)的邊集.TILE是所有1度頂點和非1度頂點的頂點Tile的集合.

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

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

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

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

為了將完美匹配從眾多的結(jié)果序列中分離出來，本文同時在種子配置中設(shè)計了結(jié)果序列檢測部分，檢測結(jié)果序列中是否有重復(fù)的頂點Tile.若沒有，說明結(jié)果序列是完美匹配，將在組裝體左上角出現(xiàn)一個SuccessTile，從而分離出完美匹配；否則，組裝體將在下一步升溫過程中溶解.T中所有Tile的S和N相互結(jié)合，形成種子配置的第0列，即種子配置的結(jié)果序列檢測部分.這里稱結(jié)果序列檢測部分的每個Tile叫檢測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é)合域為bdE(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é)果序列中掃描到自身，將不會繼續(xù)掃描，而是將信號r繼續(xù)向左傳遞.在位置(xs-6,ys+1)上，因為bdW(S1(xs-5,ys+1))=r，bdN(S1(xs-6,ys))=r，故在t∈U2中，只有滿足結(jié)合域為bdS(t)=r和bdE(t)=r的LTile才能穩(wěn)定地結(jié)合到配置上，形成配置S2,如圖4(b)所示.

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

Step4. 完成自組裝.由圖4(g)可知，?i=1,2,…,5，配置S6中的位置(xs-i,ys+6)∈Q7，暴露在外面的結(jié)合域為bdW(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時，即在位置(xs-6,ys+6)處，由于暴露在外面的結(jié)合域為bdW(S6(xs-5,ys+6))==，bdN(S6(xs-6,ys+5))=r，只有結(jié)合域為bdS(t)=r和bdE(t)==的SuccessTile才能穩(wěn)定地結(jié)合到配置上，進而完成整個組裝過程.如圖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 計算結(jié)果

本文提出的完美匹配自組裝模型經(jīng)2.5節(jié)的Step1自組裝產(chǎn)生結(jié)果序列的過程中，對每個位置(x,y)∈Q1，U1中可能會有多個Tile能夠結(jié)合到該位置上.而對于同一個Tilet,t∈U1，可能也能夠結(jié)合到不同的位置(x,y)∈Q1上.也就是說位置(x,y)∈Q1和Tilet∈U1是多對一的關(guān)系.所以，在結(jié)果序列中可能會出現(xiàn)重復(fù)的頂點Tile，而這樣的結(jié)果序列顯然不是完美匹配.為了將完美匹配的結(jié)果序列與這些非完美匹配的結(jié)果序列分離開來，本文設(shè)計了結(jié)果序列檢測部分.若結(jié)果序列是完美匹配，最終將在組裝體的左上角出現(xiàn)一個標(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)，顯然這個結(jié)果序列不是完美匹配.圖5(b)是種子配置的檢測部分對結(jié)果序列進行檢測的自組裝模型.

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

3 算法分析

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

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

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

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

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

證畢.

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

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

證畢.

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

證畢.

4 結(jié) 論

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

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

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

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

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

(許進, 保錚. 神經(jīng)網(wǎng)絡(luò)與圖論[J]. 中國科學(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)

(劉洋. 量子計算機中的數(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計算模型的研究及應(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計算自組裝模型的若干密碼問題研究[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)鍵, 鄧國強, 等. 一種求解二部圖最大匹配問題新算法及其應(yīng)用[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]. 計算機研究與發(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)

(高琳, 馬潤年, 許進. 基于質(zhì)粒DNA匹配問題的分子算法[J]. 生物化學(xué)與生物物理進展, 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計算粘貼模型的研究[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]. 計算機研究與發(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)

(呂宗偉, 林爭輝, 張鐳. 基于二部圖完美匹配的布爾匹配算法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報, 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

國家自然科學(xué)基金項目(61379059)；中央高校基本科研業(yè)務(wù)費專項基金項目(CZZ13003);2015年中南民族大學(xué)研究生優(yōu)秀學(xué)位論文培育項目

強小利(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.