DNA計算在求解NP-完全問題的應(yīng)用

周金鳳

（安徽理工大學 安徽 淮南 232001）

0 引言

電子計算機的快速發(fā)展，在很大程度上促進了優(yōu)化計算問題的解決。但是，電子計算機運算速度不夠快，存貯容量不夠大。而且隨著現(xiàn)代社會科學技術(shù)的不斷進步發(fā)展，許多新的復(fù)雜疑難問題在不斷出現(xiàn)，如一些非線性問題和NP-完全問題，特別是在一些工程領(lǐng)域內(nèi)，電子計算機很難滿足計算機發(fā)展的需要，為了可以更好的解決這類問題，一種新型的計算方法被受人們關(guān)注，即DNA計算。近些年來，DNA很受科學領(lǐng)域的關(guān)注。它的進步之處不僅僅在于其存儲量和運算速度的改善，更重要的是他開發(fā)了本身潛在的計算能力。實踐證明，DNA計算機在計算速度和存儲容量等方面確實有很大的進展。

DNA計算的基本思想是：利用DNA特殊的雙螺旋結(jié)構(gòu)和堿基互補配對規(guī)律進行信息編碼，把要運算的對象映射成DNA分子鏈，在生物酶的作用下，生成各種數(shù)據(jù)池，然后按照一定的規(guī)則將原始問題的數(shù)據(jù)運算高度并行地映射成DNA分子鏈的可控的生化過程。最后，利用分子生物技術(shù)如聚合鏈反應(yīng)PCR、超聲波降解、親和層分析、克隆、誘變、分子純化、電泳、磁珠分離等，檢測所需的運算結(jié)果。最早的計算機模式是由Alderman博士在1994首先提出的。而后，對于DNA計算機領(lǐng)域的研究引起了各科學等領(lǐng)域研究者的廣泛關(guān)注。DNA計算研究的最終目的是構(gòu)造出具有巨大并行性的DNA計算機。國內(nèi)開始DNA計算的研究始于1996年。到目前為止，我國關(guān)于DNA計算的研究大致可以分為3個階段，學習階段、理論研究階段、理論與實驗研究階段[1]。自2001年開始，國內(nèi)關(guān)于DNA計算的研究基本上已經(jīng)轉(zhuǎn)入理論研究階段。自2005年開始，開始進入實驗研究階段。為了克服DNA計算中的一些不足，一種將編碼DNA序列固定在表面上進行操作的方法被廣泛的研究。大部分DNA計算的出發(fā)點都放在解決古典的、非常復(fù)雜的計算問題上，特別是NP-完全問題。這里有三點原因：（1）NP-完全問題是現(xiàn)有計算機難以計算的。（2）NP-完全問題隨著問題的變量、頂點的線性增加，計算時間是指數(shù)增加的；（3）可以說明DNA計算的高度并行性和超越電子計算機的潛在能力。NP完全性是計算復(fù)雜性理論中的一個重要概念，它表征某些問題的固有復(fù)雜度。一旦確定一類問題具有NP完全性時，就可知道這類問題實際上是具有相當復(fù)雜程度的困難問題。NP完全性的研究在實踐中有重要指導作用。在算法設(shè)計和分析過程中，如果已證明某問題是 NP完全的，這就意味著面臨的是一個難于處理的問題。對于它，要找出一個在計算機上可行的（即多項式時間的）算法是十分困難的，甚至可能根本找不到(因為很可能有 NP≠P)。利用DNA計算模型解決了許多NP-完全問題，DNA計算是一種模擬生物分子并借助于分子生物技術(shù)進行計算的新方法，開創(chuàng)了以化學反應(yīng)作為計算工具的先例，為解決NP-完全問題提供了一種全新的途徑，DNA計算的實現(xiàn)方式可以分為3種：試管、表面、芯片，試管方式是DNA計算的初級階段，目的是驗證算法的可行性；表面方式是從試管走向芯片的過渡階段；芯片方式是DNA計算最終成功的標志。下面幾節(jié)中將較為詳細的介紹國內(nèi)關(guān)于NP-完全問題中的DNA研究成果。

1 NP-完全問題

