基于分治的背包問(wèn)題DNA計(jì)算機(jī)算法

曾毅

摘要：在DNA計(jì)算機(jī)研究領(lǐng)域，將降低DNA計(jì)算機(jī)在大型難解問(wèn)題求解中問(wèn)題輸入純指數(shù)增長(zhǎng)的DNA鏈數(shù)問(wèn)題作為研究重要內(nèi)容，于背包問(wèn)題的DNA分子計(jì)算中引入分治策略，提出一種進(jìn)行背包問(wèn)題求解的DNA計(jì)算機(jī)算。重點(diǎn)對(duì)其算法組成及應(yīng)用進(jìn)行分析。通過(guò)模擬實(shí)驗(yàn)發(fā)現(xiàn)，新算法其能夠提高破解背包公鑰維數(shù)，解決背包問(wèn)題所需DNA鏈數(shù)增長(zhǎng)問(wèn)題，切實(shí)提高DNA計(jì)算機(jī)算法操作的準(zhǔn)確性。

關(guān)鍵詞：分治；背包問(wèn)題；DNA；計(jì)算機(jī)算法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）05-0213-03

1 基于分治的背包問(wèn)題DNA計(jì)算機(jī)算法提出背景

伴隨著分子生物技術(shù)發(fā)展，單個(gè)測(cè)試試管可產(chǎn)生1018個(gè)DNA鏈，1018個(gè)DNA分子鏈用數(shù)學(xué)方式表示即代表1018位數(shù)據(jù)。當(dāng)前，基本生物學(xué)支持同時(shí)進(jìn)行1018位數(shù)據(jù)處理。在大型難解問(wèn)題領(lǐng)域，生物計(jì)算其能夠提供并行性。早在1994年，Adleman在DNA分子生物反應(yīng)的基礎(chǔ)上進(jìn)行了有向Hamilton路徑問(wèn)題解決。在此之后，DNA計(jì)算機(jī)及DNA計(jì)算模型等研究獲得高度重視，Lipton通過(guò)DNA生物技術(shù)實(shí)現(xiàn)了NP完全問(wèn)題的可滿足性問(wèn)題解決。

NP完全問(wèn)題中的背包問(wèn)題其具體描述為：設(shè)定q個(gè)正整數(shù)集合W與正整數(shù)M并要求決定W、M二值的q元祖X參數(shù)能夠滿足公式[i=1qwixi=M]要求。背包問(wèn)題在數(shù)論研究與信息密碼學(xué)研究領(lǐng)域存在著重要作用及應(yīng)用價(jià)值。為解決背包問(wèn)題，有學(xué)者提出構(gòu)建粘貼模型DNA計(jì)算機(jī)算法，2004年，Chang等學(xué)者提出一種DNA計(jì)算機(jī)算法，其算法優(yōu)勢(shì)在于編碼錯(cuò)誤較少。

然而以上算法多屬于簡(jiǎn)單窮舉算法類型，如設(shè)定其方法解決背包密鑰維數(shù)為q，則其算法在解決背包問(wèn)題時(shí)所面臨的DNA鏈數(shù)量則為O（2q）。以當(dāng)前的生物技術(shù)水平而言，其在處理DNA濃度問(wèn)題上僅為微摩爾量級(jí)，采取以上DNA計(jì)算機(jī)算法在理論上能夠進(jìn)行背包密鑰破解的維數(shù)只為60。依據(jù)最新DNA算法，其能夠?qū)崿F(xiàn)背包密鑰破解維度結(jié)果為80。李源等在研究此問(wèn)題時(shí)在DNA計(jì)算中引入了進(jìn)步算法，提出DNA計(jì)算機(jī)概率算法，這種算法方式其在降低DNA分子數(shù)目上存在一定效果。

