周 旭,周炎濤,李肯立,潘 果

(1.湖南大學(xué) 信息科學(xué)與工程學(xué)院, 湖南 長沙 410082；2.嘉興學(xué)院 數(shù)理與信息工程學(xué)院,浙江 嘉興 314001；3.湖南大學(xué) 電氣與信息工程學(xué)院,湖南 長沙 410082)

最大匹配問題Tile自組裝模型

周 旭1,2,周炎濤1,3?,李肯立1,潘 果1

(1.湖南大學(xué) 信息科學(xué)與工程學(xué)院, 湖南 長沙 410082；2.嘉興學(xué)院 數(shù)理與信息工程學(xué)院,浙江 嘉興 314001；3.湖南大學(xué) 電氣與信息工程學(xué)院,湖南 長沙 410082)

Tile自組裝模型憑借其自組裝、可編程等特性在解決NP問題方面具有巨大優(yōu)勢.文中提出了一種求解最大匹配問題的Tile自組裝新模型,該模型主要由初始配置子系統(tǒng)、選擇子系統(tǒng)及檢測子系統(tǒng)3大部分構(gòu)成.新模型中首先設(shè)計Tile分子存儲問題信息,其次通過Tile分子自組裝操作生成最大匹配問題解空間,最后通過Tile檢測分子篩選得到最大匹配問題的解.對模型從所需Tile分子種類、計算時間和計算空間3個方面進行性能分析,并通過實驗?zāi)M論證了模型的有效性和正確性.

DNA計算; Tile自組裝模型; 最大匹配問題; NP完全問題; 并行計算

1994年,Adleman提出了DNA計算模型[1].此后,DNA計算以其具有的海量存儲能力,巨大并行性及低能耗等特點,得到科學(xué)界的廣泛關(guān)注.隨著DNA計算的發(fā)展, 眾多DNA計算模型被提出,主要有：粘貼DNA計算模型[2],表面計算模型[3],自組裝模型[4]等.以上模型中,自組裝模型以其自治性及納米特性等優(yōu)勢,成為當(dāng)前最具應(yīng)用潛力的DNA計算模型之一[5].

隨著生物技術(shù)的不斷進步,Tile自組裝模型自提出以來,得到了飛速的發(fā)展.Winfree基于Wang的Tile理論提出Tile自組裝模型[4];Zhao等人提出了基于線性自組裝的DNA加法算法[6]; Brun提出了基于Tile自組裝的子集和問題算法[7];張勛才等人提出了一種基于自組裝DNA計算的NTRU密碼系統(tǒng)破譯方案[8];方習(xí)文等人基于線性自組裝模型提出了DNA減法模運算算法[9];周炎濤等人基于DNA自組裝模型提出了一種求解最大團問題的算法[10].

圖的最大匹配的DNA計算算法已有相當(dāng)研究[11-12].然而文獻[11]中提出的算法基于表面模型、文獻[12]中提出算法基于粘貼模型，此兩種模型均很難克服實驗操作難度較大，需要大量的人工干預(yù)的缺點.此外,從公開發(fā)表的刊物看,關(guān)于最大匹配問題Tile自組裝模型的研究還比較少.為此,本文對最大匹配問題Tile自組裝模型進行了較深入的探索.主要工作如下:

1) 提出了一種最大匹配問題Tile自組裝模型,該模型主要由初始配置子系統(tǒng)、選擇子系統(tǒng)及檢測子系統(tǒng)3大部分構(gòu)成.

2)從所需Tile分子種類、計算時間和計算空間3個方面進行性能分析，并通過對算法進行實例模擬,進一步驗證模型及算法的正確性和有效性.

1 Tile自組裝模型

1.1 Tile分子的結(jié)構(gòu)

基于Wang的Tile理論,1998年Winfree提出了一種Tile自組裝數(shù)學(xué)模型又稱為Tile自組裝模型[4].Tile自組裝模型中的Tile分子可以通過不同的DNA編碼來構(gòu)建.如圖1所示,每個Tile分子可以抽象成為帶有標(biāo)簽的四邊形,每個標(biāo)簽可以識別不同的粘性末端.若兩個不同的Tile分子的兩個粘性末端互補,兩個互補的粘性末端通過堿基互補配對連接進行Tile分子的自組裝.本文將Tile分子定義為5元組.Tile分子分別通過North, South, West, East 4個

