DNA計(jì)算在求解NP—完全問題的應(yīng)用(共7頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上DNA計(jì)算在求解NP完全問題的應(yīng)用作者：周金鳳來源：科技視界2012年第35期        【摘 要】基于生化反應(yīng)的DNA計(jì)算模型越來越受到關(guān)注。DNA計(jì)算的研究已經(jīng)成為一個(gè)熱點(diǎn)。本文主要介紹了DNA計(jì)算在一些NP-完全問題中的應(yīng)用。并分析了DNA模型存在的問題。指出未來國內(nèi)DNA計(jì)算研究的重點(diǎn)可以在三個(gè)方面：解的檢測，降低空間復(fù)雜度，生化實(shí)驗(yàn)研究。        【關(guān)鍵詞】DNA計(jì)算；NP-完全問題；最大團(tuán)

2、；最小頂點(diǎn)覆蓋        0 引言        電子計(jì)算機(jī)的快速發(fā)展，在很大程度上促進(jìn)了優(yōu)化計(jì)算問題的解決。但是，電子計(jì)算機(jī)運(yùn)算速度不夠快，存貯容量不夠大。而且隨著現(xiàn)代社會科學(xué)技術(shù)的不斷進(jìn)步發(fā)展，許多新的復(fù)雜疑難問題在不斷出現(xiàn)，如一些非線性問題和NP-完全問題，特別是在一些工程領(lǐng)域內(nèi)，電子計(jì)算機(jī)很難滿足計(jì)算機(jī)發(fā)展的需要，為了可以更好的解決這類問題，一種新型的計(jì)算方法被受人們關(guān)注，即DNA計(jì)算。近些年來，DNA很受科學(xué)領(lǐng)域的關(guān)注。它

3、的進(jìn)步之處不僅僅在于其存儲量和運(yùn)算速度的改善，更重要的是他開發(fā)了本身潛在的計(jì)算能力。實(shí)踐證明，DNA計(jì)算機(jī)在計(jì)算速度和存儲容量等方面確實(shí)有很大的進(jìn)展。        DNA計(jì)算的基本思想是：利用DNA特殊的雙螺旋結(jié)構(gòu)和堿基互補(bǔ)配對規(guī)律進(jìn)行信息編碼，把要運(yùn)算的對象映射成DNA分子鏈，在生物酶的作用下，生成各種數(shù)據(jù)池，然后按照一定的規(guī)則將原始問題的數(shù)據(jù)運(yùn)算高度并行地映射成DNA分子鏈的可控的生化過程。最后，利用分子生物技術(shù)如聚合鏈反應(yīng)PCR、超聲波降解、親和層分析、克隆、誘變、分子純化、電泳、磁珠分離等，檢測所需的運(yùn)算

4、結(jié)果。最早的計(jì)算機(jī)模式是由Alderman 博士在1994首先提出的。而后，對于DNA計(jì)算機(jī)領(lǐng)域的研究引起了各科學(xué)等領(lǐng)域研究者的廣泛關(guān)注。DNA計(jì)算研究的最終目的是構(gòu)造出具有巨大并行性的DNA計(jì)算機(jī)。國內(nèi)開始DNA計(jì)算的研究始于1996年。到目前為止，我國關(guān)于DNA計(jì)算的研究大致可以分為3個(gè)階段，學(xué)習(xí)階段、理論研究階段、理論與實(shí)驗(yàn)研究階段1。自2001年開始，國內(nèi)關(guān)于DNA計(jì)算的研究基本上已經(jīng)轉(zhuǎn)入理論研究階段。自2005年開始，開始進(jìn)入實(shí)驗(yàn)研究階段。為了克服DNA計(jì)算中的一些不足，一種將編碼DNA序列固定在表面上進(jìn)行操作的方法被廣泛的研究。大部分DNA計(jì)算的出發(fā)點(diǎn)都放在解決古典的、非常復(fù)雜的計(jì)

5、算問題上，特別是NP-完全問題。這里有三點(diǎn)原因：（1）NP-完全問題是現(xiàn)有計(jì)算機(jī)難以計(jì)算的。（2）NP-完全問題隨著問題的變量、頂點(diǎn)的線性增加，計(jì)算時(shí)間是指數(shù)增加的；（3）可以說明DNA計(jì)算的高度并行性和超越電子計(jì)算機(jī)的潛在能力。NP 完全性是計(jì)算復(fù)雜性理論中的一個(gè)重要概念，它表征某些問題的固有復(fù)雜度。一旦確定一類問題具有 NP完全性時(shí)，就可知道這類問題實(shí)際上是具有相當(dāng)復(fù)雜程度的困難問題。NP 完全性的研究在實(shí)踐中有重要指導(dǎo)作用。在算法設(shè)計(jì)和分析過程中，如果已證明某問題是 NP 完全的，這就意味著面臨的是一個(gè)難于處理的問題。對于它，要找出一個(gè)在計(jì)算機(jī)上可行的（即多項(xiàng)式時(shí)間的）算法是十分困難的，

6、甚至可能根本找不到（因?yàn)楹芸赡苡?NPP）。利用DNA計(jì)算模型解決了許多NP-完全問題，DNA計(jì)算是一種模擬生物分子并借助于分子生物技術(shù)進(jìn)行計(jì)算的新方法，開創(chuàng)了以化學(xué)反應(yīng)作為計(jì)算工具的先例，為解決NP-完全問題提供了一種全新的途徑，DNA計(jì)算的實(shí)現(xiàn)方式可以分為3種：試管、表面、芯片，試管方式是DNA計(jì)算的初級階段，目的是驗(yàn)證算法的可行性；表面方式是從試管走向芯片的過渡階段；芯片方式是DNA計(jì)算最終成功的標(biāo)志。下面幾節(jié)中將較為詳細(xì)的介紹國內(nèi)關(guān)于NP-完全問題中的DNA研究成果。        1 NP-完全問題