容易處理的問題屬于P問題。至今既沒有找到多項式的算法，又不能證明它不存在多項式的算法，這類問題成為NP問題，還有一類重要問題，只要其中任何一個問題能用一個多項式時間最壞情況算法來解，那么所有這些問題都能用多項式時間最壞情況算法解答，稱其為NP完全問題，簡稱為NPC問題。因此，對于 NP完全問題，最好是去尋找近似解法，或者針對該問題的某些有實用價值的特殊情況，尋找多項式時間算法。

1.1 0-1規(guī)劃問題的DNA計算模型

對于0-1規(guī)劃問題，2003年，殷志祥等人給出了表面DNA計算模型。通過觀察熒光來排除非解，這種解讀方法簡單而有效且錯誤率低[2]。2007年，殷志祥等人又給出了基于分子信標芯片的0-1規(guī)劃問題的DNA計算模型[3]。該模型將問題變量映射為分子信標探針，在芯片上制備可尋址的DNA分子信標探針，通過加入代變量的DNA鏈的互補鏈，DNA分子就會按照W-C互不原則進行雜交，從而并行地生成問題的所有可能解。隨后通過對雜交后分子信標探針圖像進行分析即可得到問題的最優(yōu)解，和以往的DNA計算模型相比，該模型由于運用了分子信標芯片技術(shù)，具有高密度樣品矩陣，有可能解決更多個變量的0-1整數(shù)規(guī)劃問題。由于分子信標作為生物芯片可以充分利用自身的優(yōu)點：編碼簡單；耗材低；操作時間短；技術(shù)先進。所以對于不同的組合優(yōu)化問題,可以將標有不同熒光分子的信標、不同識別區(qū)長度的分子信標、不同莖桿長度的分子信標通過生物素的形式固定到硅片的表面上，制成分子信標片，利用所構(gòu)造的分子信標芯片實現(xiàn)問題的自動化求解過程。其編碼過程為：首先合成3n種短的寡聚核苷酸。將它們分為3等組，第一組的n種寡聚核苷酸分別表示變x1，x2，…xn；第2組的 n 種寡聚核苷酸分別表示變量第 3 組的 n 種寡聚核苷酸分別是第一組對應(yīng)的補鏈，并分別記為x1′，x2′，…xn′。 為了避免他們之間的錯誤雜交 ，我們選擇前兩組的寡聚核苷酸具有較大差異，至少有4個以上的不同（注意這里xi對應(yīng)的寡聚核苷酸表示變量xi取值為1，而對應(yīng)的寡聚核苷酸表示變量xi取值為0）。然后利用前2組的2n種寡聚核苷酸構(gòu)造分子信標探針，對應(yīng)的分子信標識別區(qū)分別為表示的寡聚核苷酸片段。

我們下面分五步來簡單介紹基于分子信標的0-1規(guī)劃問題的生物操作過程：（1）構(gòu)造出2n種分子信標對應(yīng)的探針，每個分子信標識別區(qū)包含n個變量對應(yīng)的寡聚核苷酸，利用雜交的方法將它們固定在表面上，使之成為一行。（2）在每個不同行對應(yīng)的分子信標探針的莖桿底部設(shè)置熒光。對應(yīng)的算法步驟2，根據(jù)約束方程的各個變量，把它們中的各個變量對應(yīng)的補鏈加到表面上，通過雜交使表面上的分子信標探針產(chǎn)生熒光，利用激光共聚焦顯微鏡觀察到某一列分子信標探針對應(yīng)的解是否滿足該約束條件。（3）對應(yīng)算法的步驟3，我們對步驟2的產(chǎn)物進行加熱解開雙鏈，沖洗掉與分子信標探針雜交的所有補鏈，（對于已經(jīng)判斷為不滿足約束條件的不再考慮）。（4）對應(yīng)算法步驟4，（我們重復(fù)步驟2,3的操作m次），我們就可以得到滿足約束方程組的可行解。（5）對應(yīng)算法的步驟5，我們對可行解所對應(yīng)的目標函數(shù)值加以比較后，就可以得到問題的最優(yōu)解。

1.2 最小頂點覆蓋問題的DNA計算模型