粘性末端存儲信息,其中Value用來表示Tile分子代表的值(如圖1).

圖1 DNA Tile分子及其抽象模型

1.2 相關(guān)生物操作

本文模型在自組裝模型中的基本生物操作如退火,連接,熒光標(biāo)記及凝膠電泳操作的基礎(chǔ)上,引入了Adleman-Lipton模型中抽取,檢測,讀取等生物操作, 具體描述見文獻[12].

1.3 擴展的Tile自組裝模型的抽象描述

對傳統(tǒng)Tile自組裝模型進行擴展[4].擴展后的Tile自組裝模型定義為5元組, 其中g(shù),t及Configuratio定義見文獻[9],而TileSet及BioOperations定義如下：

1) TileSet, 表示自組裝模型中Tile分子的集合, Tile分子的4個粘性末端可以表示不同的數(shù)值或計算過程中用到的符號.其中Tile分子定義如下.

①符號Σ表示Tile分子所有粘性末端標(biāo)識的有限集合, null∈Σ.一個基本Tile分子可以用一個5元組<σValue,σNorth,σSouth,σWest,σEast>∈Σ5表示;

②Tile分子的位置用二維坐標(biāo)(x,y)表示.假設(shè)某一Tile分子的坐標(biāo)為(x,y),通過方向函數(shù)集Direction= {fNorth,fEast, fSouth, fWest}可以得到其相鄰4個Tile分子的坐標(biāo),如fNorth(x,y)= (x,y+1), fEast(x,y)=(x+1,y), fSouth(x,y)=(x,y-1), fWest(x,y)=(x-1,y). 當(dāng)位置(x,y)和(x′,y′)相鄰時,滿足條件d∈Direction,d(x,y)= (x′,y′).

2)BioOperations復(fù)制、退火、連接等生物操作[12].

2 最大匹配問題Tile自組裝模型

2.1 問題描述

無向圖G= (V,E)中具有頂點集V= {v1,v2,…,vn}, 邊集E= {e1,e2,…,em}, 對E的任一子集M, 如果M中任意兩條邊ek,ed在G中沒有公共的端點,則M為G的一個匹配.若G中沒有另外的M’使得|M’|>|M|,則稱M為G的最大匹配[12].圖2包含的最大匹配分別為M1={e1,e3,e6}和M2= {e2,e4,e6}.

圖2 具有6個頂點,6條邊的簡單無向圖G

2.2 最大匹配問題Tile自組裝模型

本文的最大匹配問題Tile自組裝模型主要分為初始配置子系統(tǒng), 選擇子系統(tǒng)和檢測子系統(tǒng)3個部分.

2.2.1 初始配置子系統(tǒng)

初始配置基本Tile分子抽象結(jié)構(gòu)如圖3所示. 生成大量如圖3所示的初始配置Tile分子后,將通過本節(jié)的初始配置子系統(tǒng)生成最大匹配問題的初始配置.

圖3 初始配置子系統(tǒng)中Tile分子抽象結(jié)構(gòu)

定理1 定義∑s={p,C, |, =},初始配置子系統(tǒng)SystemInitial= ,其中Tinitial表示基本Tile分子的集合,ginitial=1,τinitial=2,BioOperations表示所需的生物操作.SystemInitial將生成最大匹配問題的初始配置.

證 初始配置系統(tǒng)SystemInitial中的基本Tile分子集合Tinitial={、<|, |,p, null>、、<|, null, null, =>、<|, null, = , null>和< null, |, =, null> }，其中1≤p≤m.初始配置子系統(tǒng)中通過將Tinitial集合中的Tile分子充分自組裝后將生成初始配置Cinitial, 其中Cinitial中存在一些位置(x,y)∈2,滿足如下約束：

1)?(x=0,y=0),Cinitial(x,y)= <|, null,=, null > ;

2)?(x=0, 1≤y≤n-1),Cinitial(x,y)= <|, |,p, null>, 其中1≤p≤m;