7、60;       容易處理的問題屬于P問題。至今既沒有找到多項(xiàng)式的算法，又不能證明它不存在多項(xiàng)式的算法，這類問題成為NP問題，還有一類重要問題，只要其中任何一個(gè)問題能用一個(gè)多項(xiàng)式時(shí)間最壞情況算法來解，那么所有這些問題都能用多項(xiàng)式時(shí)間最壞情況算法解答，稱其為NP完全問題，簡稱為NPC問題。因此，對于 NP 完全問題，最好是去尋找近似解法，或者針對該問題的某些有實(shí)用價(jià)值的特殊情況，尋找多項(xiàng)式時(shí)間算法。        1.1 0-1規(guī)劃問題的DNA計(jì)

8、算模型        對于0-1規(guī)劃問題，2003年，殷志祥等人給出了表面DNA計(jì)算模型。通過觀察熒光來排除非解，這種解讀方法簡單而有效且錯(cuò)誤率低2。2007年，殷志祥等人又給出了基于分子信標(biāo)芯片的0-1規(guī)劃問題的DNA計(jì)算模型3。該模型將問題變量映射為分子信標(biāo)探針，在芯片上制備可尋址的DNA分子信標(biāo)探針，通過加入代變量的DNA鏈的互補(bǔ)鏈，DNA分子就會按照W-C互不原則進(jìn)行雜交，從而并行地生成問題的所有可能解。隨后通過對雜交后分子信標(biāo)探針圖像進(jìn)行分析即可得到問題的最優(yōu)解，和以往的DNA計(jì)算模型相比，該模型由于運(yùn)用

9、了分子信標(biāo)芯片技術(shù)，具有高密度樣品矩陣，有可能解決更多個(gè)變量的0-1整數(shù)規(guī)劃問題。由于分子信標(biāo)作為生物芯片可以充分利用自身的優(yōu)點(diǎn)：編碼簡單；耗材低；操作時(shí)間短；技術(shù)先進(jìn)。所以對于不同的組合優(yōu)化問題，可以將標(biāo)有不同熒光分子的信標(biāo)、不同識別區(qū)長度的分子信標(biāo)、不同莖桿長度的分子信標(biāo)通過生物素的形式固定到硅片的表面上，制成分子信標(biāo)片，利用所構(gòu)造的分子信標(biāo)芯片實(shí)現(xiàn)問題的自動化求解過程。其編碼過程定在表面上，使之成為一行。（2）在每個(gè)不同行對應(yīng)的分子信標(biāo)探針的莖桿底部設(shè)置熒光。對應(yīng)的算法步驟2，根據(jù)約束方程的各個(gè)變量，把它們中的各個(gè)變量對應(yīng)的補(bǔ)鏈加到表面上，通過雜交使表面上的分子信標(biāo)探針產(chǎn)生熒光，利用激光

