王劍波

(湖南人文科技學院 計算機科學技術(shù)系，湖南 婁底 417001)

基于質(zhì)粒模型的DNA計算機算法求解背包問題

王劍波

(湖南人文科技學院 計算機科學技術(shù)系，湖南 婁底 417001)

DNA計算機在求解大型科學問題中DNA鏈數(shù)呈純指數(shù)增長的瓶頸亟待解決。本文提出一種將分治策略應用求解背包問題的新的基于質(zhì)粒DNA計算機算法，使DNA鏈數(shù)可達到亞指數(shù)的O(1.414n)，其中n為背包問題的維數(shù)。與已有文獻結(jié)論進行的對比分析表明: 本算法將窮舉算法中所需的DNA鏈數(shù)從O(2n)減少至O(1.414n)，利用本算法將可破解的背包公鑰的維數(shù)在試管級水平上從60提高到120。

DNA計算機；質(zhì)粒模型；背包問題

1 DNA計算機求解NP完全問題

到目前為止，一個測試試管已可產(chǎn)生1018個DNA鏈，它可使1018位數(shù)據(jù)以數(shù)據(jù)并行的方式并行運行。因此，DNA計算機可提供相當于1018個處理單元的并行性和O(1018)的存儲空間。即DNA計算的本質(zhì)是將傳統(tǒng)計算機求解NP完全問題的時間代價轉(zhuǎn)換為DNA計算的空間即生物分子數(shù)目代價，因此，在基于窮舉的DNA計算機算法中，純指數(shù)階(O(2n))的時間轉(zhuǎn)化成了純指數(shù)量級的DNA鏈數(shù)，這也是目前求解難解問題的DNA計算機算法中的DNA鏈數(shù)為(O(2n))的原因。

就DNA計算而言，用DNA計算機求解NP完全的圖和組合優(yōu)化問題的的一個關(guān)鍵問題是DNA計算模型的選擇。雖然DNA計算模型一直在不斷的發(fā)展，從最初的剪接系統(tǒng)模型發(fā)展到目前常用的剪接系統(tǒng)模型、粘貼模型、表面計算模型、基于質(zhì)粒的DNA計算模型和基于圖的自組模型以及最近的禁止-強迫模型(forbidding-enforcing，fe)等，這些模型在生物操作所出現(xiàn)的偽解等方面較最初的模型均有較大改進。但現(xiàn)有的這些模型均存在一定不足: 基于粘貼的DNA計算模型能實現(xiàn)二進制的各種算術(shù)運算，理論上可解決許多NP完全問題，而且在運算過程中不需要DNA鏈的延伸和酶的作用，但算法必須通過雜交、退火和探針的設計來完成。由于雜交及退火的不完整性，會導致大量的偽解出現(xiàn)。表面計算可解決一些如最佳匹配問題等NP完全問題，但基于該模型的算法中仍然存在雜交和酶切等生物操作，因而依然無法避免大量偽解的產(chǎn)生?；谫|(zhì)粒的DNA計算模型成功解決了最大權(quán)團等NP完全問題，該模型雖沒有復雜的自身退火單鏈DNA 或PCR擴增步驟造成的麻煩，可確保計算過程免受其它酶的干擾，從而保證計算的準確性和穩(wěn)定性，但受其自身特性的影響，該模型實現(xiàn)算術(shù)減法、乘法和除法操作目前均有難度?；趫D的自組模型和fe模型盡管可成功求解小規(guī)模SAT問題，但滿足條件的圖的建造有時卻相當困難。