3)?(x=0,y=n),Cinitial(x,y)= < null, |,=, null > ;

4)?( -n+1≤x≤2,y=0),Cinitial(x,y)= ;

5)?(x=n,y=0),Cinitial(x,y)= < |, null, null,= > ;

6) 對于其他的位置(x,y) ∈2, (x,y)?Cinitial.

證畢.

2.2.2 選擇子系統(tǒng)

基于2.2.1節(jié)中初始配置，通過本節(jié)的選擇子系統(tǒng)基本Tile分子將生成最大匹配問題的初始解空間配置.選擇子系統(tǒng)所需的基本Tile分子如圖4所示.

圖4 選擇子系統(tǒng)中Tile分子抽象結(jié)構(gòu)

定理2 定義∑C={C,Cp0,Cp1,p},選擇子系統(tǒng)SystemChoose= ,其中Tchoose表示基本選擇子系統(tǒng)Tile分子的集合,gchoose=1,τchoose=2, BioOperations表示所需的生物操作.SystemChoose將生成最大匹配問題的所有初始解空間配置,而在某一初始解空間配置基礎(chǔ)上能夠產(chǎn)生唯一的最終配置.

證 選擇子系統(tǒng)SystemChoose中的基本Tile分子集合Tchoose={, 、< null,C, = ,=> }其中1≤p≤m. SystemChoose中通過將Tchoose中的選擇分子自組裝到初始配置Cinitial上生成初始解空間配置CInitialResult.CInitialResult中存在一些位置(x,y)∈2,滿足如下約束：

1) ?(x=0,1≤y≤n-1),CInitialResult(x,y)= 其中0．當(dāng)邊ep被選中時,i=1,CInitialResult(x,y)= , 其中1≤p≤m;

2)?(x=0,y=n),CInitialResult(x,y)= ;

3) 對于其他的位置(x,y)∈2, (x,y)?CInitialResult.

2.2.3 檢測子系統(tǒng)

根據(jù)最大匹配問題的定義及Tile分子的基本生物特性,本節(jié)中設(shè)計了用于檢測的Tile分子類型(如圖5).

定理3 定義∑D={Cp0,Cp1,Cq0,Cq0,p, |, =},檢測子系統(tǒng)SystemDetect=,其中Tdetect表示檢測子系統(tǒng)中基本Tile集合,gD=1,τD=2.針對初始解空間配置CInitialResult,通過Tdetect中的檢測分子能夠檢測出最大匹配問題的合法的DNA Tile組裝體.

證 如圖5,檢測子系統(tǒng)SystemDetect中檢測分子集合Tdetect={,,,,,,,,< null,Cp1, =, =>,< null,Cp0, =, =>,< |, |, null,Cq1>,< |, |, null,Cp0>,< |, null, null, =>,}其中1≤p,q≤m且p≠q.基于初始解空間配置CInitialResult,SystemDetect中通過將檢測分子自組裝到初始配置CInitialResult上生成最終配置Cfinal.Cfinal中存在一些位置(x,y)∈2,滿足如下約束：

1) ?(-m-1≤x≤-2, 1≤y≤m),Cfinal(x,y)=,,,,,,,;

2) ?(-2≤x≤-m-1,y=m+1),Cfinal(x,y)= 或;

3) ?(x=-m-2,1≤y≤m-1),Cfinal(x,y)= < |, |, null,Cq1> 或< |, |, null,Cq0>;

4) ?(x=-m-2,y=0),Cfinal(x,y)= < |, null, null, =>;

5) ?(x=-m-2,y=m+1),Cfinal(x,y) =;

6) 其他的位置(x,y) ∈2,Cfinal(x,y)=empty.

從以上分析可以發(fā)現(xiàn)?t∈Tdetect,(bdsouth(t),bdwest(t)) 是唯一的,因此檢測子系統(tǒng)SystemDetect中針對某一初始解空間配置CInitialResult將生成唯一的的最終配置Cfinal.

證畢.

圖5 檢測子系統(tǒng)中的基本Tile分子

2.3 性能分析

本節(jié)將從所需Tile分子種類、計算時間及計算空間3個方面分析算法的性能.