10、共聚焦顯微鏡觀察到某一列分子信標(biāo)探針對應(yīng)的解是否滿足該約束條件。（3）對應(yīng)算法的步驟3，我們對步驟2的產(chǎn)物進(jìn)行加熱解開雙鏈，沖洗掉與分子信標(biāo)探針雜交的所有補(bǔ)鏈，（對于已經(jīng)判斷為不滿足約束條件的不再考慮）。（4）對應(yīng)算法步驟4，（我們重復(fù)步驟2，3的操作m次），我們就可以得到滿足約束方程組的可行解。（5）對應(yīng)算法的步驟5，我們對可行解所對應(yīng)的目標(biāo)函數(shù)值加以比較后，就可以得到問題的最優(yōu)解。        1.2 最小頂點(diǎn)覆蓋問題的DNA計(jì)算模型      &#

11、160; 對于圖G=（V，E）的結(jié)點(diǎn)子集K？哿V，如果G的任意一條邊都至少有一個(gè)端點(diǎn)屬于K，則稱K為G的一個(gè)頂點(diǎn)覆蓋；若對任意結(jié)點(diǎn)V？哿K，K-V不再是頂點(diǎn)覆蓋，稱K為G的極小頂點(diǎn)覆蓋；K是G的頂點(diǎn)覆蓋，且G不存在另一頂點(diǎn)K滿足KK，則稱K為G的最小頂點(diǎn)覆蓋；G的最小頂點(diǎn)覆蓋的基數(shù)稱為G的覆蓋數(shù)，記做C（G），G的頂點(diǎn)覆蓋常簡稱為G的覆蓋。最小頂點(diǎn)覆蓋問題是圖論中一個(gè)著名的NP-完全問題。2004年，王淑棟等利用表面DNA計(jì)算的方法給出了最小頂點(diǎn)覆蓋問題的DNA計(jì)算模型4。該模型的優(yōu)點(diǎn)是結(jié)合了圖論中的基本結(jié)論，增加了DNA計(jì)算的可操作性。但是該模型在編碼介紹上不夠清楚。2005年，董

12、亞飛等人給出了最小頂點(diǎn)覆蓋問題的粘貼模型5。在算法中設(shè)計(jì)了熒光淬滅的有關(guān)技術(shù)，利用觀察熒光來排除非解，這種讀解方法簡單而有效且錯(cuò)誤率低。由于檢測方法的改變，省略了在試管計(jì)算中常用的酶切、磁珠分離、PCR擴(kuò)增、凝膠電泳等步驟，避免了在這些步驟中可能出現(xiàn)的計(jì)算誤差和數(shù)據(jù)丟失；并且我們使用的材料可重復(fù)使用，與在試管溶液中的DNA計(jì)算相比，更接近于工程實(shí)踐。但是，自然界可供我們使用的熒光素種類有限，如果DNA計(jì)算的規(guī)模便得巨大，有可能造成計(jì)算材料上的困難，該方法是DNA計(jì)算粘貼模型利用表面技術(shù)的一種嘗試。2009年，羊四清等利用基于表面的DNA計(jì)算，將圖的最小頂點(diǎn)覆蓋問題轉(zhuǎn)化為特殊的0-1規(guī)劃問題，將

13、對應(yīng)于問題解空間的DNA分子固定在固體載體上，利用熒光淬滅技術(shù)，通過對每一個(gè)約束方程進(jìn)行判斷，刪除所有不滿足條件的解，得到剩余解。最后比較剩余解中0的個(gè)數(shù)最多的解集都為該圖的最小頂點(diǎn)覆蓋6。        1.3 最大團(tuán)與最大匹配問題的DNA計(jì)算模型        最大團(tuán)問題是圖論上一重要的NP完全問題，而且它在理論和實(shí)踐上具有重要的意義。設(shè)G=V，E是簡單無向圖，T？哿V，TQ，若T中任意兩個(gè)頂點(diǎn)都相鄰，則稱T是圖G的團(tuán)。若T是圖G的