對于圖G＝（V，E）的結(jié)點子集K哿V，如果G的任意一條邊都至少有一個端點屬于K，則稱K為G的一個頂點覆蓋；若對任意結(jié)點V哿K，K-{V}不再是頂點覆蓋，稱K為G的極小頂點覆蓋；K是G的頂點覆蓋，且G不存在另一頂點K′滿足則稱K為G的最小頂點覆蓋；G的最小頂點覆蓋的基數(shù)稱為G的覆蓋數(shù)，記做C（G），G的頂點覆蓋常簡稱為G的覆蓋。最小頂點覆蓋問題是圖論中一個著名的NP-完全問題。2004年，王淑棟等利用表面DNA計算的方法給出了最小頂點覆蓋問題的DNA計算模型[4]。該模型的優(yōu)點是結(jié)合了圖論中的基本結(jié)論，增加了DNA計算的可操作性。但是該模型在編碼介紹上不夠清楚。2005年，董亞飛等人給出了最小頂點覆蓋問題的粘貼模型[5]。在算法中設(shè)計了熒光淬滅的有關(guān)技術(shù)，利用觀察熒光來排除非解，這種讀解方法簡單而有效且錯誤率低。由于檢測方法的改變，省略了在試管計算中常用的酶切、磁珠分離、PCR擴增、凝膠電泳等步驟，避免了在這些步驟中可能出現(xiàn)的計算誤差和數(shù)據(jù)丟失；并且我們使用的材料可重復(fù)使用，與在試管溶液中的DNA計算相比，更接近于工程實踐。但是，自然界可供我們使用的熒光素種類有限，如果DNA計算的規(guī)模便得巨大，有可能造成計算材料上的困難，該方法是DNA計算粘貼模型利用表面技術(shù)的一種嘗試。2009年，羊四清等利用基于表面的DNA計算，將圖的最小頂點覆蓋問題轉(zhuǎn)化為特殊的0-1規(guī)劃問題，將對應(yīng)于問題解空間的DNA分子固定在固體載體上，利用熒光淬滅技術(shù)，通過對每一個約束方程進行判斷，刪除所有不滿足條件的解，得到剩余解。最后比較剩余解中0的個數(shù)最多的解集都為該圖的最小頂點覆蓋[6]。

1.3 最大團與最大匹配問題的DNA計算模型

最大團問題是圖論上一重要的NP完全問題，而且它在理論和實踐上具有重要的意義。 設(shè)G=〈V，E〉是簡單無向圖，T哿V，T≠Q(mào)，若 T中任意兩個頂點都相鄰，則稱T是圖G的團。若T是圖G的團，但是任意增加一個新頂點后，它就不成為團，則稱T式圖G的極大團。2004年，李源等給出了最大團問題的DNA計算模型[7]。該算法的主要思想是首先用一個n位的二進制數(shù)表示具有n個頂點的圖的可能團，將問題轉(zhuǎn)化為求解二進制數(shù)字串中含有1最多的數(shù)字串。然后設(shè)計算法，算法計算是從空網(wǎng)開始，對應(yīng)的二進制數(shù)每一位都是0，然后讓樣本群體一代代演化。在每一代中，首先使各個二進制數(shù)的每一位以某一概率置1，然后從樣本群體中刪除在補圖中相鄰頂點對應(yīng)位置均為1的數(shù)字串。算法的生物實現(xiàn)主要是先將二進制數(shù)編碼到DNA鏈中，一個單鏈代表一個二進制數(shù)。為了編碼一個n位二進制數(shù)，共用2*n+1種不同的DNA片段，分別用n+1種不同的DNA片段序列代表n+1個位置和n代表每一位置的片段，這里表示0，1值的序列分別用不同的長度；來區(qū)別。該算法在數(shù)值為1的位置不用任何DNA片段表示，而用酶切位點取代。通過酶切刪除在補圖中相鄰頂點位置均為1的鏈，最后可以求出問題的解。

該算法的最大優(yōu)點在于將分子化思想引的入DNA算法中，而不是生成所有可能的解。因此使用了一個較小的樣本空間可以對NP問題進行求解，隨著圖的頂點數(shù)的增加，算法所需的步驟也是線性增長的。

對于最大匹配問題，同樣是一重要的NP完全問題。設(shè)G是無環(huán)圖，M哿E（G），M≠Q(mào)，如果M中任意兩條邊在G中均不相鄰，則稱M是圖G的一個匹配。若對圖G的任何匹配M′，均有則稱M為圖G的最大匹配。G中最大匹配中的邊數(shù)稱為匹配數(shù)，記作α′（G）。