引理1 Tile分子種類,計算時間和計算空間： 本文提出的最大匹配問題Tile自組裝高效模型中,需要的Tile分子種類為O(m2), 計算時間為O(m),計算空間為O(m2).

證 本文模型主要由初始配置子系統(tǒng)、選擇子系統(tǒng)及檢測系統(tǒng)3個部分組成.其中初始配置子系統(tǒng)中需要Tile分子種類為2m+4; 選擇子系統(tǒng)中所需的Tile分子種類為2m+1;檢測系統(tǒng)中所需的Tile分子種類數(shù)為共為8m2-2m+2.綜上分析可知本模型中所需Tile分子種類數(shù)為O(m2)；其次計算時間即自組裝體的深度,本文模型中自組裝體的深度為m+2,因而計算時間復(fù)雜度為O(m)；最后空間復(fù)雜度即Tile自組裝體的面積,本文模型中自組裝體的最大面積為(m+2)×(m+2),因而計算空間復(fù)雜度為O(m2).

證畢.

2.4 實驗?zāi)M

為了驗證算法的正確性,借鑒文獻[7]中的實驗方法.以圖G為最大匹配問題的實例.

2.4.1 Tile分子編碼

以下將針對本文模型中的初始配置子系統(tǒng)，選擇子系統(tǒng)及檢測子系統(tǒng)3個部分,分別設(shè)計基本Tile分子：

1) 初始配置子系統(tǒng)中基本Tile分子有以下兩類.① 針對每條邊設(shè)計兩類Tile分子：< 1, null, =, =>,< |, |, 1, null >,< 2, null, =, =>,< |, |, 2, null >,< 3, null, =, =>,< |, |, 3, null >,< 4, null, =, =>,< |, |, 4, null >,< 5, null, =, =>,< |, |, 5, null >,< 6, null, =, =>,< |, |, 6, null >; ②為了隨后隨機生成解空間，設(shè)計了Tile分子；③邊界Tile分子<|, null, null , =>，<|, null, = , null>和< null, |, = , null>.

2)選擇子系統(tǒng)中基本Tile分子有, ,,,,,,,,,,,< null,C, =, =>.

3) 檢測子系統(tǒng)中基本Tile分子有檢測分子, 信息傳遞分子及輔助檢測分子3類.

①檢測子系統(tǒng)中設(shè)計了如下檢測分子用于傳遞邊的信息，實現(xiàn)將初始配置中底端的邊信息進行傳遞的Tile分子,其中p∈{1,2,3,4,5,6}; 主要用于輔助頂點信息的傳遞Tile分子,, ,其中p,q∈{1,2,3,4,5,6}且p≠q.

②檢測系統(tǒng)中根據(jù)兩條邊是否具有相同頂點,設(shè)計檢測分子.若被檢測的兩條邊同時存在于初始配置中時,若邊不具有相同的頂點,此時設(shè)計的檢測分子有,,,,,,,,,,,,,,,;被檢測的兩條邊中僅存在一條邊存在于某一匹配方案中時,檢測分子有, ,其中p,q∈{1,2,3,4,5,6}且p≠q;當(dāng)前被檢測的兩條邊均不存在于最大匹配中時,檢測分子,其中p,q∈{1,2,3,4,5,6}且p≠q.

③一種邊界分子主要用于輔助檢測的同時輸出結(jié)果.其中Tile分子有< null,C10, =, =>,< null,C11, =, =>,< null,C20, =, =>,< null,C21, =, =>,< null,C30, =, =>,< null,C31, =, =>,< null,C40, =, =>,< null,C41, =, =>,< null,C50, =, =>,< null,C51, =, =>,< null,C60, =, =>,< null,C61, =, =>,< |,|, null,C11>, < |,|, null,C10>,< |,|, null,C21>, < |,|, null,C20>,< |,|, null,C31>, < |,|, null,C30>,< |,|, null,C41>, < |,|, null,C40>,< |,|, null,C51>, < |,|, null,C50>,< |,|, null,C61>, < |,|, null,C60>, < |,null, null,=> 和.

2.4.2 求解過程