14、團(tuán)，但是任意增加一個(gè)新頂點(diǎn)后，它就不成為團(tuán)，則稱T式圖G的極大團(tuán)。2004年，李源等給出了最大團(tuán)問題的DNA計(jì)算模型7。該算法的主要思想是首先用一個(gè)n位的二進(jìn)制數(shù)表示具有n個(gè)頂點(diǎn)的圖的可能團(tuán)，將問題轉(zhuǎn)化為求解二進(jìn)制數(shù)字串中含有1最多的數(shù)字串。然后設(shè)計(jì)算法，算法計(jì)算是從空網(wǎng)開始，對應(yīng)的二進(jìn)制數(shù)每一位都是0，然后讓樣本群體一代代演化。在每一代中，首先使各個(gè)二進(jìn)制數(shù)的每一位以某一概率置1，然后從樣本群體中刪除在補(bǔ)圖中相鄰頂點(diǎn)對應(yīng)位置均為1的數(shù)字串。算法的生物實(shí)現(xiàn)主要是先將二進(jìn)制數(shù)編碼到DNA鏈中，一個(gè)單鏈代表一個(gè)二進(jìn)制數(shù)。為了編碼一個(gè)n位二進(jìn)制數(shù)，共用2*n +1種不同的DNA片段，分別用n+1種不

15、同的DNA片段序列代表n+1個(gè)位置和n代表每一位置的片段，這里表示0，1值的序列分別用不同的長度；來區(qū)別。該算法在數(shù)值為1的位置不用任何DNA片段表示，而用酶切位點(diǎn)取代。通過酶切刪除在補(bǔ)圖中相鄰頂點(diǎn)位置均為1 的鏈，最后可以求出問題的解。        該算法的最大優(yōu)點(diǎn)在于將分子化思想引的入DNA算法中，而不是生成所有可能的解。因此使用了一個(gè)較小的樣本空間可以對NP問題進(jìn)行求解，隨著圖的頂點(diǎn)數(shù)的增加，算法所需的步驟也是線性增長的。       &

16、#160;對于最大匹配問題，同樣是一重要的NP完全問題。設(shè)G是無環(huán)圖，M？哿E（G），MQ，如果M中任意兩條邊在G中均不相鄰，則稱M是圖G的一個(gè)匹配。若對圖G的任何匹配M，均有M        順序進(jìn)行編碼）二進(jìn)制串來表示；若二進(jìn)制串中的某位值為1，則其對應(yīng)的邊在匹配中；否則，則不在，具體的算法步驟如下：        （1）對圖G中的m位二進(jìn)制串進(jìn)行編碼；      

17、0; （2）生成圖G的滿足條件的所有匹配。        （3）找出其中含1最多的串，即為對應(yīng)的最大匹配，并輸出結(jié)果。        本文主要思想通過表面上逐步生成解空間的過程，隨時(shí)刪除所生成的不可行解；最后，通過合適的編碼，用PCR和電泳技術(shù)可以將解集中的不同解逐步分辨出來。        1.4 圖的頂點(diǎn)著色問題  

18、0;     圖G的頂點(diǎn)集V（G）表示物體，G中的邊表示邊的來兩個(gè)頂點(diǎn)所代表的物體不能在同一類中。用顏色C表示類，用著色表示物體的劃分：V（G）C。如果C有k種顏色，則被稱為k著色。則稱G是n可著色的。使得G是n可著色的最小值n稱為G的點(diǎn)色數(shù)，或簡稱為色數(shù)，記為？掊（G）。圖著色問題指的是給定一個(gè)n個(gè)頂點(diǎn)和m條邊的圖，？掊（G）是多少？圖著色問題是NP-完全問題。        2006年許進(jìn)等人給出了一種圖頂點(diǎn)著色的DNA計(jì)算模型9。給出了實(shí)現(xiàn)給出了實(shí)現(xiàn)20個(gè)頂點(diǎn)