2003年，劉文斌等人給出了最大匹配問題的表面DNA計算模型[8]。對于任意給定的 n 階圖 G=（V，E），令 G（E）={e1，e2，…，em}。 則其可能的匹配可以很方便的應(yīng)用m位（按照邊的順序進行編碼）二進制串來表示；若二進制串中的某位值為1，則其對應(yīng)的邊在匹配中；否則，則不在，具體的算法步驟如下：

（1）對圖G中的m位二進制串進行編碼；

（2）生成圖G的滿足條件的所有匹配。

（3）找出其中含1最多的串，即為對應(yīng)的最大匹配，并輸出結(jié)果。

本文主要思想通過表面上逐步生成解空間的過程，隨時刪除所生成的不可行解；最后，通過合適的編碼，用PCR和電泳技術(shù)可以將解集中的不同解逐步分辨出來。

1.4 圖的頂點著色問題

圖G的頂點集V（G）表示物體，G中的邊表示邊的來兩個頂點所代表的物體不能在同一類中。用顏色C表示類，用著色α表示物體的劃分：α：V（G）→C。如果C有k種顏色，則α被稱為k著色。對i∈C，集合α-1（i）被稱為第i個色類。如果對G的邊集E（G）的每一條邊xy著色 α 滿足 α（x）≠α（y），則稱 α 是一個正常著色。 如果對于某個m≤n，G可以被m種顏色正常著色，則稱G是n可著色的。使得G是n可著色的最小值n稱為G的點色數(shù)，或簡稱為色數(shù)，記為掊（G）。圖著色問題指的是給定一個n個頂點和m條邊的圖，掊（G）是多少？圖著色問題是NP-完全問題。

2006年許進等人給出了一種圖頂點著色的DNA計算模型[9]。給出了實現(xiàn)給出了實現(xiàn)20個頂點的圖頂點的3著色的DNA計算機編碼，擬以這20個頂點的圖為例進一步研究此模型的DNA計算機。在前人工作的基礎(chǔ)上，本研究針對性地提出了求解此類問題的專用型DNA計算機，不但給出了詳細的理論說明及其基本原理，并且在此思想的指導下，利用雜交反應(yīng)、磁珠分離技術(shù)以及PCR反應(yīng)等生物實驗技術(shù)，實現(xiàn)了具有5個頂點圖的3著色的DNA計算，再一次驗證了DNA計算的高度并行性，以及解決NP問題的可能性.同時從生物實驗的角度出發(fā)，進行靈敏度實驗，在此基礎(chǔ)上通過預(yù)實驗選擇合適的雜交溫度和雜交時間，確保PCR反應(yīng)的有效模板濃度，并進行了重復(fù)實驗，進而保證實驗結(jié)果的可靠性。在以前的編碼研究中，大多停留在理論研究水平，真正用于生物學實驗的并不多。 本文在前人研究的基礎(chǔ)上，認識到編碼的重要性的同時，綜合考慮化學自由能、溫度、生物酶、編碼的相似性、DNA分子的組成等對編碼的制約和影響，給出了8個約束條件，并在此基礎(chǔ)上，給出編碼的具體算法，并得到比較適合解決20個頂點的圖的頂點3著色求解的DNA序列。5個頂點圖的3著色的DNA計算所用的編碼也來源于此。

5個頂點的無向有限圖的3著色的DNA計算的生物實驗的成功，不僅豐富了DNA計算的理論，而且在實驗過程中摸索到的實驗條件都可以為進一步深入研究圖頂點著色問題提供參考，甚至對其他問題的DNA計算都有很大的意義.但是本實驗依然存在不足，實驗過程耗時較長，溶液中DNA鏈的損失較大，還應(yīng)從選擇更適用的實驗方法和手段，以及尋找更具有普適性的編碼方案等方面繼續(xù)深入研究。

2 面臨的問題

