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

藍雯飛 邢志寶 黃 俊 強小利

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

?

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

藍雯飛 邢志寶 黃 俊 強小利

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

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

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

在計算面臨的三大類問題(即容易、困難和不可計算)中，對于容易問題，傳統電子計算機可以輕松地處理，但是對于困難問題(一般指NP-完全問題)，計算時間將會隨著計算規模的增大而呈指數增長.針對這個問題，很多科學家將目光轉向對其他類型的計算機結構研究上，從而類似于神經網絡計算機[1-2]、量子計算機[3-4]以及DNA計算機模型[5-11]等應運而生.DNA計算機模型，憑借其高度的并行計算能力和海量的存儲能力在各種新型計算機中脫穎而出,在很多領域(比如生物、物理、數學及計算機科學)中都得到了廣泛的應用，并成為解決NP難問題的一種潛在的方案.

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

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

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

1 DNA計算自組裝模型

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

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

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

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

對于方向集D={N,E,S,W}來講，對于所有點的坐標(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上的結合域.

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

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

1) (x,y)∈A;

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

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

4)A(x,y)=t.

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

定義3. 在一個Tile系統S中,A是Tile集T′?Σ4的一個配置，那么一個Tilet∈T能在位置(x,y)上從配置A上分離下來并產生一個新的配置A′，當且僅當其滿足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′.

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

經過連續不斷的組裝后得到的最后結果，稱為最終配置.如果在所有操作下得到的最終配置相同，則稱系統產生唯一的最終配置.

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

2.1 完美匹配問題

在無向圖G=(V,E)中，邊集E的任意一個子集M?E，若M中的任意2條邊都沒有公共端點，則稱M為圖G的一個匹配.若匹配M中的所有與匹配邊相關聯的頂點稱為關于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 算法模型實例

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

本文將這個系統定義為完美匹配自組裝系統Spm=〈Tpm,gpm,τpm〉,其中：Tpm為自組裝模型獲得完美匹配所使用的所有Tile的集合;gpm是Spm的結合函數，Spm的結合域為Σpm={null,χ,r,-,=,v}，χ={a,b,c,d,e,a′,b′,c′,d′,e′}.結合函數定義如下：

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.

任意結合域與null的結合強度為0.除結合域=,v外,其余結合域與其自身的結合強度都為1.=,v與其自身結合強度為2.任何結合域與非自身結合域的結合強度為0.設定系統溫度τ=2，也就是說只有當一個Tile的結合域強度之和大于或等于2時，它才能穩定地結合到已有的集合上.

2.3 DNA Tile編碼設計

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

Fig. 2 Compute Tile.圖2 運算Tile

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

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

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

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

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

2.4 運算Tile的設計算法

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

算法1.BigraphToTile(G).

S←正偶數集合；

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

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

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

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

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

為了將完美匹配從眾多的結果序列中分離出來，本文同時在種子配置中設計了結果序列檢測部分，檢測結果序列中是否有重復的頂點Tile.若沒有，說明結果序列是完美匹配，將在組裝體左上角出現一個SuccessTile，從而分離出完美匹配；否則，組裝體將在下一步升溫過程中溶解.T中所有Tile的S和N相互結合，形成種子配置的第0列，即種子配置的結果序列檢測部分.這里稱結果序列檢測部分的每個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.只有滿足結合域為bdE(S0(xs-i,ys))=-,bdS(S0(xs-i,ys))=κi的Tilet,t∈U1,才能穩定地結合到S0上.在位置(xs-6,ys)∈Q1,bdW(S0(xs-5,ys))=-,bdN(S0(xs-6,ys-1))=r，U1中只有結合域bdS(t)=r,bdE(t)=r的EndTile滿足條件.EndTile結合到配置上形成新的配置S1.Step1完成后，所產生的組裝體如圖4(a)所示.

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

在此過程中，aTile一旦在結果序列中掃描到自身，將不會繼續掃描，而是將信號r繼續向左傳遞.在位置(xs-6,ys+1)上，因為bdW(S1(xs-5,ys+1))=r，bdN(S1(xs-6,ys))=r，故在t∈U2中，只有滿足結合域為bdS(t)=r和bdE(t)=r的LTile才能穩定地結合到配置上，形成配置S2,如圖4(b)所示.

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

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

記ti j∈Ui是能夠在第i步中在位置(xs-j,ys-i)∈Qj處結合到配置Si上并能穩定存在的Tile，Δ=Σd∈Dg(bd(t),bdd-1(A(d(x,y))))≥τ是tTile能夠穩定存在于配置上的條件.具體的自組裝算法記為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 計算結果

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

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

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

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

3 算法分析

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

定理1. 完美匹配自組裝系統Spm=〈Tpm,gpm,τpm〉計算終止時返回的自組裝結構是一個完美匹配.

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

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

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

證畢.

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

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

證畢.

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

證畢.

4 結 論

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

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

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

利用DNA自組裝進行計算是一種新的計算理念，通過設計具有不同功能的DNA Tile，進而形成代表問題的解結構，從理論上展現了自組裝模型應用于復雜問題的計算.

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

(許進, 保錚. 神經網絡與圖論[J]. 中國科學: 技術科學, 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)

(劉洋. 量子計算機中的數據庫處理[D]. 北京: 清華大學, 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計算模型的研究及應用[D]. 武漢: 華中科技大學, 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]. 武漢: 華中科技大學, 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)

(唐敏, 關鍵, 鄧國強, 等. 一種求解二部圖最大匹配問題新算法及其應用[J]. 計算機系統應用, 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)

(印桂生, 崔曉暉, 董紅斌, 等. 量子協同的二分圖最大權完美匹配求解方法[J]. 計算機研究與發展, 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)

(高琳, 馬潤年, 許進. 基于質粒DNA匹配問題的分子算法[J]. 生物化學與生物物理進展, 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]. 武漢: 華中科技大學, 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)

(周旭, 李肯利, 樂光學, 等. 一種最大匹配問題DNA計算算法[J]. 計算機研究與發展, 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].計算機輔助設計與圖形學學報, 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

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

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