19、的圖頂點(diǎn)的3著色的DNA計(jì)算機(jī)編碼， 擬以這20個(gè)頂點(diǎn)的圖為例進(jìn)一步研究此模型的DNA計(jì)算機(jī)。在前人工作的基礎(chǔ)上， 本研究針對性地提出了求解此類問題的專用型DNA計(jì)算機(jī)， 不但給出了詳細(xì)的理論說明及其基本原理， 并且在此思想的指導(dǎo)下， 利用雜交反應(yīng)、磁珠分離技術(shù)以及PCR反應(yīng)等生物實(shí)驗(yàn)技術(shù)， 實(shí)現(xiàn)了具有5個(gè)頂點(diǎn)圖的3著色的DNA計(jì)算， 再一次驗(yàn)證了DNA計(jì)算的高度并行性， 以及解決NP問題的可能性. 同時(shí)從生物實(shí)驗(yàn)的角度出發(fā)， 進(jìn)行靈敏度實(shí)驗(yàn)， 在此基礎(chǔ)上通過預(yù)實(shí)驗(yàn)選擇合適的雜交溫度和雜交時(shí)間， 確保PCR反應(yīng)的有效模板濃度， 并進(jìn)行了重復(fù)實(shí)驗(yàn)， 進(jìn)而保證實(shí)驗(yàn)結(jié)果的可靠性。在以前的編碼研究中，

20、 大多停留在理論研究水平， 真正用于生物學(xué)實(shí)驗(yàn)的并不多。 本文在前人研究的基礎(chǔ)上， 認(rèn)識到編碼的重要性的同時(shí)， 綜合考慮化學(xué)自由能、溫度、生物酶、編碼的相似性、DNA分子的組成等對編碼的制約和影響， 給出了8個(gè)約束條件， 并在此基礎(chǔ)上， 給出編碼的具體算法， 并得到比較適合解決20個(gè)頂點(diǎn)的圖的頂點(diǎn)3著色求解的DNA序列。 5個(gè)頂點(diǎn)圖的3著色的DNA計(jì)算所用的編碼也來源于此。        5個(gè)頂點(diǎn)的無向有限圖的3著色的DNA計(jì)算的生物實(shí)驗(yàn)的成功， 不僅豐富了DNA計(jì)算的理論， 而且在實(shí)驗(yàn)過程中摸索到的實(shí)驗(yàn)條件都可以

21、為進(jìn)一步深入研究圖頂點(diǎn)著色問題提供參考， 甚至對其他問題的DNA計(jì)算都有很大的意義. 但是本實(shí)驗(yàn)依然存在不足， 實(shí)驗(yàn)過程耗時(shí)較長， 溶液中DNA鏈的損失較大， 還應(yīng)從選擇更適用的實(shí)驗(yàn)方法和手段， 以及尋找更具有普適性的編碼方案等方面繼續(xù)深入研究。        2 面臨的問題        雖然，DNA計(jì)算有了很大的發(fā)展，但是還是存在一些不足之處，理論和實(shí)際操作方面都還面臨著一系列的挑戰(zhàn)。在生化反應(yīng)操作的過程中容易出錯(cuò)。特別是在進(jìn)行雜交

22、時(shí)容易出錯(cuò)。計(jì)算精度不能夠得到確保，因?yàn)楹怂崦傅慕到庑什粔蚋?；DNA的計(jì)算規(guī)模還受到限制；所以對于DNA計(jì)算機(jī)來說，一些問題還需要及時(shí)進(jìn)行解決。（1）怎樣才能夠把誤差降到最低，因?yàn)樵谶M(jìn)行生物操作的提取和退火步驟中，會產(chǎn)生誤差。（2）怎樣更好的對獲得的結(jié)果進(jìn)行檢索？大量DNA聚集在一起，因?yàn)榘l(fā)生退火反應(yīng)以至于產(chǎn)生“偽解”。（3）怎樣才可以盡量避免錯(cuò)誤地雜交？（4）怎樣才可以進(jìn)行正確的編碼？隨著用于編碼的寡聚核苷酸鏈長度的增加，編碼的復(fù)雜度也隨著增加，容易產(chǎn)生發(fā)夾結(jié)構(gòu)。（5）在進(jìn)行實(shí)際操作時(shí)，怎樣才能夠建立更好的模型，使問題得到有效解決？10。    &#