雖然DNA計(jì)算機(jī)算法與傳統(tǒng)計(jì)算機(jī)計(jì)算其在存儲(chǔ)及計(jì)算方式上存在差異，但從本質(zhì)上而言，DNA算法其屬于一種并行超級(jí)算法。在本文研究背包問(wèn)題DNA計(jì)算機(jī)算法過(guò)程中，引入分治策略，提出一種新型的建立于分治策略基礎(chǔ)之上的背包問(wèn)題DNA計(jì)算機(jī)算法。這種算法具體包括n位并行減法器與并行數(shù)據(jù)搜索器兩種關(guān)鍵子算。模擬計(jì)算結(jié)果表明，這種算法在進(jìn)行背包問(wèn)題DNA鏈數(shù)維數(shù)求解時(shí)達(dá)到了O（2q/2）。

2 Adleman-Lipton模型認(rèn)知

1995年，在Adleman研究的基礎(chǔ)上，Lipton在解決可滿足性問(wèn)題的過(guò)程中提出了一種NDA計(jì)算模型即Adleman-Lipton模型。在Adleman-Lipton模型條件下，一個(gè)試管可以視為由有限字母構(gòu)成的字母表{A ， C ， T， G }相互組合形成的串集合，具體DNA操作可以通過(guò)如下進(jìn)行描述：

第一，抽取。設(shè)定具體試管P與短DNA單鏈S，具體抽取操作為：+（P，S）、-（P，S）。其中+（P，S）代表P試管中含有S的所有集合作為子鏈的DNA分子鏈，-（P，S）則代表P試管中不存在S作為子鏈的DNA分子鏈。第二，合并。將試管設(shè)定為P1，P2，采取合并操作，具體公式表達(dá)為U（P1，P2） =P1UP2 ，其合并操作的具體含義為將P1及P2試管合并到同一根試管環(huán)境之中卻不改變其各個(gè)試管之中的任何DNA分子鏈。第三，檢測(cè)，設(shè)定試管為P，檢測(cè)設(shè)定條件如試管中至少存在1個(gè)DNA鏈，在檢測(cè)條件基礎(chǔ)上運(yùn)行，滿足條件則返回“yes”，不滿足條件則執(zhí)行“no”。第四，復(fù)制，設(shè)定試管為P，通過(guò)操作之后產(chǎn)生P的復(fù)制結(jié)果，即P1、P2，在復(fù)制之后P試管不存在任何分子鏈，為空。第五，添加。設(shè)定試管P，明確短DNA鏈為Z，通過(guò)添加操作方法在P試管中每個(gè)鏈的末尾位置增加鏈Z。第六，讀取。設(shè)定試管為P，通過(guò)讀取操作，能夠獲取試管P中任何一個(gè)NDA分子鏈信息。

3 基于分治的背包問(wèn)題DNA計(jì)算機(jī)算法分析

（1）基于分治法理念的背包問(wèn)題DNA計(jì)算機(jī)算法思想分析

Horowitz與Sahni在NP完全問(wèn)題算法研究過(guò)程中，引入了分治策略并提出了二表算法，這種算法在進(jìn)行SAT精確求解、最大團(tuán)問(wèn)題及集覆蓋問(wèn)題求解等背包類NP完全問(wèn)題解決中應(yīng)用十分廣泛。通過(guò)NDA分子方式進(jìn)行二表算法應(yīng)用發(fā)現(xiàn)，采取二表算法無(wú)法解決DNA算法中數(shù)目呈純指數(shù)增加的鏈數(shù)問(wèn)題，這是因?yàn)槎硭惴ㄖ械呐判騿?wèn)題及解搜索無(wú)法實(shí)現(xiàn)并行操作。在二表算法設(shè)計(jì)理念的基礎(chǔ)上，在DNA算法中引入分治策略，依據(jù)DNA分子操作特性進(jìn)行背包問(wèn)題解決。這種新型算法的核心思想為：通過(guò)分治策略方式將所有背包分量進(jìn)行部分劃分，將分量w1 ， w2 ，…wn劃分為兩部分，對(duì)劃分后部分所有的O（2q/2）子集進(jìn)行求和，設(shè)定背包容量為M，通過(guò)應(yīng)用減法方式將M與其中一個(gè)子集所包含的所有子集和進(jìn)行減法運(yùn)算，這種算法要求先獲取M，然后求解出一個(gè)子集中所包含的所有子集和，并計(jì)算兩者之間的差值，將其差值與另一部分子集和進(jìn)行對(duì)比，判斷是否有解。采取這種計(jì)算方式不僅解決了二表算法中存在的排序及解搜索DNA操作串行局限問(wèn)題，還能夠有效降低NDA操作的實(shí)際難度，這種算法方式其DNA鏈只需保存2q/2個(gè)，并非2q/所有子集和?；诜种蔚谋嘲鼏?wèn)題DNA計(jì)算機(jī)算法實(shí)現(xiàn)過(guò)程描述如下：

