DNA計算在求解NP-完全問題的應用

周金鳳

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

0 引言

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

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

1 NP-完全問題

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

1.1 0-1規劃問題的DNA計算模型

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

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

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

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

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

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

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

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

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

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

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

（3）找出其中含1最多的串，即為對應的最大匹配，并輸出結果。

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

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的點色數，或簡稱為色數，記為掊（G）。圖著色問題指的是給定一個n個頂點和m條邊的圖，掊（G）是多少？圖著色問題是NP-完全問題。

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

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

2 面臨的問題

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

3 進一步的研究方向

從1994年Adleman提出計算機模型以來，DNA計算的研究內容有了很大的發展：DNA芯片的研制、DNA計算模型的構造、DNA計算和納米技術的結合，計算模擬和序列設計等。DNA計算可以分為大致以下幾個研究方面：

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

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

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

雖然DNA計算現在還存在一些問題，但是DNA計算作為一個新興的研究領域，已經得到了廣泛應用，而且已用來解決了很多實際問題。現在科學家對DNA的研究和發展抱有很大信心。它使人們首次認識到生物中存在的基本算法，總之，DNA計算機和DNA計算有著巨大的發展潛力。

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

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

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

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

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

［6］羊四清,李小龍,袁輝勇.圖的最小頂點覆蓋問題DNA表面計算模型[J].計算機工程與應用,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].系統工程與電子技術,2007,29(7)：1159-1163.

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

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