ＤＮＡ計算原理、現狀及展望

方　鋮

摘要：綜述了DNA計算原理和特點，接著介紹了DNA計算的研究現狀，指出了目前DNA計算的主要研究方向和DNA計算需要解決問題，最后對DNA計算的發展前景進行了展望。

關鍵詞：DNA計算NP完全問題圖論

中圖分類號TP301.6文獻標識碼A文章編號：1002-2422(2007)05-0002-02

對于一類被稱之為NP完全問題的復雜計算，計算機的處理時間會隨著問題規模的增大呈現指數級增長，因此迫切需要一種新的計算形式來解決它，DNA計算就是一種新的嘗試。

1DNA計算原理、特點

1.1DNA計算原理

DNA計算是伴隨著分子生物學的興起而出現的。生物學家研究發現，DNA有一種特性，能夠攜帶生物體內各種細胞擁有的大量基因物質。計算機專家從中得到啟迪，正在研制液體DNA電腦。這種DNA電腦的工作原理是以瞬間發生的生化反應為基礎，通過和酶的相互作用，將反應過程進行分子編碼，對問題以新的DNA編碼形式加以解答。

DNA是一種由許多脫氧核苷酸的單體連接在一起形成的聚合物。核苷酸是由三部分組成的：脫氧核糖、磷酸和含氮堿基，其中堿基有四種類型：腺嘌呤A、鳥嘌呤G、胸腺嘧啶T、胞嘧啶C，與之對應的核苷酸也有四種，分別稱為脫氧腺苷酸(A)、脫氧鳥苷酸(G)、脫氧胸苷酸(T)、脫氧胞苷酸(C)。單核苷酸端對端連接在一起形成DNA鏈，在這種連接過程中，堿基嚴格遵循下述配對原則：A、T配對，G、C配對。

一個DNA單鏈可看作由四個不同符號A、T、G和C連成的串，就像電子計算機中的O、1編碼一樣，可使用四個字母的集合∑={A，G，C，T}，并按照DNA雙螺旋結構和堿基互補配對原則對問題進行編碼，酶可看作模擬在DNA序列上的計算，不同的酶相當于作用在DNA串上的不同的算子，主要的酶操作有：限制內切酶進行切割操作、接合酶作連接操作、聚合酶可用作復制、外核酸酶可用作刪除等等。

DNA算法解決計算問題的基本思想是：把要運算的對象映射成DNA分子鏈，在DNA溶液的試管里，在生物酶的作用下，生成各種數據池，然后按照一定的規則將原始問題的數據運算高度并行地映射成DNA分子鏈的可控的生化過程，最后。利用分子生物技術如聚合酶鏈反應、聚合重疊放大技術、超聲波降解、親和層析、克隆、誘變、分子純化、電泳、磁珠分離等，破獲運算結果。

完整的DNA計算過程包括數據輸入、運算以及結果的輸出。首先，將問題空間的對象映射成DNA分子鏈；第二步，利用DNA分子鏈的高度并行運算的特點，用可控的生化操作完成正確答案的篩選工作；第三步，結果的輸出，主要通過測定來判斷是否有解，如果有解則將DNA鏈進行譯碼，就得到所求問題的解。

1.2DNA計算優點、不足

1.2.1DNA計算具有以下優點：

(1)運算速度快：目前最快的電子計算機的計算速度為10¹²次/秒，而對于DNA計算機，如果是兩個DNA的連接視為一次操作，又假定4*10¹⁴個邊DNA片斷有一半發生了連接反應，則DNA計算機的運算速度為10¹⁴次/秒。

(2)低能耗：生化反應所需要的能量消耗很小，完成同樣的運算DNA計算所消耗的能量是大型機的十億分之一。

(3)存儲容量高：DNA存儲信息的密度是1bit／nm³，而當前錄像帶的信息存儲密度僅為1bit/12¹²nm³。

(4)可真正實現并行工作：傳統電子計算機主要是串行工作，而DNA計算機可視為多CPU的并行工作，可以實現現有計算機無法真正實現的模糊推理和神經網絡運算功能。對于DNA計算機，一個DNA分子相當于一個CPU，在