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

周金鳳

（安徽理工大學(xué) 安徽 淮南 232001）

0 引言

電子計(jì)算機(jī)的快速發(fā)展，在很大程度上促進(jìn)了優(yōu)化計(jì)算問題的解決。但是，電子計(jì)算機(jī)運(yùn)算速度不夠快，存貯容量不夠大。而且隨著現(xiàn)代社會(huì)科學(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)注。它的進(jìn)步之處不僅僅在于其存儲(chǔ)量和運(yùn)算速度的改善，更重要的是他開發(fā)了本身潛在的計(jì)算能力。實(shí)踐證明，DNA計(jì)算機(jī)在計(jì)算速度和存儲(chǔ)容量等方面確實(shí)有很大的進(jìn)展。

DNA計(jì)算的基本思想是：利用DNA特殊的雙螺旋結(jié)構(gòu)和堿基互補(bǔ)配對(duì)規(guī)律進(jìn)行信息編碼，把要運(yùn)算的對(duì)象映射成DNA分子鏈，在生物酶的作用下，生成各種數(shù)據(jù)池，然后按照一定的規(guī)則將原始問題的數(shù)據(jù)運(yùn)算高度并行地映射成DNA分子鏈的可控的生化過程。最后，利用分子生物技術(shù)如聚合鏈反應(yīng)PCR、超聲波降解、親和層分析、克隆、誘變、分子純化、電泳、磁珠分離等，檢測(cè)所需的運(yùn)算結(jié)果。最早的計(jì)算機(jī)模式是由Alderman博士在1994首先提出的。而后，對(duì)于DNA計(jì)算機(jī)領(lǐng)域的研究引起了各科學(xué)等領(lǐng)域研究者的廣泛關(guān)注。DNA計(jì)算研究的最終目的是構(gòu)造出具有巨大并行性的DNA計(jì)算機(jī)。國(guó)內(nèi)開始DNA計(jì)算的研究始于1996年。到目前為止，我國(guó)關(guān)于DNA計(jì)算的研究大致可以分為3個(gè)階段，學(xué)習(xí)階段、理論研究階段、理論與實(shí)驗(yàn)研究階段[1]。自2001年開始，國(guó)內(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ì)算問題上，特別是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è)難于處理的問題。對(duì)于它，要找出一個(gè)在計(jì)算機(jī)上可行的（即多項(xiàng)式時(shí)間的）算法是十分困難的，甚至可能根本找不到(因?yàn)楹芸赡苡?NP≠P)。利用DNA計(jì)算模型解決了許多NP-完全問題，DNA計(jì)算是一種模擬生物分子并借助于分子生物技術(shù)進(jìn)行計(jì)算的新方法，開創(chuàng)了以化學(xué)反應(yīng)作為計(jì)算工具的先例，為解決NP-完全問題提供了一種全新的途徑，DNA計(jì)算的實(shí)現(xiàn)方式可以分為3種：試管、表面、芯片，試管方式是DNA計(jì)算的初級(jí)階段，目的是驗(yàn)證算法的可行性；表面方式是從試管走向芯片的過渡階段；芯片方式是DNA計(jì)算最終成功的標(biāo)志。下面幾節(jié)中將較為詳細(xì)的介紹國(guó)內(nèi)關(guān)于NP-完全問題中的DNA研究成果。

1 NP-完全問題

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

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

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

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

1.2 最小頂點(diǎn)覆蓋問題的DNA計(jì)算模型

對(duì)于圖G＝（V，E）的結(jié)點(diǎn)子集K哿V，如果G的任意一條邊都至少有一個(gè)端點(diǎn)屬于K，則稱K為G的一個(gè)頂點(diǎn)覆蓋；若對(duì)任意結(jié)點(diǎn)V哿K，K-{V}不再是頂點(diǎn)覆蓋，稱K為G的極小頂點(diǎn)覆蓋；K是G的頂點(diǎn)覆蓋，且G不存在另一頂點(diǎn)K′滿足則稱K為G的最小頂點(diǎn)覆蓋；G的最小頂點(diǎn)覆蓋的基數(shù)稱為G的覆蓋數(shù)，記做C（G），G的頂點(diǎn)覆蓋常簡(jiǎn)稱為G的覆蓋。最小頂點(diǎn)覆蓋問題是圖論中一個(gè)著名的NP-完全問題。2004年，王淑棟等利用表面DNA計(jì)算的方法給出了最小頂點(diǎn)覆蓋問題的DNA計(jì)算模型[4]。該模型的優(yōu)點(diǎn)是結(jié)合了圖論中的基本結(jié)論，增加了DNA計(jì)算的可操作性。但是該模型在編碼介紹上不夠清楚。2005年，董亞飛等人給出了最小頂點(diǎn)覆蓋問題的粘貼模型[5]。在算法中設(shè)計(jì)了熒光淬滅的有關(guān)技術(shù)，利用觀察熒光來排除非解，這種讀解方法簡(jiǎn)單而有效且錯(cuò)誤率低。由于檢測(cè)方法的改變，省略了在試管計(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ī)劃問題，將對(duì)應(yīng)于問題解空間的DNA分子固定在固體載體上，利用熒光淬滅技術(shù)，通過對(duì)每一個(gè)約束方程進(jìn)行判斷，刪除所有不滿足條件的解，得到剩余解。最后比較剩余解中0的個(gè)數(shù)最多的解集都為該圖的最小頂點(diǎn)覆蓋[6]。

