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