明確需要求解的背包問(wèn)題DNA計(jì)算機(jī)算法框架，其算法實(shí)現(xiàn)步驟為：第一，通過(guò)DNA鏈進(jìn)行背包分量集合W1、W2的所有子集在試管T01與T02中表示，其中W1={w1，w2，…wq/2}，W2={wq/2+1，wq/2+2，…wq}；第二，在試管T01與T02中通過(guò)DNA鏈進(jìn)行背包分量集合W1、W2所有子集對(duì)應(yīng)元素表示，TM代表M的DNA分子鏈形式；第三，對(duì)試管中DNA鏈相對(duì)應(yīng)子集執(zhí)行DNA并行加法器運(yùn)算并獲得背包分量所有子集的子集和；第四，通過(guò)并行減法器對(duì)T01試管減法操作，獲得M與T01試管中各子集和之差的DNA鏈；第五，通過(guò)執(zhí)行n位并行數(shù)據(jù)搜索器運(yùn)行，對(duì)試管T01與T02中進(jìn)行比對(duì)，找出試管T01差與T02中和參數(shù)相同的DNA鏈，其結(jié)果即背包問(wèn)題解。

（2）DNA計(jì)算機(jī)子算法中的n位并行減法器

在DNA計(jì)算機(jī)算法應(yīng)用中，如TM試管中其DNA鏈通過(guò)M來(lái)表示，如其M的第j位數(shù)值屬于1，則采取[y1q2×n+j]進(jìn)行標(biāo)記，其中j值大于0小于n+1，如其第j位樹(shù)值不為1，則通過(guò)[y0q2×n+j]進(jìn)行標(biāo)記。試管T01中[yq/2×n+j]代表子集和第j位，以lj表示T01試管運(yùn)行減法所獲得的借位，l1屬于借位初始參數(shù)，其參數(shù)值為0。通過(guò)減法運(yùn)算所獲得的差值第j位則通過(guò)uj進(jìn)行表示。n位并行減法器實(shí)現(xiàn)描述如下圖所示：

圖1 基于分治的背包問(wèn)題DNA計(jì)算機(jī)算法n位并行減法器運(yùn)行程序

通過(guò)這種算法能夠求解出M與T01試管中各DNA鏈子集和差值。

（3）DNA計(jì)算機(jī)子算法中的n位并行數(shù)據(jù)搜索器

