熱心網友

生物計算機：試管里的奇跡 周游 編者按:本文是2004年7月26日出版的《計算機世界》周報第28期產品與技術版 “新一代計算機”系列專題文章之一，另兩篇文章分別為“納米計算機：承上啟下”、“量子計算機：顛覆傳統”1994年， Leonard M。 Adleman用一種不平常的技術解決了一個平常的計算問題。這是個一個人只用一會兒時間，普通桌面計算機只需一眨眼功夫，就可以解答的問題。可是，Adleman用了7天才找到答案。那么，這項工作為什么不同尋常呢？因為他利用DNA解決了這個問題。這是一次里程碑式的分子級計算演示。Adleman求解的問題是一個著名問題。它的正式名字叫定向哈密爾頓路徑（HP）問題，但人們更多地稱它為“貨郎擔問題”。在Adleman版的貨郎擔問題（TSP）中，一位貨郎試圖找到一條穿越幾個城市的道路，而且他只到每個城市一次。隨著城市數量的增加，問題變得越來越困難，直至問題的答案無法用解析分析法求解，必須采用蠻力搜索法。城市數量巨大的TSP的計算成本會變得很高，以致在最新型的超級計算機上求解都不切實際。Adleman的演示只涉及7個城市，因此答案甚至可以用肉眼觀察就輕松地得到。但是，他的工作卻由于多種理由而意義重大。它顯示了利用DNA解決一類難于或不可能利用傳統計算方法解決的問題的可能性；它是分子級計算的例子，而半導體行業可能永遠達不到分子級水平；它展示了DNA作為一種數據結構的獨特方面；它證明了DNA計算可以以大規模并行方式運行。DNA：一種獨特的數據結構人們在過去40年里積累了大量有關DNA分子生物學的信息。因此，為避免被DNA的生物化學和生物學細節搞得焦頭爛額，我們將只探討與DNA計算有關的信息。DNA的數據密度大得驚人。正像一串二進制數據用“0”和“1”編碼一樣，一串DNA用4個用字母A、T、C和G代表的脫氧核糖核酸基鹽編碼。在DNA分子上的脫氧核糖核酸基鹽（也叫核苷酸）之間的間隙為0。35納米，從而使DNA具有了每英寸近18 Mbits的不同尋常的數據密度。在兩維空間中，如果假設每平方納米有一個核苷酸的話，數據密度超過每平方英寸1百萬Gbits。與數據密度約為每平方英寸7 Gbits的典型高性能硬盤相比，DNA數據密度超過它10萬倍以上。DNA的另一個重要屬性是其雙鏈性質。核苷酸A、T、C和G可以粘合在一起，形成核苷酸對。因此每個DNA序列都具有一個天然的補序列。例如，如果序列S為ATTACGTCG，那么其補序列S'為TAATGCAGC。S和S'將混合在一起（或雜交）形成雙鏈DNA。這種互補性使DNA成為一種獨特的計算結構，可以以多種方式加以利用。其中的一個例子就是糾錯。由于種種因素，DNA中會出現錯誤。DNA酶偶爾也會犯錯誤，在不應該斷開的地方斷開，或在本該插入G的地方插入T。太陽發出的紫外線和熱量也會損壞DNA。如果錯誤發生在雙鏈DNA的某一段上，修復酶可以利用補序列串作為參考，恢復正確的DNA序列。從這個意義上說，雙鏈DNA類似于一臺RAID 1陣列，即第二塊硬盤是第一塊硬盤的鏡像，如果第一塊硬盤發生錯誤，數據可以從第二塊硬盤中恢復。在生物系統中，這種糾錯能力意味著錯誤率相當低。例如，在DNA復制時，每復制10^9個核苷酸發生一次錯誤，換句話說，錯誤率為10^-9（相比之下，采用Reed-Solomon糾錯時，硬盤的讀錯誤率只有10^-13）。并行操作在細胞中，DNA由不同的酶以生物化學方式進行修改。酶是微小的蛋白質，它按照大自然的設計，讀取和處理DNA。這類在分子級上處理DNA的“運行的”蛋白質的種類和數量都非常多。例如，既有切斷DNA的酶，又有將它們再粘在一起的酶。一些酶發揮復印機的作用，另一些酶承擔修理工的職責。分子生物學、生物化學和生物工藝學開發出了使我們能夠在試管中完成這些細胞功能的許多功能的技術。正是這種細胞組織以及一些合成化學品，構成了一套可用于計算的操作。CPU有一套加、移位、邏輯算子等基本組成的操作集合，這些操作使CPU可以執行最復雜的計算。正像CPU一樣，DNA也具有切斷、復制、粘貼、修理以及其它許多操作。需要注意的是，在試管中，酶并不是順序地工作，一次處理一個DNA，而是酶的很多副本同時處理許多的DNA分子。這正是DNA計算的威力所在：可以以大規模并行方式運行。與硅計算機的比較DNA憑借其獨特的數據結構和執行很多并行操作的能力，使人們能夠從不同的角度研究計算問題。基于晶體管的計算機通常以順序方式處理操作。當然，現在出現了多處理器計算機，而且現代CPU具有一定的并行處理能力，但一般而言，在基本的von Neumann架構計算機中，指令是順序執行的。一臺von Neumann機器(所有的現代CPU都屬于von Neumann機器)基本上一次又一次地重復同樣的“讀取和執行周期”，它從主內存中讀取指令和相應的數據，然后再執行指令。它非常非常快地、許多許多次地順序執行這些操作。而DNA計算機不是von Neuman機器，它是隨機的機器，它在解決不同類型的問題時，以不同于普通計算機的方式進行計算。一般來說，提高硅計算機的性能，意味著更快的時鐘速度（和更寬的數據通道），此時強調的是CPU速度，而不是內存的大小。然而，對于DNA計算來說，其力量來自內存容量和并行處理。假如被迫執行順序操作的話，DNA將失去它的吸引力。以DNA的讀/寫速度為例。在細菌中，DNA可以以每秒大約500對核苷酸的速度進行復制。從生物學角度看，速度相當快（比人類細胞快9倍），而且考慮到低錯誤率，這是個很了不起的成就。但是，這只是1000 bps，與一般硬盤的數據吞吐量相比，等于是蝸牛爬。首先，復制酶甚至在完成復制第一個DNA串之前，就可以開始復制第二個DNA串。因此，數據速度猛增到了2000 bps。DNA串的數量指數級增加(n次迭代后數量為2^n)。每增加一串DNA，數據速率就增加1000 bps。因此在10次迭代后，DNA的復制速度約為1M bps，30次迭代后，增加到1000G bps。這超過了最快速硬盤的持續數據速率。現在讓我們來比較一下用傳統計算機和DNA計算機解決非平凡的貨郎擔問題(城市數量 10)的情況。在使用傳統的馮·諾伊曼計算機時，一種原始的方法是建立搜索樹，然后順序測量每一個完整的分支，并保留最短的路線。這種方法可利用更好的搜索算法加以改進。一種肯定不會使用的方法是首先生成所有可能的路線，然后搜索整個路線表。為什么呢？因此對于20個城市的貨郎擔問題，整個路線表理論上將占用4千5百萬GB的內存！對于一臺運算速度100 MIPS的計算機，僅生成所有的路徑就需要兩年時間(假設一條指令周期生成一條路線中的一個城市)。然而在使用DNA計算機時，這種方式卻變得可行了！10^15對于生物化學來說，是很小的數量。此外，路線也不再順序搜索了。操作都是以并行方式完成的。Adleman的試驗讓我們利用Adleman演示的DNA方式來解決我們自己的定向哈密爾頓路線問題。為敘述方便起見，我們對例子進行了簡化。假設你住在洛杉磯，需要訪問4個城市：芝加哥、達拉斯、邁阿密和紐約，其中紐約是最后的目的地。你所選擇的航空公司的轉接班機限制了你能選擇的路由(例如，有從洛杉磯到芝加哥的航班，但沒有邁阿密到芝加哥的飛機)。如果你希望只訪問每個城市一次，該怎么走呢？圖1Adleman的步驟是：生成所有可能的路由；選擇從起點城市開始到終點城市結束的路線；選擇具有正確城市數量的路線；選擇包含每個城市只出現一次的路線。以上所有步驟都可以利用標準的分子生物技術完成。第一步：生成所有可能的路由策略：用短DNA序列為城市名編碼。通過連接存在路由的不同城市序列，對路線編碼。DNA可以當做數據串對處理。例如，每個城市可以用六個核苷酸成組的“字”來代表：洛杉磯：GCTACG 芝加哥：CTAGTA 達拉斯：TCGTAC 邁阿密：CTACGG 紐約： ATGCCG整條路線的編碼可通過將這些代表具體城市的DNA序列串起來完成。例如，從洛杉磯--芝加哥--達拉斯--邁阿密--紐約的路線表示為GCTACGCTAGTATCGTACCTACGGATGCCG，也可以等價地用這條序列的補序列形式表示。那么，我們怎樣生成這條序列呢？人工合成短單鏈DNA現在是一種常規方法，因此，城市名編碼十分簡單。一種叫做DNA合成器的設備可以制作這些分子，也可以從第三方定制。然后，按正確的次序將城市名編碼連接在一起來生成路線。在完成這項工作時，我們可以利用DNA與其補序列雜交的事實。例如，我們可以通過對起始城市的后一半字母(后三個字母)和到達城市的前一半字母(前三個字母)的補序列進行編碼，對城市間路由編碼。例如，邁阿密(CTACGG)與紐約(ATGCCG)之間的路由可以用邁阿密編碼的后一半(CGG)和紐約編碼的前一半(ATG)組成，即CGGATG。取補后，得到GCCTAC。GCCTAC不僅惟一表示了從邁阿密到紐約的路由，而且還通過把代表邁阿密和紐約的DNA與CGG和ATG雜交，連接將它們連接在一起。(見圖 g)隨機路線可以通過將城市編碼與路線編碼混合起來生成。最后，這些DNA串可以用一種叫做連接酶的酶連接在一起。這時我們得到的是代表示具有任意數量的城市和任意路由集合的路線的DNA串。(見圖 g)利用大量的DNA編碼(比如，10^13個每個城市和城市間每條路由的副本)，我們肯定得到所有可能的組合,一個正確的組合就包括在這些組合中。第二步：選擇從起點城市開始到終點城市結束的路線策略：利用聚合酶鏈反應，有選擇地只復制和放大開始于洛杉磯并結束于紐約的DNA部分。完成第一步后，我們得到了一只裝滿代表路線編碼的各種長度的DNA的試管。我們需要的是從洛杉磯到紐約的路線。為此，我們可以使用一種叫做聚合酶鏈反應(PCR)的技術。PCR使我們可以生產出某一DNA序列的大量副本。聚合酶將復制開始于引分子(primer)位置的一段單鏈DNA。引分子是一小截DNA，與我們感興趣的那段DNA的一端互補。通過選擇位于我們希望放大的那段DNA兩側的引分子，聚合酶優先放大這些引分子間的DNA，將包含這一序列的DNA的數量增加一倍。經過多次PCR后，DNA被放大了指數級倍。在有選擇地放大我們感興趣的路線時，我們使用與洛杉磯和紐約互補的引分子。在PCR后，我們最后得到的是一只裝滿不同長度、代表著從洛杉磯起到紐約止的路線編碼的雙鏈DNA的試管。第三步：選擇具有正確城市數量的路線策略：根據長度分類DNA，選擇長度對應5個城市的DNA。經過第二步后，試管中路線DNA編碼盡管代表著始于洛杉磯止于紐約的路線，但經過城市的數量卻不同。我們現在希望選擇只經過五個城市的路線。為此，我們可利用一種叫做凝膠電泳的技術。凝膠電泳法是一種用于解決DNA長度的通用過程。凝膠電泳法的基本原理是利用電場，迫使DNA經過一個凝膠矩陣。在多數條件下，DNA為負電荷分子，因此如果放置在電場中，將被吸引到正電位上。但是由于DNA的電荷密度恒定不變，懸浮在液體中的長DNA段與短DNA段運動速度一樣快。這就是為什么要使用凝膠矩陣的原因。凝膠由形成細絲網的聚合體構成。DNA被迫穿過細絲間的微小空間，細絲降低了DNA的移動速度，速度降低多少取決于DNA的長度。最后得到許多DNA帶子，每個帶子對應于某個長度。然后，我們可以切掉我們感興趣的帶子，分離出特定長度的DNA。由于我們知道每個城市用6對DNA編碼，因此，掌握路線的長度就使我們掌握了城市的數量。在本例中，我們將分離具有30對核苷酸長度(5個城市X 6對核苷酸)的DNA。（ g）第四步：選擇包含每個城市只出現一次的路線策略：按城市連續過濾DNA分子，每次一個城市。由于我們處理的DNA包括五個城市，我們將得到每個城市只編碼一次的DNA序列。我們可以利用一項叫做親和純化的技術，從DNA樣本中純化出包含特定序列的DNA。我們可以通過將DNA序列的補序列連接到一種基質上(如磁珠)，完成這項工作。磁珠然后與DNA混在一起。這時，包含我們所需要序列的DNA將與磁珠上的補序列雜交。然后，這些磁珠被取出，分離出DNA。我們進行5次親和純化，每次使用一個不同的城市補序列。例如，第一次時，使用帶有洛杉磯補序列的磁珠，來分離包含洛杉磯編碼的DNA序列。如此反復5次，我們就得到了從洛杉磯開始、只訪問每個城市一次、結束于紐約的所有路線。讀取答案一種找到結果的可能方法是對DNA序列排序。不過，由于我們已經有了城市編碼的序列，因此我們可以使用一種叫做漸變PCR的方法。這時我們利用對應于洛杉磯的引分子，接著使用對應于每個城市的不同引分子，進行一系列PCR放大。通過測量每個PCR結果得到的不同DNA長度，我們可以將路線中的最終城市序列拼湊出來。例如，我們知道DNA路線開始于洛杉磯，具有30對核苷酸長度，因此如果洛杉磯和達拉斯引分子的PCR結果為24對核苷酸長，可知達拉斯是路線中的第四個城市(24被6除)。最后，如果我們在DNA處理中十分仔細的話，試管中留下的惟一DNA應當中代表洛杉磯、芝加哥、邁阿密、達拉斯和紐約路線編碼的DNA。因此，如果使用的引分子順序是洛杉磯與芝加哥、洛杉磯與邁阿密、洛杉磯與達拉斯和洛杉磯與紐約，那么我們將得到長度為12、18、24和30對核苷酸的PCR結果。幾點說明Adleman的試驗解決了7個城市的問題，但是有兩大缺點阻止擴大其計算的規模。當使用一種不同的解法時，貨郎擔問題的復雜度并沒有消失：復雜度仍以指數級增長。就Adleman的方法而言，指數級增長的東西不是計算時間，而是DNA的數量。不幸的是，這給可以求解的城市數量帶來了一些硬性限制。在Adleman的文章發表后，很多人指出使用他的方法求解200個城市的HP問題，需要的DNA的重量將比地球還要重。限制Adleman方法的另一個因素是每次操作的錯誤率。由于這些操作并不是確定性而是隨機驅動的(我們是在做化學試驗)，每一步都包含統計錯誤，因而限制了在產生錯誤的概率超過產生正確結果的概率前我們所能連續迭代的次數。例如，1%的錯誤率可進行10次迭代，這時的錯誤率小于10%，而在進行100次迭代后，錯誤率增長為63%。“試管”的未來那么DNA能被用于解決城市數量超過傳統計算機能力的貨郎擔問題嗎？鑒于目前傳統計算機的記錄是13,509個城市，這肯定不能用上述過程求解。傳統計算機求解這個問題只用了3個月時間，當時動用了3臺Digital AlphaServer 4100s(共有12個處理器)和一個由32臺Pentium-II PC組成的群集。此問題的求解不是由于計算能力，而是由于人們使用了一些效率非常高的分支規則。Adleman的第一次DNA計算演示采用了一種不太高明的算法，但是隨著DNA計算形式的不斷細化，新算法也許有一天將使DNA超過傳統計算機，創造新記錄。在“硬件方面”(或者應當說“濕件”)，生物技術的改進正在以類似于半導體行業的進步速度發展。以DNA排序為例，曾需要一位研究生用5年時間完成的工作，現在只需要一天。鑒于政府投入到基因研發大量資金和來自利潤豐厚的制藥和醫療相關市場的潛在巨額回報，這種情況并不讓人感到吃驚。人類基因組項目正在排序技術方面迅速取得創新。DNA處理的未來是速度、自動化和小型化。不難想像，總有一天我們將擁有制造利用DNA或DNA式的生物高聚物作為計算基礎的小型集成桌面機的工具和人材以及各種設計酶(designer enzymes)。也許DNA計算機不會被用于玩“Quake IV”或上網沖浪(這些事情是傳統機所善長的)，而肯定可以被用于研究邏輯、加密、基因編程與算法、自動控制、語言系統以及很多現在還沒有發明出來的其它有趣的事。 。

