熱心網友

1 DNA計算的理論、特點和問題 1994年11月美國計算機科學家 L．阿德勒曼（L．Adleman）在《科學》上公布了DNA計算機的理論，并成功的運用DNA計算機解決了一個有向哈密爾頓路徑問題[1]。這一成果迅速在國際上產生了巨大反響[2]，同時也引起了國內學者的關注[3]。一些人相信，DNA計算蘊含的理念可使計算的方式產生“進化”。另一些人則看到DNA計算的理念將有助于揭示生命的本質與演化。總之，這一全新的計算理論，將在數學與生命科學中產生極其深遠而廣大的影響。同時它也提出了一系列值得我們深思的哲學性問題。DNA計算機目前尚處在理論研究階段，一旦它在實用意義上獲得成功，DNA計算將徹底改變計算機硬件的性質。在過去的半個世紀里，計算機完全就是物理芯片的同義詞。但阿德勒曼DNA計算機則是一種化學反應計算機[4]。它的基本構想是：以DNA堿基序列作為信息編碼的載體，利用現代分子生物學技術，在試管內控制酶作用下的DNA序列反應，作為實現運算的過程；這樣，以反應前DNA序列作為輸入的數據，反應后的DNA序列作為運算的結果。阿德勒曼具體應用哈密爾頓有向圖這個經典NPC問題，詳細描述了他的理論。DNA計算機的提出，產生于這樣一個發現，即生物與數學的相似性：①生物體異常復雜的結構是對由DNA序列表示的初始信息執行簡單操作（復制、剪接）的結果；②可計算函數f（w）的結果可以通過在w上執行一系列基本的簡單函數而獲得。阿德勒曼不僅意識到這兩個過程的相似性，而且意識到可以利用生物過程來模擬數學過程，更確切地說是，DNA串可用于表示信息，酶可用于模擬簡單的計算。這是因為：①DNA是由稱作核苷酸的一些單元組成，這些核苷酸隨著附在其上的化學組或基的不同而不同。共有四種基：腺瞟吟、鳥瞟吟、胞嘧啶和胸腺嘧啶，分別用A、G、C、T表示。一些單個的核苷酸順序連在一起形成DNA鏈。單鏈DNA可以看作是由符合A、G、C、T組成的字符串。從數學上講，這意味著我們可以用一個含有四個字符的字符集∑＝A、G、C、T來為信息編碼（電子計算機僅使用0和1這兩個數字）。②DNA序列上的一些簡單操作需要酶的協助，不同的酶發揮不同的作用。起作用的有四種酶：a．限制性內切酶，主要功能是切開包含限制性位點的雙鏈DNA；b．DNA連接酶，它主要是把一個DNA鏈的端點同另一個鏈連接在一起；c．DNA聚合酶，它的功能包括DNA的復制與促進DNA的合成；d．外切酶，它可以有選擇地破壞雙鏈或單鏈DNA分子。正是基于這四種酶的協作實現了DNA計算。 自阿德勒曼用DNA計算機解決了哈密爾頓有向圖問題，隨后很快便有人用DNA計算機相繼解決了其他一些疑難問題（NPC完全問題），如可滿足性問題等。與電子計算機相比，DNA計算機有明顯的優勢。不過，這些還僅僅是利用分子技術解決的幾個特定問題，是為解決特定問題而進行的一次性實驗。DNA計算機還沒有一個固定的程式。由于問題的多樣性導致所采用的分子生物學技術的多樣性，具體問題需要設計具體的實驗方案。于是，便引出了兩個根本性的問題，阿德勒曼最早就意識到了它們：①DNA計算機可以解決哪些問題？確切地說，DNA計算機是完備的嗎？即通過操縱DNA能完成所有的（圖靈機）可計算函數嗎？②是否可設計出可編程序的DNA計算機？即是否存在類似于電子計算機的通用計算模型——圖靈機——那樣的通用DNA系統（模型）？目前，人們正處在對這兩個根本性問題的研究過程之中。在我們看來，這就類似于在電子計算機誕生之前的20世紀三四十年代——理論計算機的研究階段。如今，已經提出了多種DNA計算模型，但各有千秋，公認的DNA計算機的“圖靈機”還沒有誕生。相對而言，一種被稱為“剪接系統”的DNA計算機模型較為成功[5]。 由于DNA鏈可以比作在四字符集上的串，為DNA計算建模的自然方式就是利用專門處理字符和字符串的形式語言理論。建模的關鍵就是要將實際的DNA重組抽象為數學上的剪接操作。實際的DNA重組，就是在前面所提到的四種“工具酶”的作用下，對DNA鏈的切割和粘貼的組合過程。其數學抽象稱為剪接操作。大體可做如下描述：給定字符集∑（其元素為符號）及其上的兩個字符串x、y，利用剪接規則r剪接x和y的過程可以分為：①在由剪接規則r決定的位置上切割x和y；②分別將結果中x的前段和y的后段、y的前段和x的后段連在一起。∑ 的剪接規則 r是形如α1#β1$α2#β2的詞，其中α1、β1、α2、β2是∑的串，＃和$是∑外的標記符。我們稱z和w是根據剪接規則r＝α1#β1$α2#β2剪接x和y的結果，當且僅當存在∑上的x1、xƇ、y2、yƈ使得x=x1α1β1xƇ, y＝y2α2β2yƈ且 z=x1α1β2yƈ, w=y2α2β1xƇ并記作（x，y） →（z，w）。α1β1和α2β2這兩個串稱為剪接位點；x和y稱為剪接項。剪接規則r決定了切割的位點和位置：第一項在α1和β1之間，第二項在α2和β2之間。值得注意的是位點α1β1和α2β2會分別在x和y中出現多次，如果這樣，選擇哪一個位點是不確定的。結果會造成對x和y剪接的結果是（z，w）的一個集合。 將剪接操作當作基本工具來構建一種生成機制，便形成了剪接系統。給定一個字符串集A,A∑*,∑*為字符集∑上由連接操作生成的字符串的集合（∑*中的元素為串），以及一個剪接現則集R（r∈R∑*＃∑*$∑*＃∑*），由此所生成的東西是由如下方法得到的串組成；從集A開始，在A和已獲得的串上重復使用剪接規則。另外，應該說明一點，通常剪接x和y得到z和w后，仍可以將x和y當作剪接項，與此相似，對新生成的z和x也沒有數量上的限制。但對某些串僅可使用有限次。故在數學上不用集合來表示剪接項，而用多重集——在每個時刻都應當記錄每個串可用的個數。至此，可以給出剪接系統的一個簡潔而又嚴格的定義：剪接系統是一個四元組r＝（∑、T、A、R），其中∑是一個字符集，T ∑是終結字符集，A是∑*上的多重集，R是剪接規則的集合。定義了DNA計算的數學模型后，便可以來回答前面提出的DNA計算的完備性與通用性問題。在計算機科學中，眾所周知的丘奇一圖靈論點深刻地刻畫了任何實際計算機的計算能力——任何可計算函數都是可由圖靈機計算的函數（一般遞歸函數）。現已證明：剪接系統是計算完備的，即任何可計算函數都可以用剪接系統來計算。換句話說就是，任何圖靈機可計算的函數都可以由這種DNA計算模型來計算。反之亦然。這就回答了DNA計算機可以解決哪些問題——全部圖靈機可計算問題。 對于第二個問題——是否存在基于剪接的可編程計算機——也有了肯定的答案：對每個給定的字符集T，都存在一個剪接系統，其公理集和規則集都是有限的，而且對于以T為終結字符集的一類系統是通用的。這就是說，理論上存在一個基于剪接操作的通用可編程的DNA計算機。程序由往通用計算機公理集中添加的字符串組成。程序會有多個，而可利用的公理集合有無窮多個。這些計算機使用的生物操作只有合成、剪接（切割一連接）和抽取。 理論上DNA計算機具有現代電子計算機同樣的計算能力，但它具有的巨大潛力（功能）卻是電子計算機不可比擬的：DNA計算機運算速度極快，其幾天的運算量就相當于計算機問世以來世界上所有計算機的總運算量；它的貯存容量非常大，1立方分米的DNA溶液可以存儲1萬億億位二進制的數據，超過目前所有計算機的存儲容量；它的能量消耗只有一臺普通計算機的十億分之一。如此優越的分子計算機當然是激動人心的。然而它離開發、實際應用還有相當的距離，尚有許多現實的技術性問題需要去解決。如生物操作的困難，有時輕微的振蕩就會使DNA斷裂；有些DNA會粘在試管壁、抽筒尖上，從而就在計算中丟失了。盡管DNA計算機面對著許許多多的質疑，但它的提出者阿德勒曼教授依然是極其樂觀的：DNA計算機剛剛提出，尚在胚胎時期，與發展了半個世紀的電子計算機相比，確實相形見細。在他看來，提出DNA計算機并不就是要與電子計算機競爭。首先，分子計算的觀念拓寬了人們對自然計算現象的理解，特別是生物學中基本算法的理解。另外，DNA計算的觀念向現有的計算機科學和數學提出了挑戰，相信它所蘊涵的理念可以使計算的方式發生進化。 DNA計算理論是目前西方發達國家的一個研究熱點，有些困難已經通過新的程序設計技術（無須等待生物技術的發展），采用概率算法及修改數學問題等傳統的解決方案得以解決。人們大都相信，分子計算的實際應用在未來是可行的。另外，要知道，類似合成雜交、抽取等所有生物操作的問題，都已被大自然中的生物系統所涉及，而且這些問題在生物體內已成功的解決了，這就不會在生物體外解決不了。向大自然學習，問題就會得到解決。2 DNA計算：計算方式的進化 1994年11月阿得勒曼在提出DNA計算機的時候就相信：DNA計算機所蘊涵的理念可使計算的方式產生進化。后來的研究者就更堅信這一點了。如加拿大的卡爾（L．Kari）就更明確的指出：“DNA計算是考察計算問題的一種全新的方式。或許這正是大自然做數學的方法：不是用加和減，而是用切割和粘貼、用插入和刪除。正如用十進制計數是因為我們有十個手指那樣，或許我們目前計算中的基本功能僅因為人類歷史使然。正如人們已經采用其它進制計數一樣，或許現在是考慮其它的計算方式的時候了”[6]。我們以為，這一說法是很有啟示性的。確實，仔細回顧一下人類計算方式或計算技術的歷史，就不難體會到目前人們的計算方式確實是一種歷史的結果，而非計算本性的邏輯必然。不過為了進一步論證和拓展這一觀點，下面有必要就什么是計算。計算的方式是什么等問題給予一個簡要的回答。 計算的本質是什么？應該說人類對其已經有了一個基本的清晰的認識，這就是遞歸論或可計算性理論中所揭示的一個基本內容：計算就是依據一定的法則對有關符號串的變換過程。根據丘奇一圖靈論點，一切可計算的函數都是遞歸函數。抽象地說，計算的本質就是遞歸。不過這里我們想給出一個直觀的描述：計算就是從已知符號開始，一步一步地改變符號串，經過有限步驟后，最終得到一個滿足預定條件的符號串的過程。這樣一種有限的符號串的變換過程與遞歸過程是等價的、一致的。所謂計算方式就是符號變換的操作方式，尤其指最基本的動作方式。廣義地講，還應包括符號的載體或符號的外在表現形式。從中國古代的籌算方式（一組竹棍表征）、珠算方式，到后來的筆算方式就是一系列的計算方式的變化（它們各自具有各自的操作方式）。相對于后來的機器計算方式，這些計算的方式均可歸結為“手工計算方式”，其特點是用手工操作符號，實施符號的變換——擺排竹棍、撥弄算珠或書寫符號。機器計算的歷史可以追溯到1641年，當年18歲的法國數學家帕斯卡爾從機械時鐘得到啟示——齒輪也能計數，成功地制作了一臺齒輪傳動的八位加法計算機。這使人類計算方式、計算技術進入了一個新的階段。后來經過人們數百年的艱辛努力，終于在1945年成功地研制出了世界上第一臺電子計算機。從此，人類進入了一個全新的計算技術時代。就電子計算機而言，至今它也經歷了四個大的時期。從最早的帕斯卡爾齒輪機到今天最先進的電子計算機，計算技術有了長足的發展。這是一個計算方式發生重大變革的歷史時期。這時計算表現為一種物理性質的機械的操作過程。但是，無論是手工計算還是機器計算，其計算方式——操作的基本動作都是一種物理性質的符號變換，具體是由“加”和“減”這種基本動作構成的。二者的區別就在于前者是手工的，后者是自動的。 然而，如今出現的DNA計算則有了更大的本質性的變化。計算不再是一種物理性質的符號變換，而是一種化學性質的符號變換，即不再是物理性質的‘“加”、“減”操作，而是化學性質的切割和粘貼、插入和刪除。這種計算方式的變革是前所未有的，具有劃時代的意義。它將徹底改變計算機硬件的性質，改變計算機基本的運作方式，其意義將是極為深遠的。我們完全可以做這樣一番想象，一旦DNA計算機全面實現，那么真正的“人機合一”就會實現。到那時，人們最不需要的就是電腦，因為大腦本身就是一臺自然的DNA計算機，人們真正需要的只是一個接口。DNA計算機蘊涵的理念不僅可以使計算的方式產生進化，而且可以使人類的大腦、思維產生進化。這是我們對阿德勒曼認識的一點補充。然而，盡管DNA計算較之以往的各種計算有了重大的變革，但是，在計算本質上，它同人類有史以來的一切計算都是等價的、一致的。這是因為：任何可計算函數都可由剪接系統來實現，即任何圖靈機可計算的函數也可以由DNA計算機來計算。反之，任何由剪接系統計算的函數都可由留靈機計算。這就是說，DNA計算也是一種遞歸計算。這一結論有著重要的數學意義。它一方面使人們認識了DNA計算的本質；另一方面進一步證實或支持了丘奇一圖靈論點，使丘奇一圖靈論點首次獲得了電子計算機之外的生物計算機的證實，這種證實自然是更加有力的。 綜上所述，我們看到，計算之所以為計算，在于它具有一種根本的遞歸性，或在于它是一種可一步一步進行的符號串變換操作。至于這種符號變換的操作方式如何，以及符號的載體或其外在表現形式如何，都不是本質性的東西，它們無不是一種歷史的結果，無不處于一種不斷變革或進化的過程之中。符號可以用一組竹棍表征、用一組算珠表征、用一組字母表征，也可以用齒輪表征、用電流表征，還可以分子表征、電子表征等等。不同表征下的符號變換有著不同的操作方式，甚至同一種表征下的符號變換都可以有不同的操作方式。在此，計算本質的統一性與計算方式的多樣性得到了深刻的體現。我們相信，隨著科學技術的不斷發展，計算方式的多樣性還會有新的表現。既然DNA計算機的出現已經打開了人們暢想未來計算方式的思維視窗，那么就讓我們翹首以待吧。3 DNA計算：生命進化的方式 生命是什么？生命是怎樣進化的？這是人類一個永恒的話題。隨著自然科學的不斷發展，生命問題也在不斷變換著其形式，人們對它的理解、認識也在不斷地更新，以適應新的理論的發展與進步。在20世紀八九十年代，由于人類基因組計劃、計算機人工生命、遺傳方法和DNA計算機等一系列全新的理論和觀念的出現，使人們對生命是什么、生命是怎樣進化的等重大基礎性問題再一次產生了新的理解。這種理解的核心內容是：生命就是一臺自然計算機。生命的法則就是算法，生命就是以計算的方式在進化著。DNA計算對這樣一種生命觀給予了強有力的支持。DNA計算表明了計算存在于生物學的根基上，計算處于生命的核心，生命本身就是由一系列復雜的計算組成的。下面我們對此作一個簡要的論述。 什么是算法？簡單地說，算法就是求解某類問題的通用法則或方法。通常要求用它能夠在有限步驟內一步一步地完成對問題的求解。換句話說，算法也就是對有關數據或符號進行變換的方法規則。計算就是對算法的執行或對數據、符號依據有關規則進行的變換操作。長期以來，計算、算法一直是數學的專有概念。但如今由于電子計算機深刻而廣泛的運用，使人們對這兩個基本概念有了更寬泛地認識，使它們泛化到了整個自然界。認為自然界就是一臺巨型自然計算機。任何一種自然過程都是自然規律作用于一定條件下的物理或信息過程，其本質上都體現了一種嚴格的計算和算法特征。在此，自然系統相當于計算機的硬件，自然規律相當于計算機的軟件，而自然過程就是計算機的計算過程。生命系統作為自然界中最復雜最有特色的系統，它也就是形形色色的自然計算機中的一種。DNA計算機就是對生命這種自然機的一種表征。這是因為，DNA是生命的信息庫和程序庫，既是一套自復制的程序，同時又是一個以進化論為基礎發展過來并正在發展的程序。它構成了遺傳、發育、進化統一的物質基礎。現代生物學表明，一方面DNA可以看作是由A、G、C、T四個字符組成的字符串。從數學上講，這意味著我們可以用一個含有四個字符的字符集∑={A、G、C、T}為信息編碼。DNA代碼與計算機代碼所不同的只是它不是二進制的，而是一種四進制代碼。有人甚至指出：除了專業術語不同之外，分子生物學雜志里面的每一頁都可以換成計算機技術雜志的內容。另一方面，DNA能夠對該信息載體進行一系列可控制的變換（即化學反應）。變換的具體方式是DNA的復制、剪切、連接、修復，變換的過程就是一種生命過程，也即生命的自構造性特征。因此，我們完全可以把生命看作是一臺自然計算機，生命的進化法則就是算法。另外，DNA作為一種自然語言，和計算機程序語言一樣，具有不同的層次，具有遞歸、并行、模塊化的基本特征。現代生物學表明，一維線性分子在特定的環境中通過復雜而準確的信息處理，可拓展為一個豐富的四維時空生命體，這種展現過程所獲得的新信息反過來又不斷地反映到一維線性分子中，導致生物物種的不斷進化。這正是DNA程序語言層次性的表現。一維DNA序列只不過是最低級的生命機器語言，所有的高級語言都必須編譯成DNA序列語言才能執行。目前，DNA這種自然語言的詞法、句法規則我們尚不清楚，但本質上是一種程序化語言[7] 。 DNA計算機的提出，就是一種分子算法的化學實現。以前分子算法，如自復制自動機、胞格自動機、遺傳算法、人工生命等全都是在電子計算機上實現的，DNA計算機的出現是分子算法的化學實現的開端。這種立足于可控的生物化學反應或反應系統，無疑更加有力地直接地表明了生物現象與過程的計算特征。而這對于現代生物學的研究自然有著十分積極的影響。正如阿得勒曼所說：DNA計算機的構想，是從另一個角度出發啟示人們用算法的觀念研究生命。“算法對于生命的意義，就在于以過程或程序描述代替對生物的狀態或結構描述，將生命表示為一種算法的邏輯，把對生命的研究轉換成為對算法的研究”[8]。在這個意義上，生命就是程序、就是算法——一種能夠實現自我復制、自我構造和自我進化的算法。在尼葛洛龐帝的《數字化生存》中，有一個已是眾所周知的主題論斷：計算不再只和計算機有關，它決定我們的生存。但是，尼葛洛龐帝僅是從社會生活的意義上說這番話的。我們在這里則要賦予它另一種新的含義——生理生存，即計算決定我們的肉體的生存。 生物學界這種算法觀念的廣泛運用，更增強了人們運用算法觀念看待整個自然界的信心，拓展了人們對自然現象的理解。要知道生命是最復雜的自然現象之一，是自然界進化的最高代表。因此，我們完全有理由猜想：整個宇宙也是按算法構成的，是按算法演化的。現實世界之萬事萬物只不過是算法的復雜程度的多樣性。從虛無到存在、從非生命到生命、從感覺到意識，或許整個世界的進化過程就是一個計算復雜性不斷增長的過程。看來畢達哥拉斯或許真是對的：萬物皆數！應該說，這便是DNA計算機所蘊涵的最深奧的哲學理念：數學可能是萬物的基礎，數學可能是現實世界和可能世界的核心。今天，我們或許應該將畢達哥拉斯的哲學再向前推進一步：存在的意識就是數學意識。因為DNA計算宣稱數學處于生命的核心。參考文獻[1]L M Adleman。 Molecular Computation of Solutions to Combinatorial Problems [J]。Science, 1994。266。 Science， 1994． 266．[2]M Linial。 On the Potential of Molecular Computing [J]。 Science， 1995．268．[3]鄧少平，等．DNA計算的一些基本問題［J］．科學（中文版），1996（5）．[4]Barry Cipra．Computer Science discovers DNA［J］．What's Happening in the Mathematical Science．AMS，1996（3）．[5][6]Lila Kari． DNA Computing： Arrival of Biological Mathematics［J］． The Mathematical Intelligencer．1997（2）．[7][8]鄧少平．生命與算法[J]．科學（中文版），1996．10。。