基于分治的子集積問題DNA計算機算法

基于分治的子集積問題DNA計算機算法

0　引言

分治法是一種較為傳統的算法，這種算法在中國流行了許多年，時至今日這種算法依然被很多專業人士所運用。而DNA算法是近些年才在中國國內興起的。盡管DNA算法在國內發展的時間還很短暫，但因為DNA算法有著巨大的優勢，所以DNA算法越來越受到專業人士的青睞。本文將把這兩種算法綜合運用，從而來解答子集積的問題。

1　DNA計算、分治法同時用于子集積問題中的現實意義

分治法通常包含三個步驟：第一個步驟是把需要解答的問題看作是母問題，把母問題分解成一個個規模較小的子問題，第二個步驟是把小規模的子問題一個個解決掉，第三個步驟是把已經解決了的所有子問題統統合并起來，最后得出母問題的答案。而DNA算法的本質是：由于DNA能很好地做到并行計算，所以把DNA工具當成是計算的工具，充分借助DNA的運行能力來解決一些問題。目前，分治法被當作是傳統算法，DNA這種算法被當成是現代算法，而本文就是要把這兩種算法結合從而誕生一種全新的算法，并將其用于子集積問題的實際解答中。

2　阿德爾曼—立頓模型的基本內容

現實中，DNA計算時對阿德爾曼—立頓模型的利用率是最高的。所以，本文先來介紹下阿德爾曼—立頓這種模型的基本內容。這種模型是由生物學家立頓結合生物學家阿德爾曼的研究成果而提出的。生物學家立頓認為阿德爾曼—立頓模型包括6個基本步驟。

第一個步驟簡稱為抽取步驟。假定有一個試管，該試管用字母Q表示，還有一個DNA單鏈，該DNA單鏈用字母R表示。那么抽取步驟有-（Q,R）和+（Q,R）兩種。假如某DNA鏈中包含了R單鏈，那么這個DNA鏈便屬于+（Q,R）中。假如某DNA鏈中并不包含R單鏈，那么這個DNA鏈便屬于-（Q,R）中。

第二個步驟簡稱為合并步驟。假定有兩個不同的試管，這兩個不同的試管分別用字母Q1和Q2來表示。合并步驟是指：把Q1試管和Q2試管中的內容合并起來放到同一根試管中，同時要保證無論Q1還是Q2中的分子鏈都不能有任何改變。

第三個步驟簡稱為檢測步驟[3]。假定有一個試管，該試管用字母Q表示。Q試管中有一個及以上的DNA鏈，那么結果便返回英文YES，否則結果便返回英文NO。

第四個步驟簡稱為復制步驟。假定有一個試管，該試管用字母Q表示。對Q試管做2次復制的基本操作，則將產生Q1和Q2，同時Q試管被清空。

第五個步驟簡稱為添加步驟。假定有一個試管，該試管用字母Q表示，還有一個DNA單鏈，該DNA單鏈用字母R表示。添加步驟是指：把R單鏈分別添加到Q試管中每個DNA鏈的尾部位置。

第六個步驟簡稱為讀取步驟。假定有一個試管，該試管用字母Q表示。讀取步驟是指：把Q試管中全部的DNA鏈進行0/1信息的讀取。

3　基于分治的子集積問題DNA計算機算法

3.1DNA計算用于子集積問題中的計算框架

本文認為DNA計算、分治法同時用于子集積問題中的計算框架包含了如下的步驟：（1）假定有兩根不同的試管，這兩根不同試管分別用字母Q1和Q2來表示。假定有兩個子集積，這兩個子集積分別用字母V1和V2來表示。第一步是把V1、V2中的全部子集以DNA鏈的方式分別表示于Q1、Q2試管中。QL用以表示DNA鏈的基本形式[1]。（2）當V1、V2中的全部子集以DNA鏈的方式分別表示于Q1、Q2試管中之后，對Q1和Q2試管中的全部DNA鏈做乘法運算，得到的便是V1和V2每個子集對應的子集積。（3）對Q1中的全部DNA鏈做除法運算，得到的便是Q1中全部子集積跟L商的全部DNA鏈。（4）借助并行數據的常用搜索器（N位）進行搜索，搜索的目的是比較Q1和Q2中的全部DNA鏈。找出Q1中商以及Q2中積完全相同的鏈，這些完全相同的鏈便是整個子集積問題的最后答案。

3.2DNA計算用于子集積問題中的子算法設計

本文認為子算法的基本設計思路共有以下幾個步驟：

（1）假定有一個試管，該試管用字母Q表示。利用上述談到的抽取步驟對Q試管做兩次抽取的操作，得出Q1和Q2。Q1中商信息的首位用字母Cn,1來表示，那么Cn,1（Qn，1）的值為1。Q2中商信息的首位也用字母Cn,1來表示，那么Cn,1（Qn，1）的值為0。把Q1中商信息的前面5位（32種）用不同試管分別裝取。