完成并行減法計(jì)算后，T01試管NDA鏈對(duì)M及各背包分量w1，w2，…wq/2所產(chǎn)生子集的子集和差值進(jìn)行描述，而背包分量wq/2+1，wq/2+2，…wq所產(chǎn)生子集和參數(shù)則保存在T02試管中。要求對(duì)其背包分量子集和參數(shù)進(jìn)行對(duì)比。如T01試管之中所存在的某個(gè)或某些DNA鏈差值信息與T02試管中存在的DNA鏈和值參數(shù)信息一致，則說(shuō)明此背包問(wèn)題有解，如不存在相同參數(shù)信息，則說(shuō)明此背包問(wèn)題無(wú)解。為判斷背包問(wèn)題是否有解，需要讀其差值信息及子集和信息進(jìn)行對(duì)比，在本算法中為避免出現(xiàn)窮舉對(duì)比問(wèn)題，將比較劃分為兩個(gè)步驟來(lái)實(shí)現(xiàn)，即前五位與后n-5位比較方法。針對(duì)n-5位信息對(duì)比，要求在完成n-5位差信息最大值求解后查找是否存在后與之相同信息，如有則對(duì)前5位數(shù)據(jù)采取分離操作或窮舉，循環(huán)求解。通過(guò)并行數(shù)據(jù)搜索器，能夠?qū)01試管中差值與T02試管子集和值是否存在相等進(jìn)行搜索對(duì)比。通過(guò)算法對(duì)比可以實(shí)現(xiàn)信息前5位是否存在相等DNA鏈進(jìn)行分析，如存在相等鏈則說(shuō)明背包問(wèn)題有解，通過(guò)算法循環(huán)搜索出背包問(wèn)題最終解。采取這種方式，其能夠在相對(duì)短的時(shí)間內(nèi)實(shí)現(xiàn)T01試管中差值與T02試管子集和值相等狀況搜索，其鏈長(zhǎng)不變。

4 基于分治的背包問(wèn)題DNA計(jì)算機(jī)算法模擬實(shí)驗(yàn)分析

為驗(yàn)證基于分治的背包問(wèn)題DNA計(jì)算機(jī)算法應(yīng)用有效性，選擇待求解背包實(shí)例進(jìn)行模擬實(shí)驗(yàn)。設(shè)定W={1，2}，M=3，采取分治背包問(wèn)題DNA計(jì)算機(jī)算法進(jìn)行求解過(guò)程模擬：

（1）DNA編碼操作

選擇應(yīng)用Braich變量SAT問(wèn)題解決中所采取的DNA計(jì)算模型對(duì)背包中的每一個(gè)變量進(jìn)行長(zhǎng)度設(shè)計(jì)，具體設(shè)計(jì)為長(zhǎng)度均為15的堿基并作為“值序列”。綜合考慮BraichDNA計(jì)算模型之中的編碼規(guī)則，在Windows XP環(huán)境下選擇Visual C++6.0編碼器進(jìn)行DNA序列產(chǎn)生。試管T01與T02中產(chǎn)生的DNA序列具體如表1所示：

（2）算法求解過(guò)程分析

將背包集合劃分為W1、W2，應(yīng)用試管進(jìn)行T01與T02集合表示。集合W1={1}中子集[Φ]所對(duì)應(yīng)DNA分子鏈具體表示為[x01s01，1s01，2]，{1}所對(duì)應(yīng)DNA分子鏈則為[x11s11，1s01，2]，同理，集合W2={2}中子集[Φ]所對(duì)應(yīng)DNA分子鏈具體表示為[x01s01，1s01，2]，{2}所對(duì)應(yīng)的DNA分子鏈為[x11s01，1s11，2]。[xi]代表的是子集標(biāo)號(hào)，通過(guò)子集標(biāo)號(hào)進(jìn)行集合標(biāo)示，對(duì)第i個(gè)元素是否在該子集中出現(xiàn)進(jìn)行描述。Si，j代表子集集中元素標(biāo)號(hào)，該標(biāo)號(hào)作為第i個(gè)元素進(jìn)行二進(jìn)制轉(zhuǎn)換后所獲得的第j位值，通過(guò)DNA并行加法器執(zhí)行并行加法運(yùn)算。集合w1={1}其子集對(duì)應(yīng)DNA分子鏈為[x01s01，1s01，2y01y02z01y03z02y04z03]表示和為0，{1}對(duì)應(yīng)DNA分子鏈為[x11s11，1s01，2y01y02z01y13z02y04z03]表示和值為1，同理，也可以獲取集合w2={2}子集所對(duì)應(yīng)的DNA分子鏈和值為0，{2}所對(duì)應(yīng)的DNA分子鏈和值為2。應(yīng)用DNA計(jì)算機(jī)算法能夠獲取M與試管T01各子集之間差值，獲得對(duì)應(yīng)DNA分子鏈，求解出差值信息與試管T02中某些DNA鏈和值的信息，其結(jié)果即背包問(wèn)題的解。計(jì)算結(jié)果顯示試管T01子集{1}的DNA分子鏈與試管T02子集{2}的DNA分子鏈，兩條鏈并集部分即背包問(wèn)題的解。