本文模型中的算法步驟可以分為Tile分子生成階段、初始配置生成階段、選擇階段、檢測階段和解的獲取5個部分,具體求解過程如下:

1) 準(zhǔn)備階段.執(zhí)行預(yù)處理算法,生成所需的基本Tile分子,分別存于試管Ttileinitial,Ttilechoose,Ttiledetect.

2) 初始配置生成階段.試管Ttileinitial,通過Anneal()及Ligation()操作, Tile分子充分自組裝得到初始配置(見圖6).

3) 初始解空間生成階段.合并試管Ttileinitial,Ttilechoose中大量Tile分子于試管Ttilechoose,通過Anneal()及Ligation()操作,Ttilechoose中的Tile分子充分自組裝后得到初始解空間配置.如圖7所示,分別展示了子圖{e1,e3,e6}及{e1,e2,e6}對應(yīng)的初始解空間配置.

4) 檢測階段.將存儲檢測Tile分子的試管Ttiledetect,存儲初始解空間配置的試管Ttilechoose中的Tile分子及Tile自組裝體進行合并后得到新的試管Ttiledetect.通過Anneal()及Ligation()操作,Ttiledetect中的Tile分子及初始配置充分地自組裝得到最終配置.其中子圖{e1,e3,e6}及{e1,e2,e6}對應(yīng)的最終配置如圖8所示.

圖6 初始配置子系統(tǒng)生成的初始配置

5) 解的獲取階段：首先通過Extract()操作,抽取出試管Ttiledetect中含有tileSucc=的最終配置到試管TMatch中.利用Gel-electrophoresis()操作即凝膠電泳技術(shù)將試管TMatch中的最終配置按照長度進行分離.并通過Extract_ maxLength()操作,得到試管TMatch中最長的DNA Tile自組裝體并存儲于試管TmaxMatch中,Detect()操作檢測試管TmaxMatch中是否含有DNA Tile自組裝體,如果返回 ‘yes’,Read()操作讀取試管TmaxMatch中的DNA Tile自組裝體存儲的信息,得到圖G的最大匹配問題的最終解即{e1,e3,e6},{e2,e4,e6}.

3 結(jié) 論

隨著生物技術(shù)的進步， DNA計算中的Tile自組裝模型憑借其自組裝,可編程等特性而得到廣泛關(guān)注.然而, 據(jù)我們所知，現(xiàn)今公開發(fā)表的刊物上還未有關(guān)于最大匹配問題的DNA Tile自組裝模型的研究.為此,本文首先提出了一種最大匹配問題的Tile自組裝有效模型,模型主要分為初始配置子系統(tǒng)，選擇子系統(tǒng)及檢測子系統(tǒng)3大部分；其次基于提出的模型，設(shè)計了相關(guān)算法，并分析了算法的性能，通過算法模擬證明算法的正確性及有效性.

圖7 選擇子系統(tǒng)生成的子圖{e1,e3,e6}，{e1,e2,e6}解空間配置實例圖

圖8 檢測子系統(tǒng)生成的子圖{e1,e3,e6},{e1,e2,e6}的最終配置實例圖

[1] ADLEMAN L M. Molecular computation of solutions to combinatorial problems [J]. Science, 1994, 266(11): 1021- 1024.

[2] CHANG W L. Fast parallel DNA-based algorithm for molecular computation: Quadratic congruence and factoring integers [J]. IEEE Transaction on Nanobioscience,2012, 11(1): 62-69.

[3] LI D F, LI X R, HUANG H T,etal. Scalability of the surface-based DNA algorithm for 3-SAT [J]. BioSystems, 2006, 85(2): 95-98.

[4] WINFREE E. Algorithmic self-assembly of DNA [D]. Pasadena: California Institute of Technology, 1998.

[5] 楊靜, 張成. DNA自組裝技術(shù)的研究進展及難點[J]. 計算機學(xué)報, 2008, 31(12): 2138-2148.

YANG Jin, ZHANG Chen. Progress and difficulty in DNA self-assembly technology [J]. Chinese Journal of Computers, 2008, 31(12):2138-2148. (In Chinese)[6] ZHAO J, QIAN L L, LIU Q,etal. DNA addition using linear self-assembly[J]. Chinese Science Bulletin, 2007, 52(11): 1462-1467.

