第1章DNA計算的產(chǎn)生與發(fā)展
　　DNA（deoxyribonucleic acid）計算是借助于分子生物技術(shù)進行計算的新方法，憑借極大的存儲密度和高度并行性，DNA計算為求解NP完全問題等復(fù)雜組合優(yōu)化問題，提供了一種全新的途徑，開創(chuàng)了廣闊的應(yīng)用前景。DNA編碼質(zhì)量的優(yōu)劣決定了DNA計算的效率，DNA編碼數(shù)量的多少決定了DNA計算可求解問題的規(guī)模，因此核酸編碼是DNA計算研究中的重要課題。
　　隨著20世紀70年代初期計算復(fù)雜性理論的形成，科學(xué)工作者發(fā)現(xiàn)并證明了大量來源于實際的組合優(yōu)化問題是非常難求解的問題，即NP完全問題和NP難問題。20世紀80年代初期，應(yīng)運而生了一系列現(xiàn)代優(yōu)化計算方法，如模擬退火算法、遺傳算法、蟻群優(yōu)化算法、粒子群算法和人工神經(jīng)網(wǎng)絡(luò)算法等。這類算法中的每一個算法都以自然、人類、生物的行為方式或物質(zhì)運動形態(tài)為背景，經(jīng)過數(shù)學(xué)抽象建立算法模型，通過電子計算機來求解組合優(yōu)化問題。然而，這些基于仿生計算的優(yōu)化計算方法不能在有效的時間中找到最優(yōu)解，而用次優(yōu)可行解來代替最優(yōu)解；即使算法找到了最優(yōu)解，算法本身也并不能證明其是最優(yōu)解。因此這一系列建立在模仿分子運動、遺傳學(xué)、動物學(xué)、神經(jīng)系統(tǒng)的現(xiàn)代優(yōu)化算法并不能徹底解決復(fù)雜的組合優(yōu)化問題。
　　DNA計算是一種基于DNA分子的并行計算模型，是在計算科學(xué)和分子生物學(xué)的基礎(chǔ)上發(fā)展起來的一個新穎而極具發(fā)展?jié)摿Φ慕徊鎸W(xué)科，這種基于生物分子的計算模式在求解NP完全問題時顯示出了極大潛力。
　　1994年，美國南加州大學(xué)的Adleman\[1\]用DNA分子進行計算，求解出7個頂點的有向Hamilton路問題，成功地利用現(xiàn)代分子生物技術(shù)在DNA溶液的試管中進行了實驗。這一研究成果很快引起了計算機、數(shù)學(xué)、分子生物學(xué)等領(lǐng)域的科學(xué)家的極大興趣。它的重要意義不僅在于算法和速度，更在于采用了一種全新的介質(zhì)作為計算要件，以生物技術(shù)來實現(xiàn)電子計算機無法解決的復(fù)雜組合優(yōu)化問題。隨后，在1995年召開的第一屆國際DNA計算會議上，來自各個國家和地區(qū)的200多名科學(xué)家共同探討并充分肯定了DNA計算機的可行性。該領(lǐng)域的專家普遍認為：一旦DNA計算機研制成功，其運算量是目前的傳統(tǒng)計算機望塵莫及的，DNA計算是一個極具開發(fā)價值的研究領(lǐng)域。與傳統(tǒng)的電子計算機相比，DNA計算機具有三個突出的優(yōu)點：高度并行性、海量的存儲能力、極低的能耗。
　　然而，當(dāng)前DNA分子的操作技術(shù)的發(fā)展遠不如電子計算機中的集成電路成熟。在DNA計算過程中，DNA分子間會發(fā)生非特異性雜交，導(dǎo)致實驗出現(xiàn)錯誤甚至失敗，極大降低DNA計算的可靠性和有效性。對DNA序列進行編碼設(shè)計是DNA計算機研制中最為核心的問題。首先，編碼質(zhì)量的優(yōu)劣決定了DNA計算的可靠性和有效性，直接影響著DNA計算能否按照預(yù)期的設(shè)計相互反應(yīng)；其次，編碼數(shù)量的多少決定了DNA計算求解問題規(guī)模的大小，與DNA計算機研究能否深入發(fā)展息息相關(guān)。所以，本書在詳細分析編碼質(zhì)量和編碼數(shù)量的主要影響因素的基礎(chǔ)上，對DNA計算機中的編碼問題及其算法進行了深入研究。
　　DNA計算的基本思想：DNA計算是以DNA相關(guān)的生物酶等作為基本材料，基于生化反應(yīng)原理的一種新型的分子生物計算方法。利用DNA特殊的雙螺旋結(jié)構(gòu)和堿基互補配對規(guī)律進行信息編碼，把要運算的對象映射成DNA分子鏈，然后在生物酶的作用下，按照一定的規(guī)則將原始問題的數(shù)據(jù)運算映射成高度并行的DNA分子鏈可控的生化反應(yīng)。最后，利用分子生物技術(shù)如聚合酶鏈反應(yīng)（PCR）、超聲波降解、親和層析、克隆、誘變、分子純化、電泳、磁珠分離等，檢測所需要的運算結(jié)果。DNA計算的關(guān)鍵是將經(jīng)過編碼的DNA分子作為輸入，在試管內(nèi)或其他載體上經(jīng)過一定時間完成可控的生物化學(xué)反應(yīng)，最后提取出代表問題解的DNA分子。
　　1994年Adleman求解7個頂點有向Hamiltion路的實驗解釋了DNA計算過程的三個基本步驟，其有向圖G如圖1.1所示。
　　圖1.1有向圖G存在唯一Hamiltan路v0→v1→v2→v3→v4→v5→v6
　　(1) 有向圖的每一個頂點都編碼為唯一的DNA分子，有向圖的每一條邊用相鄰兩頂點的DNA分子補鏈各取一半組成。
　　(2) 在一定的反應(yīng)條件下，代表頂點和代表邊的DNA分子相互雜交，相互連接形成長的DNA分子，產(chǎn)生這個有向圖的路徑。
　　(3)最后檢測出代表該Hamiltion路的DNA分子。具體計算過程如下。
　　（1）解的產(chǎn)生。首先將圖1.1中各頂點vi用長度為20個堿基的單鏈DNA(Oi)來代替，vi和Oi一一對應(yīng)。若頂點vi和vj之間存在邊e(i，j)，再根據(jù)Oi，Oj來合成圖中各條邊Oi→j，Oi→j同樣由長度為20個堿基的單鏈DNA構(gòu)成，前10個堿基取Oi的3′端10個堿基，后10個堿基取Oj的5′端10個堿基。這種DNA序列設(shè)計使得如果存在路徑i→j和j→k，通過添加Oj的補鏈Oj，可以產(chǎn)生路徑i→j→k。
　　如圖1.2所示，以產(chǎn)生路徑2→3→4為例，O2、O3、O4分別為20個堿基組成的單鏈DNA，代表v2、v3、v4三個頂點，O3是O3的補鏈。單鏈DNAO2→3和O3→4代表該有向圖的邊e(2，3)和e(3，4)。其中O2→3由O2的3′端10個堿基和O3的5′端10個堿基組成，O3→4由O3的3′端10個堿基和O4的5′端10個堿基組成。在O2→3和O3→4共同存在的DNA溶液中，加入一定濃度的O3，則代表路徑2→3→4的雙鏈DNA 就產(chǎn)生了。依此類推，當(dāng)這一步連接反應(yīng)包括了圖1.1中所有的邊e(i，j)時，圖1.1中所有隨機路徑的DNA就可以在一步之間全部產(chǎn)生了。
　　圖1.2產(chǎn)生DNA分子Hamiltion路徑2→3→4
　�。�2） 解的分離。在第（1）步中產(chǎn)生了各種路徑，首先需要選出起點和終點分別為O0和O6的路徑。使用O0和O′6作為引物，利用PCR對第（1）步的結(jié)果進行擴增，就能選擇性地擴增那些從O0至O6的DNA路徑。PCR擴增完畢后，DNA溶液中存在以O(shè)0為起點、O6為終點的不同長度的雙鏈DNA，如圖1.3所示。
　　圖1.3以0開始6結(jié)尾的所有路徑
　　由于從O0開始，每增加一個頂點，該雙鏈DNA的長度就增加20個堿基。通過所有7個頂點的DNA路徑，對應(yīng)的堿基個數(shù)必須為140bp。通過凝膠電泳技術(shù)，在電鏡下觀察得到140個堿基對應(yīng)的譜帶，割下這條膠帶，浸入雙蒸水中提取DNA。（3） 解的檢測。第（2）步得到了長度為140bp的DNA溶液，還要選出其中經(jīng)過每個頂點各一次的DNA路徑，如圖1.4所示。應(yīng)用親和純化法，選出經(jīng)過所有頂點至少一次的DNA路徑。先將DNA雙鏈解開雙螺旋成單鏈DNA，讓其通過接有O1補的磁珠，只有含有O1序列的單鏈DNA才能由于互補鏈的結(jié)合而被滯留，這個操作分離出了經(jīng)過O1的DNA。這樣依次通過接有O2補、O3補、O4補和O5補的磁珠，最終得到了經(jīng)過所有頂點至少一次的Hamilton路DNA分子。
　　圖1.4以0開始6結(jié)尾的等長DNA鏈通過磁珠
　　將第（3）步的產(chǎn)物再進行PCR擴增，通過DNA測序等方法，檢測目標(biāo)DNA是否存在即可。1997年Garzon等\[2\]歸納了使用DNA分子解決計算問題的三個基本步驟：①問題編碼(encoding)，這個步驟將現(xiàn)實計算問題映射轉(zhuǎn)換為DNA分子計算模型；②相互反應(yīng)(interaction)，這個步驟將設(shè)計好的DNA分子在一定溫度、鹽度和催化劑的作用下執(zhí)行核心的生化計算；③解的提取(extraction)，這個步驟利用生物檢測技術(shù)將代表解的DNA分子提取出來，使納米級的DNA分子在宏觀世界可見。
　　1.1國內(nèi)外研究進展
　　Adleman實驗的成功標(biāo)志著科學(xué)家試圖利用生物大分子(DNA、RNA、蛋白質(zhì)等)來解決電子計算機無法求解的NP完全問題和構(gòu)建新型的計算機的設(shè)想取得了重要突破，使DNA計算成為一個備受關(guān)注的學(xué)科，也使構(gòu)建新型的計算機——DNA計算機成為可能。隨后，國內(nèi)外學(xué)者在Adleman 的分子計算模型基礎(chǔ)上廣泛開展了DNA 計算的研究工作，建立了一系列求解NP完全問題的DNA計算模型，如SAT、圖著色、0-1規(guī)劃、背包問題等計算問題的DNA 計算模型。1995年，受Adleman的啟發(fā)，Lipton\[3\]提出DNA計算可以解決另一種NP完全問題——可滿足性問題(SAT)。Lipton通過構(gòu)造一個接觸網(wǎng)絡(luò)圖，將SAT問題的解空間映射為通過接觸網(wǎng)絡(luò)圖的起點和終點的所有哈密頓路。他首先利用DNA分子表示問題的所有可能解，然后利用生化反應(yīng)刪除非解。1996年，Roweis等介紹了一種新的DNA計算模型——粘貼模型，并用此模型解決了最小集合覆蓋問題和數(shù)據(jù)加密問題。1997年，Ouyang等將另一個NP完全問題——圖的最大團問題轉(zhuǎn)化為最大獨立集問題，利用并行重疊組裝(parallel overlap assembly，POA)技術(shù)在實驗室解決了一個6個頂點的最大團問題實例。1998年，Winfree等\[4\]設(shè)計出雙交叉瓦片（tile)分子DX，利用到DNA 分子間的堿基互補配對特性，由幾條DNA 單鏈在特定位置互補，交錯位置而形成分子結(jié)構(gòu)，如圖1.5所示。Winfree發(fā)現(xiàn)以DX分子作為組件可以實現(xiàn)規(guī)則結(jié)構(gòu)的自組裝。
　　圖1.5Winfree自組裝模型