曾毅

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

關鍵詞：分治；背包問題；DNA；計算機算法

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2015）05-0213-03

1 基于分治的背包問題DNA計算機算法提出背景

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

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

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

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

2 Adleman-Lipton模型認知

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

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

3 基于分治的背包問題DNA計算機算法分析

（1）基于分治法理念的背包問題DNA計算機算法思想分析

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

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

（2）DNA計算機子算法中的n位并行減法器

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

圖1 基于分治的背包問題DNA計算機算法n位并行減法器運行程序

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

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

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

4 基于分治的背包問題DNA計算機算法模擬實驗分析

為驗證基于分治的背包問題DNA計算機算法應用有效性，選擇待求解背包實例進行模擬實驗。設定W={1，2}，M=3，采取分治背包問題DNA計算機算法進行求解過程模擬：

（1）DNA編碼操作

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

（2）算法求解過程分析

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

5 結語

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

參考文獻：

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

[2] 王旖旎.基于分治的背包問題DNA計算機算法[J].計算機光盤軟件與應用，2013（4）：159.

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

[4] 張艷賓.分析 DNA 計算機中隊列數(shù)據(jù)結構的設計與實現(xiàn)[J].計算機光盤軟件與應用，2012（7）：198-199.

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

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

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

[8] 郭鋒.關于DNA計算機中二叉樹存儲結構的探討[J].中國科技博覽，2012（4）：82-82.

[9] 王樹斌.因子分解問題的DNA計算機算法探究[J].電腦編程技巧與維護，2013（16）：75-76.

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