（2）在第2a步驟中，第二位信息共有4種可能，第三位信息共有8種可能，第四位信息共有16種可能，第五位信息共有32種可能。這幾位信息的不同可能用不同試管來分別裝取。執行2a步驟的時候，一共需要做兩次執行操作。第一次執行的時候，設定j的值為2，k的值為3。第二次執行的時候，設定j的值為2，k的值為5。

（3）在第2b步驟中的首次執行中，再對Q試管做兩次抽取的操作，得出Q3和Q4。Q3中商信息的首位用字母Cn,1來表示，那么Cn,1（Qn，1）的值為1，Cn,2（Qn，2）的值也為1。Q4中商信息的首位也用字母Cn,1來表示，那么Cn,1（Qn，1）的值為1，Cn,2（Qn，2）的值為0。

（4）在第2b步驟中的二次執行中，再對Q試管做兩次抽取的操作從而得出Q5和Q6。Q5中商信息的首位用字母Cn,1來表示，那么Cn,1（Qn，1）的值為0，Cn,2（Qn，2）的值也為1。Q6中商信息的首位也用字母Cn,1來表示，那么Cn,1（Qn，1）的值為0，Cn,2（Qn，2）的值為0。

（5）當上述4個步驟都完整執行以后，那么j=2這個循環的全過程便圓滿結束。Q3、Q4、Q5、Q6試管分別把試管中的前面兩位信息存儲起來。然后，再執行j的值分別取3、取4、取5時的操作，這樣便能獲得前五位的全部信息，而前五位的全部信息一共是32種。

（6）在上面5個步驟完畢之后，便能分別獲得前五位的和信息以及差信息（32種）。第6個步驟是對這32種情況進行具體的比較。第6個步驟具體分成6a、6b、6c三種步驟。在第6a步驟中，主要判定Q131、Q231兩者是不是都存在DNA鏈。假如兩者都有DNA鏈的存在，那么在第6b的步驟中便把Q131、Q231兩者分別讀出。這時，到6c步驟的時候便結束循環。如若不然，則反復做循環的有關操作，一直到k的值取62為止。

3.3DNA計算、分治法同時用于子集積問題中的具體計算方式

把DNA計算、分治法同時用于子集積問題中的具體計算共有以下幾個步驟：

（1）將Init（Q1，?q）和Init（Q2，?q）分別執行，同時把V1、V2中的全部子集以DNA鏈的方式分別表示于Q1、Q2試管中。

（2）把V1、V2中的全部子集以DNA鏈的方式按照value（Q1，?q,n）、value（Q2，?q,n）的原則表示出來。

（3）對V2中的全部DNA鏈做乘法運算以求得子集的和。把QL也用DNA鏈的基本形式來表示。

（4）求出Q跟L間子集積的商。

（5）找出Q1中商以及Q2中積完全相同的鏈，這些完全相同的鏈便是整個子集積問題的最后答案。

以上5個步驟的解讀：第一步具體做了三個方面的操作：一是q個復制；二是2q個添加；三是q個合并。第二步也做了三個方面的操作：一是2nq個添加；二是q個抽取；三是q個合并。第三步做的操作有：n?q?O個添加、n?q?O個添加、n?q?O合并。第四步做的操作是n個添加。第五步做的操作有：n?q?O個添加、n?q?O個添加、n?q?O合并。所以，最終生物操作的總數量表示為：n?q?O+LOn。

現實中，由于算法總共用到的試管數量是62，所以試管數可以用O（1）來表示。鏈的最長長度用n?q?O來表示。算法中，集合V共計q個元素，由于引入了分治法，所以集合V被分成了兩個?q的集合V1與集合V2。在Init（Q1，?q）和Init（Q2，?q）的執行中，集合V1、V2分別生成了數量為 2q/2的DNA鏈。而在此后的運算中，便再也沒有其它DNA鏈生成。所以，DNA鏈數量為O（2q/2）[2]。

4　結束語

綜上，本文首先闡述了DNA計算、分治法同時用于子集積問題中的現實意義。其次，本文簡要闡述了DNA算法中最流行的模型（阿德爾曼—立頓模型）的基本內容。再次，本文較為細致地闡述了在解答子集積問題時把DNA算法、分治法結合使用的具體算法。

參考文獻：

[1]潘果，李肯立，劉萬方等.基于分治法的子集積問題DNA計算機算法研究[J].計算機工程與科學，2011（20）：23-36.

[2]李肯立，姚鳳娟，李仁發等.基于分治法的背包問題DNA計算機算法研究[J].計算機研究與發展，2011（10）：3-10.

[3]李肯立，徐進，李仁發等.基于分治法的子集問題DNA計算機算法研究[J].計算機學報，2013（15）：22-26.

2014年院級科研項目（Wzywt201421/23）。

項目基金：安徽省高等學校質量工程教學研究項目（2013jyxm319）；

作者簡介：呂嫄（1983-），女，安徽蕪湖人，講師，主要從事數據挖掘方向研究。