[7] BRUN Y. Solving NP-complete problems in the tile assembly model [J]. Theoretical Computer Scienee,2008, 395(l): 31- 46.

[8] 張勛才,?，?崔光照,等.基于自組裝DNA計算的NTRU密碼系統(tǒng)破譯方案[J].計算機學(xué)報,2008, 31(12):2129-2137.

ZHANG Xun-cai, NIU Yin, CUI Guang-zhao,etal. Breaking the NTRU public key cryptosystem using self-assembly of DNA tilings [J]. Chinese Journal of Computers, 2008, 31(12):2129-2137. (In Chinese)

[9] 方習(xí)文,來學(xué)嘉.基于線性自組裝的DNA減法模運算[J].科學(xué)通報, 2010,55(10):957-963.

FANG Xi-wen, LAI Xue-jia. DNA modular subtraction algorithm based on linear self-assembly[J]. Chinese Science Bull, 2010, 55(10): 957-963. (In Chinese)

[10]周炎濤, 李肯立,羅興,等.一種基于DNA自組裝模型求解最大團問題的算法[J]. 湖南大學(xué)學(xué)報:自然科學(xué)版, 2012, 39(9): 39-44.

ZHOU Yan-tao, LI Ken-li,LUO Xing,etal.An algorithm for solving maximum clique problem based on self-assembly model of DNA[J]. Journal of Hunan University:Natural Sciences,2012, 39(9): 39-44. (In Chinese)

[11]陳治平, 李小龍, 王雷，等. 最佳匹配問題的DNA表面計算模型[J].計算機研究與發(fā)展, 2005, 42(7):1241-1246．

CHEN Zhi-ping, LI Xiao-long, WANG Lei,etal. A surface-based DNA algorithm for the perfect matching problem[J]. Journal of Computer Research and Development, 2005, 42(7):1241-1246．(In Chinese)

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

ZHOU Xu, LI Ken-li, YUE Guang-xue,etal. A volume melecular solution for the maximum matching problem on DNA-Based computing[J].Journal of Computer Research and Development, 2011, 48(11): 2147-2154. (In Chinese)

Efficient Tile Assembly Model for Maximum Matching Problem

ZHOU Xu1,2, ZHOU Yan-tao1,3?, LI Ken-li1,PAN Guo1

(1. School of Information Science and Engineering, Hunan Univ, Changsha, Hunan 410082,China；2. College of Mathematics and Information Engineering, Jiaxing Univ, Jiaxing, Zhejiang 314001,China；3.College of Electrical and Information Engineering, Hunan Univ, Changsha, Hunan, 410082,China)

The characteristics of tile self-assembly model are nanoscale properties, self-assembly, programmable and so on, so it has a great advantage in solving NP problems. This paper proposed a new tile self-assembly model for maximum matching problem. The new model is composed of initial configuration subsystem, choosing subsystem and detecting subsystem. In the new model DNA tiles were designed to store the information. The solution space of maximum matching problem was generated through the assembly operation. Lastly, the answers were found out by the detecting tiles. The performance of the algorithm was also analyzed in terms of the assembly time, the computation space and the types of the tiles, and the algorithm was simulated to prove its effectiveness and correctness.

DNA computing; tile self-assembly model; maximum matching problem; NP-complete problem; parallel computing

1674-2974(2015)02-0114-07

2014-08-13

國家自然科學(xué)基金重點資助項目(61133005)，Major Research Project of National Natural Science Foundation of China(61133005); 國家自然科學(xué)基金資助項目(61173013, 61202109),National Natural Science Foundation of China(61173013,61202109); 湖南省杰出青年基金資助項目(12JJ1011) ; 浙江省教育廳科研計劃項目(Y201226110); 湖南省科技廳科技計劃項目(2013GK3082) ;湖南省教育廳資助項目(08D092)作者簡介：周 旭(1983-)，女，江蘇宿遷人，湖南大學(xué)博士研究生?通訊聯(lián)系人，E-mail: yantao_z@hnu.edu.cn

TP301.6

A