23、160;   3 進(jìn)一步的研究方向        從1994年Adleman 提出計(jì)算機(jī)模型以來，DNA計(jì)算的研究內(nèi)容有了很大的發(fā)展：DNA芯片的研制、DNA計(jì)算模型的構(gòu)造、DNA 計(jì)算和納米技術(shù)的結(jié)合，計(jì)算模擬和序列設(shè)計(jì)等。DNA計(jì)算可以分為大致以下幾個(gè)研究方面：        （1）解的檢測。如何將溶液狀態(tài)下產(chǎn)生的眾多解（DNA鏈）中代表所求問題最終解的DAN鏈分離出來，尋找合理、有效地分離方法。

24、60;       （2）降低空間復(fù)雜度。由于表面（固體狀態(tài)）計(jì)算是將時(shí)間復(fù)雜性轉(zhuǎn)化為空間復(fù)雜性，因此如何降低時(shí)間復(fù)雜性轉(zhuǎn)化時(shí)的空間復(fù)雜性就顯得非常重要。而如何降低空間復(fù)雜性牽涉到算法設(shè)計(jì)和編碼。因此進(jìn)一步研究DNA計(jì)算中的算法是非常重要的一個(gè)研究內(nèi)容。另外，結(jié)合其他相關(guān)算法如進(jìn)化算法、遺傳算法及神經(jīng)網(wǎng)絡(luò)算法等進(jìn)行研究也是一個(gè)有效途徑。最后，DNA計(jì)算中編碼的研究也是一個(gè)非常重要的研究方向，因?yàn)楹玫木幋a方法不僅可以解決復(fù)雜性轉(zhuǎn)化問題，而且它關(guān)系到DNA計(jì)算的各個(gè)方面，如生化操作的可行性，錯(cuò)配率的高低、偽解的產(chǎn)生以及生化實(shí)驗(yàn)的

25、成敗。        （3）生化試驗(yàn)的研究。DNA計(jì)算的研究的最終目標(biāo)是構(gòu)造DNA計(jì)算機(jī)，這就必須能進(jìn)行生化試驗(yàn)?，F(xiàn)有的DNA計(jì)算模型大部分都是理論研究，是否可以通過生化試驗(yàn)進(jìn)行實(shí)現(xiàn)還有待進(jìn)一步研究，生化試驗(yàn)不僅可以驗(yàn)證算法的優(yōu)劣而且可以為進(jìn)一步研究提供不斷地改進(jìn)方案。因此，我們認(rèn)為即使對現(xiàn)有的DNA計(jì)算模型進(jìn)行生化實(shí)驗(yàn)的研究都是有意義的。        雖然DNA計(jì)算現(xiàn)在還存在一些問題，但是DNA計(jì)算作為一個(gè)新興的研究領(lǐng)域，已經(jīng)得到了

26、廣泛應(yīng)用，而且已用來解決了很多實(shí)際問題。現(xiàn)在科學(xué)家對DNA的研究和發(fā)展抱有很大信心。它使人們首次認(rèn)識到生物中存在的基本算法，總之，DNA計(jì)算機(jī)和DNA計(jì)算有著巨大的發(fā)展?jié)摿Α?#160;       【參考文獻(xiàn)】        1高琳，許進(jìn)，張軍英.DNA計(jì)算的研究進(jìn)展與展望J.電子學(xué)報(bào)，2001，29（1）：973-977.        2殷志祥，許進(jìn).分子信標(biāo)芯片計(jì)算在0-1整數(shù)規(guī)劃問題中的應(yīng)用J.生物數(shù)學(xué)學(xué)報(bào)，2007，22（3）：559-564.        3殷志祥，張鳳月，許進(jìn).基于分子信標(biāo)的DNA計(jì)算J.生物數(shù)學(xué)學(xué)報(bào)， 2003，18（4）：497-501.        4王淑棟，許進(jìn)，董亞飛.圖的最小頂點(diǎn)覆蓋問題的面上DNA解法