熱心網友

生物計算機是以生物界處理問題的方式為模型的計算機。目前主要有：生物分子或超分子芯片、自動機模型、仿生算法、生物化學反應算法等幾種類型。 計算機工業在近幾十年內飛速發展，其速度令人瞠目。然而目前晶體管的密度已近當前所用技術的理論極限，晶體管計算機能否繼續發展下去？所以，人們在不斷尋找新的計算機結構。另一方面，人們在研究人工智能的同時，借鑒生物界的各種處理問題的方式，即所謂生物算法，提出了一些生物計算機的模型，部分模型已經解決了一些經典計算機難以解決的問題。 生物計算機目前主要有以下幾類： 1。 生物分子或超分子芯片：立足于傳統計算機模式，從尋找高效、體微的電子信息載體及信息傳遞體入手，目前已對生物體內的小分子、大分子、超分子生物芯片的結構與功能做了大量的研究與開發。“生物化學電路” 即屬于此。 2。 自動機模型：以自動理論為基礎，致力與尋找新的計算機模式，特別是特殊用途的非數值計算機模式。目前研究的熱點集中在基本生物現象的類比，如神經網絡、免疫網絡、細胞自動機等。不同自動機的區別主要是網絡內部連接的差異，其基本特征是集體計算，又稱集體主義，在非數值計算、模擬、識別方面有極大的潛力。 3。 仿生算法：以生物智能為基礎，用仿生的觀念致力于尋找新的算法模式，雖然類似于自動機思想，但立足點在算法上，不追求硬件上的變化。 4。 生物化學反應算法：立足于可控的生物化學反應或反應系統，利用小容積內同類分子高拷貝數的優勢，追求運算的高度并行化，從而提供運算的效率。DNA計算機 屬于此類。以下將著重介紹自動機模型中的計算神經網絡和生物化學反應算法中的DNA計算機的模型。 。

熱心網友

DNA生物計算機是美國南加州大學阿德拉曼博士1994年提出的奇思妙想，它通過控制DNA分子間的生化反應來完成運算。但目前流行的DNA計算技術都必須將DNA溶于試管液體中。這種電腦由一堆裝著有機液體的試管組成，很是笨拙。