1.3 最大團(tuán)與最大匹配問題的DNA計(jì)算模型

最大團(tuán)問題是圖論上一重要的NP完全問題，而且它在理論和實(shí)踐上具有重要的意義。 設(shè)G=〈V，E〉是簡(jiǎn)單無向圖，T哿V，T≠Q(mào)，若 T中任意兩個(gè)頂點(diǎn)都相鄰，則稱T是圖G的團(tuán)。若T是圖G的團(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)開始，對(duì)應(yīng)的二進(jìn)制數(shù)每一位都是0，然后讓樣本群體一代代演化。在每一代中，首先使各個(gè)二進(jìn)制數(shù)的每一位以某一概率置1，然后從樣本群體中刪除在補(bǔ)圖中相鄰頂點(diǎn)對(duì)應(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種不同的DNA片段序列代表n+1個(gè)位置和n代表每一位置的片段，這里表示0，1值的序列分別用不同的長(zhǎng)度；來區(qū)別。該算法在數(shù)值為1的位置不用任何DNA片段表示，而用酶切位點(diǎn)取代。通過酶切刪除在補(bǔ)圖中相鄰頂點(diǎn)位置均為1的鏈，最后可以求出問題的解。

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

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

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

（1）對(duì)圖G中的m位二進(jìn)制串進(jìn)行編碼；

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

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

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

1.4 圖的頂點(diǎn)著色問題

圖G的頂點(diǎn)集V（G）表示物體，G中的邊表示邊的來兩個(gè)頂點(diǎn)所代表的物體不能在同一類中。用顏色C表示類，用著色α表示物體的劃分：α：V（G）→C。如果C有k種顏色，則α被稱為k著色。對(duì)i∈C，集合α-1（i）被稱為第i個(gè)色類。如果對(duì)G的邊集E（G）的每一條邊xy著色 α 滿足 α（x）≠α（y），則稱 α 是一個(gè)正常著色。 如果對(duì)于某個(gè)m≤n，G可以被m種顏色正常著色，則稱G是n可著色的。使得G是n可著色的最小值n稱為G的點(diǎn)色數(shù)，或簡(jiǎn)稱為色數(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)的圖頂點(diǎn)的3著色的DNA計(jì)算機(jī)編碼，擬以這20個(gè)頂點(diǎn)的圖為例進(jìn)一步研究此模型的DNA計(jì)算機(jī)。在前人工作的基礎(chǔ)上，本研究針對(duì)性地提出了求解此類問題的專用型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é)果的可靠性。在以前的編碼研究中，大多停留在理論研究水平，真正用于生物學(xué)實(shí)驗(yàn)的并不多。 本文在前人研究的基礎(chǔ)上，認(rèn)識(shí)到編碼的重要性的同時(shí)，綜合考慮化學(xué)自由能、溫度、生物酶、編碼的相似性、DNA分子的組成等對(duì)編碼的制約和影響，給出了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)條件都可以為進(jìn)一步深入研究圖頂點(diǎn)著色問題提供參考，甚至對(duì)其他問題的DNA計(jì)算都有很大的意義.但是本實(shí)驗(yàn)依然存在不足，實(shí)驗(yàn)過程耗時(shí)較長(zhǎng)，溶液中DNA鏈的損失較大，還應(yīng)從選擇更適用的實(shí)驗(yàn)方法和手段，以及尋找更具有普適性的編碼方案等方面繼續(xù)深入研究。

2 面臨的問題

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

3 進(jìn)一步的研究方向

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

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

（2）降低空間復(fù)雜度。由于表面（固體狀態(tài)）計(jì)算是將時(shí)間復(fù)雜性轉(zhuǎn)化為空間復(fù)雜性，因此如何降低時(shí)間復(fù)雜性轉(zhuǎn)化時(shí)的空間復(fù)雜性就顯得非常重要。而如何降低空間復(fù)雜性牽涉到算法設(shè)計(jì)和編碼。因此進(jìn)一步研究DNA計(jì)算中的算法是非常重要的一個(gè)研究?jī)?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)的成敗。

（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)為即使對(duì)現(xiàn)有的DNA計(jì)算模型進(jìn)行生化實(shí)驗(yàn)的研究都是有意義的。

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

［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解法[J].小型微型計(jì)算機(jī)系統(tǒng),2004,25(2)：242-244.

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

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

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

［8］李源,方辰,歐陽頎.最大集團(tuán)問題的 DNA計(jì)算機(jī)進(jìn)化算法[J].科學(xué)通報(bào),2004,49(5)：439-443.

［9］許進(jìn),強(qiáng)小莉,方剛,等.一種圖頂點(diǎn)著色 DNA計(jì)算機(jī)模型[J].科學(xué)通報(bào).,2006,51(4)：480-487.

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

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

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