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

王劍波

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

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

王劍波

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

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

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

1 DNA計(jì)算機(jī)求解NP完全問題

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

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

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

李源等[4]于2004年首次最大團(tuán)問題的DNA計(jì)算中引入了進(jìn)化算法，提出一種求解最大團(tuán)問題的DNA計(jì)算機(jī)概率算法，該算法可在不顯著增加DNA計(jì)算時(shí)間前提下，大大減少直接窮舉方法試管中的DNA分子數(shù)目，對(duì)于具有頂點(diǎn)數(shù)為30左右的團(tuán)的問題，該算法相當(dāng)成功，因?yàn)樗梢愿吒怕收业絾栴}的解，而且所需迭代的代數(shù)也不大，但對(duì)頂點(diǎn)數(shù)更多和連同度較大的最大團(tuán)問題，該算法則很難以高概率求得問題的解[4]。

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

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

2 質(zhì)粒模型

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

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

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

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

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

3 背包問題的DNA計(jì)算機(jī)算法

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

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

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

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

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

Step 1 輸入，在實(shí)驗(yàn)杯T0中，分別對(duì)每個(gè)W1,i、W2,i-W1,i及M分量的值進(jìn)行編碼。

對(duì)每個(gè)W1,i、W2,i-W1,i及M分量的值編碼：將所有W1,1,W1,2, …,W1,n/2及所有M分量1 , 2 , …依次編碼在一條DNA雙鏈上，W1的背包分量i都用20libp的核苷酸片段編碼，并且仍用i表示該片段；每個(gè)背包分量的兩端都有相同的特殊酶切位點(diǎn)的限制性內(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ì)粒后放入到大腸桿菌中擴(kuò)增該質(zhì)粒。

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

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

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

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

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

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

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

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

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

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

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

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

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

Step 8 輸出結(jié)果。

4 小結(jié)

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

(責(zé)任編校：光明)

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.

湖南人文科技學(xué)院青年基金項(xiàng)目(2008QN018).

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

TP301.6

A

1673-0712(2010)04-0077-03