為了提高DNA計算機算法可擴展性，擴大使用DNA計算機算法解決難解問題的規(guī)模，1996年，Eric Bach等[1]首次提出了一種將Adleman和Liptom的DNA計算模型相結(jié)合的改進DNA計算模型，在此基礎上將求解3著色問題和獨立集問題傳統(tǒng)計算機算法的基本思想應用于該模型，在理論上實現(xiàn)了DNA鏈數(shù)為O(n1.89n)的求解3色問題的DNA算法，和鏈數(shù)為O(1.67n)的求解獨立集問題的DNA計算機算法。但是，由于使用經(jīng)典Adleman和Liptom計算模型，該模型中雜交、退火和探針的設計使得求解過程中錯解和偽解率過高，理論上，生物操作數(shù)也明顯復雜得多，因而難于走向?qū)嵺`。1997年，F(xiàn)u等[2]應用傳統(tǒng)串行算法設計技術(shù)，將所求問題先通過計算機做一定變化，以改變問題的初始解空間，達到降低DNA分子數(shù)的目的，并相應提出了幾種DNA計算機算法: 鏈數(shù)O(1.497n)求解3-SAT問題算法、鏈數(shù)O(1.345n)三著色問題算法、O(1.229n)的獨立集問題算法，而且，這些算法的時間或操作復雜性也均為多項式量級。但是，考慮到DNA分子計算的特性，縮小的初始空間在用DNA分子初始化時很難構(gòu)造，使其可行性大大降低，而且，使用計算機來作DNA計算的部分計算工作的方式也與DNA計算機向全自動化、無外界干預的發(fā)展趨勢不符[3]。

李源等[4]于2004年首次最大團問題的DNA計算中引入了進化算法，提出一種求解最大團問題的DNA計算機概率算法，該算法可在不顯著增加DNA計算時間前提下，大大減少直接窮舉方法試管中的DNA分子數(shù)目，對于具有頂點數(shù)為30左右的團的問題，該算法相當成功，因為它可以高概率找到問題的解，而且所需迭代的代數(shù)也不大，但對頂點數(shù)更多和連同度較大的最大團問題，該算法則很難以高概率求得問題的解[4]。

采用將電子計算機與DNA計算機相結(jié)合的方式，和在DNA算法設計中引入進化思想等，但這些方法的成功只限于小規(guī)模的局部個例，DNA計算機算法的低可擴展性問題仍然普遍存在。

本文采用傳統(tǒng)的算法設計策略。將分治策略引入背包問題的DNA計算中，提出一種新的背包問題DNA質(zhì)粒模型算法。在保持算法的DNA分子操作的計算時間(或操作次數(shù))不變的條件下，本算法求解n維背包問題的DNA鏈數(shù)降低至達到了亞指數(shù)的O(1.414n)。

2 質(zhì)粒模型

質(zhì)粒是細菌細胞內(nèi)一種自我復制的環(huán)狀雙鏈DNA分子，用于DNA重組技術(shù)的質(zhì)粒大多是經(jīng)過人工改造的，它通常具有復制子、克隆位點、選擇標志等特征。

設P是一個質(zhì)粒，s1，s2，… ，sk是P的K個相互不重疊的子段，k是正整數(shù)。對于每個i，核苷酸序列si不能出現(xiàn)在質(zhì)粒P的其余位置上，并稱si是質(zhì)粒P的“位置”。每次計算都開始于盛水的緩沖器或試管中含有大量的具有相同的k個“位置”的質(zhì)粒。在質(zhì)粒在計算過程中不斷地修改，一直到結(jié)果的讀取。質(zhì)粒的修改只在所謂的“位置”處進行，主要的方法是切割和粘貼。在計算過程中，每個核苷酸序列si1對應于一個計算的問題，可以通過一個實例更清楚地說明問題。假設用相應的限制性內(nèi)切酶剪切了S1和S4位置的核苷酸片斷，將每個操作后的外源DNA 序列分別用后面對應的數(shù)字序列表示，可以推斷，步操作之后我們能夠得到n階完全序列(圖1)。同時，由于每個核苷酸片斷長度不等，外源DNA 長度也不盡相同，則插入的外源DNA相應地轉(zhuǎn)化為一個帶有權(quán)值的有權(quán)路徑問題。不同的剪切和粘貼之后，質(zhì)粒DNA的總長度必然地發(fā)生變化。根據(jù)這一結(jié)果，可以運用質(zhì)粒DNA計算解決許多實際問題。

圖1 質(zhì)粒DNA的剪切計算模型

要么在質(zhì)粒上要么不在質(zhì)粒上，我們用1表示在質(zhì)粒上，而用0表示不在質(zhì)粒上。在某種程度上，它相當于電子計算機的k比特的存儲器(圖2)。本文正是利用質(zhì)粒所具有的特征提出圖的最大權(quán)團的DNA算法，其基本的生物操作包括連接(Ligating)、放大(Amplifying/ Copying) 、 酶切(cutting)、分離(Separation)、提取(Extracting)、檢測(Dectecting)。

圖2 質(zhì)粒結(jié)構(gòu)圖

3 背包問題的DNA計算機算法

Horowitz和Sahni在1974年提出了著名的二表算法[6]，該算法是至今為止被認為最有效的求解最大團問題等背包類NP完全問題的算法之一。受二表算法設計原理啟示，將分治策略引入到DNA 分子算法設計中。

本算法的核心為:利用分治策略，將背包分量集W={w1,w2,…wn}平均分成兩部分W1和W2，分別求出兩部分的全部各O(1.414n)個子集和，使用減法操作對背包容量M與其中一個子集W1的所有子集和做減法運算，即將二表算法中二表求和后與數(shù)M的比較以判斷是否有解轉(zhuǎn)換成先求M與一個子集所有子集和的差，然后將之與另一部分的子集和作比較以判斷問題是否有解，這種方法不僅可克服排序和解搜索的DNA操作只能串行的局限性，而且還將降低DNA操作的難度。另外，由于本算法僅需保存1.414n個的DNA鏈，而非窮舉法中數(shù)目為2n的所有子集和組合，因此，，算法中的DNA分子鏈數(shù)在不明顯提高DNA操作時間或次數(shù)的條件下由文獻[5]中的2n減少至2×1.414n。

DNA 計算在解決問題時主要可分為三個階段: (1) 對問題進行適當?shù)木幋a，也就是將要求解的問題映射到DNA 鏈上；(2) 生物實驗，依照算法模型的步驟完成各種實驗操作，生成問題的解；(3) 解的提取。為了求解背包問題，首先假設所有的背包分量wi和M的最大公約數(shù)為m，則wi=mli。M=mpj，本算法用DNA分子操作的基本實現(xiàn)過程根據(jù)其處理特性描述如下:

算法：背包問題的DNA計算機算法(the algorithm frame of DNA computer for knapsack problem)

首先將集合W= (w1,w2, ….,wn)按升序排列，并將其分成兩個元素個數(shù)相等的子集W1和W2。W1取按升序排列好后的W中的前n/2個元素，而W2取按升序排列好后的W的后n/2個元素。用W1,i表示W(wǎng)1的第i個元素，W2,i表示W(wǎng)2的第i個元素。

Step 1 輸入，在實驗杯T0中，分別對每個W1,i、W2,i-W1,i及M分量的值進行編碼。

對每個W1,i、W2,i-W1,i及M分量的值編碼：將所有W1,1,W1,2, …,W1,n/2及所有M分量1 , 2 , …依次編碼在一條DNA雙鏈上，W1的背包分量i都用20libp的核苷酸片段編碼，并且仍用i表示該片段；每個背包分量的兩端都有相同的特殊酶切位點的限制性內(nèi)切酶。不同的相鄰背包分量之間都有兩種不同的內(nèi)切酶，這兩種酶之間也可夾一些寡聚核苷酸片段；W2,i-W1,i用20libp的核苷酸片段編碼，并且仍用i表示該片段；M分量編碼在背包分量之后，用20pjbp的核苷酸片段編碼，并且用j表示該片段；編碼方式同W1,i。

Step 2 把T0產(chǎn)生的DNA片段插入到開口的質(zhì)粒中，在形成閉環(huán)狀質(zhì)粒后放入到大腸桿菌中擴增該質(zhì)粒。

Step 3 分別對背包分量集W1和W2把初始化。

將T0中的質(zhì)粒分成兩個等量的杯子T1和T2。

在杯子T1中分別加入切割W2,i-W1,i的內(nèi)切酶，再把切割下來的小片段和質(zhì)粒分離出來，并使質(zhì)粒重新環(huán)化后合成一個杯子。此時，質(zhì)粒上的DNA片斷后n/2段被切割，則質(zhì)粒上的DNA片斷前n/2段，分別表示背包分量集W1的n/2個分量值。

在杯子T2中每個W1,i和W2,i-W1,i長度之和唯一表示背包分量集W2中第i個背包分量值。

Step 4 生成W1中所有子集，并計算M與背包分量集W1中所有子集和的差。

將T1中的質(zhì)粒分成兩個等量的杯子T3和T4。

在杯子T3中加入切割W1,i的內(nèi)切酶，再把切割下來的小片段和質(zhì)粒分離出來，并使質(zhì)粒重新環(huán)化后合成一個杯子。之后放入入大腸桿菌擴增該質(zhì)粒。將擴增后的T3分成相同容量的兩個杯子T5和T6。

在杯子T4中放入切割W1,i的內(nèi)切酶，再把切割下來的小片段和質(zhì)粒分離，并使質(zhì)粒重新環(huán)化合成一個杯子。然后，逐步加入切割與W1,i等值的M分量的內(nèi)切酶，并使質(zhì)粒重新環(huán)化后合成一個杯子。轉(zhuǎn)入大腸桿菌擴增這樣的質(zhì)粒。將擴增后的T4分成兩個等量的杯子T7和T8。

此時，將T5和T7合并到T3中，T6和T8合并到T4中。當所有n/2個背包分量都完成上述操作后，再將T3和T4合并到T1中。

Step 5 生成W2中所有子集，并計算背包分量集W2中所有子集之和。

在T2中分別加入切割所有M分量的內(nèi)切酶，再把切割下來的小片段和質(zhì)粒分離出來，并使質(zhì)粒重新環(huán)化后再合成一個杯子；

Step 6 用凝膠電泳技術(shù)找出鏈長相等的質(zhì)粒；

Step 7 確定鏈長相等的質(zhì)粒所含的背包分量的并集即是背包問題的解；

Step 8 輸出結(jié)果。

4 小結(jié)

DNA計算機是解決背包問題等NP完全問題的方法之一，但目前DNA計算機算法多基于窮舉法，這種方法使得DNA計算機具有純指數(shù)量級的DNA鏈數(shù)而受到極大的限制。進化算法等現(xiàn)代算法是解決該問題的有效方法之一，但該方法尚難以高概率找出對于變量數(shù)較多的NP完全問題的解。本文提出一種求解背包問題的DNA計算機算法，將DNA分子計算中使用分治策略，應用質(zhì)粒模型，可以令DNA分子鏈數(shù)從文獻[2]的O(2n)減少到亞指數(shù)O(1.414n)，從而求解背包問題DNA分子計算的維數(shù)從60擴大到120。

[1]BRAICH R S, CHELYAPOV N, JOHNSON C, et al. Solution of a 20-variable 3-SAT problem on a DNA computer[J]. Science, 2002, 296(19):499-502.

[2]FU B. Volume bounded molecular computation[D]. New Haven: Department of Computer Science, Yale University, 1997, 55-68.

[3]LAIH C S, LEE J Y, HARN L, et al. Linearly shift knapsack public-key cryptosystem[J]. IEEE Journal on Selected Areas Communications, 1989, 7(4): 534-539.

[4]LIPTON R J. DNA solution of hard computational problems[J]. Science, 1995, 268(28): 542-545.

[5]LI K L, LI R F, LI Q H. Optimal parallel algorithm for the knapsack problem without memory conflicts[J]. Journal of Computer Science and Technology, 2004, 19(6): 760-768

[6]HOROWITZ E, SAHNI S. Computing partitions with applications to the knapsack problem[J]. Journal of ACM, 1974, 21(2): 277-292.

(責任編校：光明)

KnapsackProblemaboutDNAComputerSolvingBasedonPlasmidModel

WANGJian-bo

(Department of Computer Science, Hunan Institute of Humanities，Science and Techonology, Loudi,417001,China)

It’s an urgent question to solve that DNA chain presents pure index increasing while DNA computer solves large scale scientific problems. On the application of divide-and-conquer strategy into DNA numerator algorithm of knapsack problem, the paper introduces a new DNA computerized algorithm based on Plasmids model to solve knapsack problem. The algorithm DNA linkage numbers can reach subexponential O(1.414n) , whilenisdimensionality of knapsack problem.Through comparative analysis between new DNA computeri algorithm and document conclusion, the Algorithm decreases DNA linkage numbers in exhaust algorithm from O(2n) to O(1.414n). Hence, this algorithm proves to be a certain superiority on the tube's level increasing dimensionality of penetrable knapsack public key from 60 to 120.

DNA computer; plasmids model; knapsack problem

2010-07-15.

湖南人文科技學院青年基金項目(2008QN018).

王劍波(1978——)，男，湖南新邵人，湖南人文科技學院講師，碩士，研究方向：并行計算、電子商務。

TP301.6

A

1673-0712(2010)04-0077-03