基于分治的子集積問題DNA計(jì)算機(jī)算法

基于分治的子集積問題DNA計(jì)算機(jī)算法

0　引言

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

1　DNA計(jì)算、分治法同時(shí)用于子集積問題中的現(xiàn)實(shí)意義

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

2　阿德爾曼—立頓模型的基本內(nèi)容

現(xiàn)實(shí)中，DNA計(jì)算時(shí)對(duì)阿德爾曼—立頓模型的利用率是最高的。所以，本文先來介紹下阿德爾曼—立頓這種模型的基本內(nèi)容。這種模型是由生物學(xué)家立頓結(jié)合生物學(xué)家阿德爾曼的研究成果而提出的。生物學(xué)家立頓認(rèn)為阿德爾曼—立頓模型包括6個(gè)基本步驟。

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

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

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

第四個(gè)步驟簡(jiǎn)稱為復(fù)制步驟。假定有一個(gè)試管，該試管用字母Q表示。對(duì)Q試管做2次復(fù)制的基本操作，則將產(chǎn)生Q1和Q2，同時(shí)Q試管被清空。

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

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

3　基于分治的子集積問題DNA計(jì)算機(jī)算法

3.1DNA計(jì)算用于子集積問題中的計(jì)算框架

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

3.2DNA計(jì)算用于子集積問題中的子算法設(shè)計(jì)

本文認(rèn)為子算法的基本設(shè)計(jì)思路共有以下幾個(gè)步驟：

（1）假定有一個(gè)試管，該試管用字母Q表示。利用上述談到的抽取步驟對(duì)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種可能。這幾位信息的不同可能用不同試管來分別裝取。執(zhí)行2a步驟的時(shí)候，一共需要做兩次執(zhí)行操作。第一次執(zhí)行的時(shí)候，設(shè)定j的值為2，k的值為3。第二次執(zhí)行的時(shí)候，設(shè)定j的值為2，k的值為5。

（3）在第2b步驟中的首次執(zhí)行中，再對(duì)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步驟中的二次執(zhí)行中，再對(duì)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）當(dāng)上述4個(gè)步驟都完整執(zhí)行以后，那么j=2這個(gè)循環(huán)的全過程便圓滿結(jié)束。Q3、Q4、Q5、Q6試管分別把試管中的前面兩位信息存儲(chǔ)起來。然后，再執(zhí)行j的值分別取3、取4、取5時(shí)的操作，這樣便能獲得前五位的全部信息，而前五位的全部信息一共是32種。

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

3.3DNA計(jì)算、分治法同時(shí)用于子集積問題中的具體計(jì)算方式

把DNA計(jì)算、分治法同時(shí)用于子集積問題中的具體計(jì)算共有以下幾個(gè)步驟：

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

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

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

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

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

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

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

4　結(jié)束語

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

參考文獻(xiàn)：

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

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

[3]李肯立，徐進(jìn)，李仁發(fā)等.基于分治法的子集問題DNA計(jì)算機(jī)算法研究[J].計(jì)算機(jī)學(xué)報(bào)，2013（15）：22-26.

2014年院級(jí)科研項(xiàng)目（Wzywt201421/23）。

項(xiàng)目基金：安徽省高等學(xué)校質(zhì)量工程教學(xué)研究項(xiàng)目（2013jyxm319）；

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