雖然，DNA計算有了很大的發(fā)展，但是還是存在一些不足之處，理論和實際操作方面都還面臨著一系列的挑戰(zhàn)。在生化反應(yīng)操作的過程中容易出錯。特別是在進行雜交時容易出錯。計算精度不能夠得到確保，因為核酸酶的降解效率不夠高；DNA的計算規(guī)模還受到限制；所以對于DNA計算機來說，一些問題還需要及時進行解決。（1）怎樣才能夠把誤差降到最低，因為在進行生物操作的提取和退火步驟中，會產(chǎn)生誤差。（2）怎樣更好的對獲得的結(jié)果進行檢索？大量DNA聚集在一起，因為發(fā)生退火反應(yīng)以至于產(chǎn)生“偽解”。（3）怎樣才可以盡量避免錯誤地雜交？（4）怎樣才可以進行正確的編碼？隨著用于編碼的寡聚核苷酸鏈長度的增加，編碼的復(fù)雜度也隨著增加，容易產(chǎn)生發(fā)夾結(jié)構(gòu)。（5）在進行實際操作時，怎樣才能夠建立更好的模型，使問題得到有效解決？[10]。

3 進一步的研究方向

從1994年Adleman提出計算機模型以來，DNA計算的研究內(nèi)容有了很大的發(fā)展：DNA芯片的研制、DNA計算模型的構(gòu)造、DNA計算和納米技術(shù)的結(jié)合，計算模擬和序列設(shè)計等。DNA計算可以分為大致以下幾個研究方面：

（1）解的檢測。如何將溶液狀態(tài)下產(chǎn)生的眾多解（DNA鏈）中代表所求問題最終解的DAN鏈分離出來，尋找合理、有效地分離方法。

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

（3）生化試驗的研究。DNA計算的研究的最終目標是構(gòu)造DNA計算機，這就必須能進行生化試驗?，F(xiàn)有的DNA計算模型大部分都是理論研究，是否可以通過生化試驗進行實現(xiàn)還有待進一步研究，生化試驗不僅可以驗證算法的優(yōu)劣而且可以為進一步研究提供不斷地改進方案。因此，我們認為即使對現(xiàn)有的DNA計算模型進行生化實驗的研究都是有意義的。

雖然DNA計算現(xiàn)在還存在一些問題，但是DNA計算作為一個新興的研究領(lǐng)域，已經(jīng)得到了廣泛應(yīng)用，而且已用來解決了很多實際問題?，F(xiàn)在科學家對DNA的研究和發(fā)展抱有很大信心。它使人們首次認識到生物中存在的基本算法，總之，DNA計算機和DNA計算有著巨大的發(fā)展?jié)摿Α?/p>

［1］高琳,許進,張軍英.DNA 計算的研究進展與展望[J].電子學報,2001,29(1)：973-977.

［2］殷志祥,許進.分子信標芯片計算在0-1整數(shù)規(guī)劃問題中的應(yīng)用[J].生物數(shù)學學報,2007,22(3)：559-564.

［3］殷志祥,張鳳月,許進.基于分子信標的DNA計算[J].生物數(shù)學學報,2003,18(4)：497-501.

［4］王淑棟,許進,董亞飛.圖的最小頂點覆蓋問題的面上DNA解法[J].小型微型計算機系統(tǒng),2004,25(2)：242-244.

［5］董亞飛,張家秀,殷志祥,許進.最小頂點覆蓋問題的改進粘貼模型[J].電子與信息學報,2005,27(4)：556-560.

［6］羊四清,李小龍,袁輝勇.圖的最小頂點覆蓋問題DNA表面計算模型[J].計算機工程與應(yīng)用,2009,45(6)：69-72.

［7］劉文斌,高琳,王淑棟.最大匹配問題的 DNA表面計算模型[J].電子學報,2003,31(10)：1496-1499

［8］李源,方辰,歐陽頎.最大集團問題的 DNA計算機進化算法[J].科學通報,2004,49(5)：439-443.

［9］許進,強小莉,方剛,等.一種圖頂點著色 DNA計算機模型[J].科學通報.,2006,51(4)：480-487.

［10］殷志祥,張家秀.圖論中的DNA計算模型[J].系統(tǒng)工程與電子技術(shù),2007,29(7)：1159-1163.

［11］李魯華,吐爾根.依布拉音.DNA計算的原理及應(yīng)用[J.應(yīng)用技術(shù),2005.

［12］殷志祥.圖與組合優(yōu)化中的DNA計算[M].北京：科學出版社,2004.