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

周旭等

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

關(guān)鍵詞：DNA計(jì)算； Tile自組裝模型； 最大匹配問題； NP完全問題； 并行計(jì)算

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A

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

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

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

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

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

1Tile自組裝模型

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

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

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

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

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

1.3擴(kuò)展的Tile自組裝模型的抽象描述

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

.

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

2.1問題描述

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)生成最大匹配問題的初始配置.

2.2.2選擇子系統(tǒng)

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

2.2.3檢測子系統(tǒng)

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

2.3性能分析

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

引理1Tile分子種類，計(jì)算時間和計(jì)算空間： 本文提出的最大匹配問題Tile自組裝高效模型中，需要的Tile分子種類為O（m2）， 計(jì)算時間為O（m），計(jì)算空間為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）；其次計(jì)算時間即自組裝體的深度，本文模型中自組裝體的深度為m+2，因而計(jì)算時間復(fù)雜度為O（m）；最后空間復(fù)雜度即Tile自組裝體的面積，本文模型中自組裝體的最大面積為（m+2）×（m+2），因而計(jì)算空間復(fù)雜度為O（m2）.

證畢.

2.4實(shí)驗(yàn)?zāi)M

為了驗(yàn)證算法的正確性，借鑒文獻(xiàn)[7]中的實(shí)驗(yàn)方法.以圖G為最大匹配問題的實(shí)例.

2.4.1Tile分子編碼

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

2.4.2求解過程

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

3結(jié)論

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

參考文獻(xiàn)

[1]ADLEMAN L M. Molecular computation of solutions to combinatorial problems [J]. Science， 1994， 266（11）： 1021- 1024.

[2]CHANG W L. Fast parallel DNAbased 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，et al. Scalability of the surfacebased DNA algorithm for 3SAT [J]. BioSystems， 2006， 85（2）： 95-98.

[4]WINFREE E. Algorithmic selfassembly of DNA [D]. Pasadena： California Institute of Technology， 1998.

[5]楊靜， 張成. DNA自組裝技術(shù)的研究進(jìn)展及難點(diǎn)[J]. 計(jì)算機(jī)學(xué)報， 2008， 31（12）： 2138-2148.

YANG Jin， ZHANG Chen. Progress and difficulty in DNA selfassembly technology [J]. Chinese Journal of Computers， 2008， 31（12）：2138-2148. （In Chinese）

[6]ZHAO J， QIAN L L， LIU Q， et al. DNA addition using linear selfassembly[J]. Chinese Science Bulletin， 2007， 52（11）： 1462-1467.

[7]BRUN Y. Solving NPcomplete problems in the tile assembly model [J]. Theoretical Computer Scienee，2008， 395（l）： 31- 46.

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

ZHANG Xuncai， NIU Yin， CUI Guangzhao， et al. Breaking the NTRU public key cryptosystem using selfassembly of DNA tilings [J]. Chinese Journal of Computers， 2008， 31（12）：2129-2137. （In Chinese）

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

FANG Xiwen， LAI Xuejia. DNA modular subtraction algorithm based on linear selfassembly[J]. Chinese Science Bull， 2010， 55（10）： 957-963. （In Chinese）

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

ZHOU Yantao， LI Kenli，LUO Xing， et al.An algorithm for solving maximum clique problem based on selfassembly model of DNA[J]. Journal of Hunan University：Natural Sciences，2012， 39（9）： 39-44. （In Chinese）

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

CHEN Zhiping， LI Xiaolong， WANG Lei， et al. A surfacebased 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ì)算算法[J].計(jì)算機(jī)研究與發(fā)展， 2011，48（11）：2147-2154.