5 結(jié)語(yǔ)

研究背包問(wèn)題其在數(shù)論研究與信息密碼學(xué)研究領(lǐng)域存在著極為重要的現(xiàn)實(shí)意義，然而在DNA計(jì)算研究中，針對(duì)大型難解問(wèn)題其存在著純指數(shù)增長(zhǎng)的DNA鏈數(shù)問(wèn)題，為解決指數(shù)增長(zhǎng)現(xiàn)值問(wèn)題，提高DNA計(jì)算效率及質(zhì)量，在DNA計(jì)算機(jī)算法中引入分治策略，并提出一種新型的背包問(wèn)題DNA計(jì)算機(jī)算法。在分析該算法實(shí)現(xiàn)步驟的基礎(chǔ)上，對(duì)其n位并行減法器及并行數(shù)據(jù)搜索器進(jìn)行分析，通過(guò)對(duì)T01試管中差值與T02試管子集和值相等狀況搜索進(jìn)行背包問(wèn)題求解。結(jié)合模擬實(shí)驗(yàn)，結(jié)果表明，采取這種DNA計(jì)算機(jī)算法，其能夠提高破解背包公鑰維數(shù)，降低背包問(wèn)題所面臨的DNA鏈數(shù)增長(zhǎng)問(wèn)題，能夠?yàn)樘岣逥NA計(jì)算機(jī)算法準(zhǔn)確性提供一種新的路徑。然而這種算法在大型難解問(wèn)題中的應(yīng)用還有待進(jìn)一步深入研究，以充分發(fā)揮其計(jì)算優(yōu)勢(shì)。

參考文獻(xiàn)：

[1] 陳改霞，耿瑞煥.基于質(zhì)粒模型的DNA計(jì)算機(jī)算法求解背包問(wèn)題[J].佳木斯職業(yè)學(xué)院學(xué)報(bào)，2014，（10）：159-159，162.

[2] 王旖旎.基于分治的背包問(wèn)題DNA計(jì)算機(jī)算法[J].計(jì)算機(jī)光盤(pán)軟件與應(yīng)用，2013（4）：159.

[3] 張曉蕾.DNA計(jì)算機(jī)算法中應(yīng)用分治背包問(wèn)題的分析[J].山海經(jīng)（故事），2015（2）：159-159.

[4] 張艷賓.分析 DNA 計(jì)算機(jī)中隊(duì)列數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)光盤(pán)軟件與應(yīng)用，2012（7）：198-199.

[5] 孫守霞，劉偉，郭迎，等.DNA計(jì)算機(jī)算術(shù)運(yùn)算的自裝配模型（Ⅲ）—減法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（32）：39-42.

[6] 張凡.基于求解Ramsey數(shù)的DNA計(jì)算機(jī)算法研究[J].湖南工業(yè)職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2015（2）：24-25，28.

[7] 張巍瓊，鄭智捷.基于不同產(chǎn)生機(jī)制的偽隨機(jī)序列和DNA序列的隨機(jī)性測(cè)量[J].成都信息工程學(xué)院學(xué)報(bào)，2012，27（6）：548-555.

[8] 郭鋒.關(guān)于DNA計(jì)算機(jī)中二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的探討[J].中國(guó)科技博覽，2012（4）：82-82.

[9] 王樹(shù)斌.因子分解問(wèn)題的DNA計(jì)算機(jī)算法探究[J].電腦編程技巧與維護(hù)，2013（16）：75-76.

[10] 徐光憲，郭曉娟.基于混沌系統(tǒng)和DNA序列運(yùn)算的新型圖像加密[J].計(jì)算機(jī)應(yīng)用研究，2015，32（6）：1766-1769.