邏輯門在DNA計算中的生物實現

崔建中

(淮南聯合大學 實訓中心，安徽 淮南 232038)

0 引言

邏輯門是集成電路上的基本組件，是構建計算機的基礎。邏輯門可以組合成邏輯電路進行復雜的邏輯運算。

摩爾定律指出集成電路上可容納的晶體管數目約每隔18 個月便會增加一倍，性能也將提升一倍。由于一方面DNA 分子海量信息的存儲能力；另一方面，兩條單鏈DNA 可以依據簡單的堿基互補配對規則形成穩定的雙鏈DNA，且反應可以高度并行地進行。上述特點使得DNA 計算很有可能取代硅介質計算機并實現計算的途徑。

本方從DNA 計算、邏輯門在DNA 計算中的生物實現兩個方面做一下簡要的介紹，文中闡述了Winfree 等人的最新研究成果，并對他們的方法應用于大規律邏輯運算時的優、缺點進行了討論。

1 DNA 計算

1994年，美國加利福尼亞大學的Adleman 博士提出利用DNA（脫氧核糖核酸）對一個圖論中的NP-完全問題-有向圖的Hamilton 路問題進行編碼，借助連接、變性、復性、PCR 擴增、電泳等生物操作可以求解出這一問題[1]。

經過二十多年的發展，關于DNA 計算領域的研究成果非常豐富。特別是近年來DNA 自組裝的研究引起了學者們的興趣，并取得了很多的研究成果。DNA 自組裝是指以DNA 分子為基本材料，通過分子間的堿基氫鍵、范德華力等微作用力自發締結成結構穩定的聚集體或超分子結構。1963年，Wang[2]提出了“Wang Tile”的概念，并指出Wang Tile 可以通過自組裝過程，在二維平面形成周期性格局，而且該過程被證明具有圖靈機等價的計算能力，然而直至20 世紀90年代，DNA自組裝技術才變為現實。

2 邏輯門在DNA 計算中的實現

通用圖靈機是計算機科學中一個抽象的計算模型。圖靈在1936年的文章中詳細描述如此的構思。現代通用電子計算機其實就是這樣一種通用圖靈機的模擬，它能接受一段程序，并運行程序實現該程序所描述的算法。各種各樣的邏輯門所構成的邏輯電路是現代通用電子計算機實現計算的功能單元，最常見的邏輯門有“與”、“或”、“非”，“異或”門。自Adleman 教授開創了DNA 計算以來，研究人員一直致力于DNA 計算機的研制。

1996年，Ogihara 和Ray 最先給出了基于DNA 分子的布爾電路模擬[3]。2004年，Wenbin Liu 等利用兩個GGG 序列誘導的DNA 分子發夾結構模擬了NAND[4]。2006年，我們給出了基于分子信標的與門、或門的實現[5]。2011年，Science[6]報道了加州理工學院計算機系的Winfree 教授課題組在試管中利用可逆的DNA 鏈置換技術實現邏輯門，并模擬了含有一個3 層、6 個邏輯門的生化電路，求解了四位二進制數的平方根。該生化電路初始狀態含有74 種DNA 鏈，當編碼輸入的DNA 鏈被加入試管后，電路被啟動進行運算，此時試管中共有130種長度為15-33 個堿基的DNA 鏈相互作用，最后通過熒光輸出計算的結果。這一成果是目前報道的利用DNA 來模擬通用計算機進行計算最好的結果，我們將在下節做詳細的介紹。

3 鏈置換技術和邏輯門實現

2011年，Winfree 等應用的DNA 鏈置換原理構造了Seesaw 門并利用級聯的Seesaw 門模擬邏輯門，求解了含有一個3 層、6 個邏輯門的生物電路。Seesaw 門是整個生物電路的基本組件，它由4 種DNA 鏈組成：輸入鏈（Input）、門鏈與輸出鏈的復合鏈（Complex）、Fuel 鏈、閾鏈Th（Threshold），如圖1 所示。

圖1 Seesaw 門示意圖及DNA 鏈編碼

圖1A 給出了Seesaw 門的示意圖，圖1B 中給出了構成Seesaw 門的DNA 鏈的編碼及構形，Complex 為穩態的部分雙鏈DNA。這里要注意的是，輸出鏈（Output）在鏈置換反應發生前是雜交在門鏈上形成部分雙鏈的復合物（Complex），在圖B 中表示為3T2（5’→3’方向）。閾鏈Th 也是穩態的部分雙鏈DNA，由于閾鏈Th 中1*T*2* 的長度大于門鏈T*2*，當輸入鏈2T1 被加入時，它們首先和閾鏈發生鏈置換，直至閾鏈完全反應，剩余的輸入鏈才會和復合鏈發生鏈置換。閾鏈的作用是控制參與鏈置換的輸入鏈的數目。輸入鏈Input 和輸出鏈Output 為DNA 單鏈，它們分別由門的編碼和輸入、輸出編碼兩部分構成，當Seesaw 門的輸入或者輸出多于2 個時，輸入、輸出鏈長度不變，只要對應修改輸入或輸出的編碼而其它結構無需改動。Fuel 鏈4T2 也是DNA 單鏈，它不是Seesaw 門必選的組件，由于鏈置換是可逆的過程，輸出鏈也會置換輸入鏈，它與輸出鏈競爭，通過設置濃度大于輸入出鏈，則可以實現對鏈置換方向的控制，被反向置換的輸入鏈再次置換輸出鏈又可實現置換結果的放大。

邏輯門由兩個Seesaw 門級聯構成（圖2B），左側第一個Seesaw 門3 用于接受邏輯門的輸入鏈3T1、3T2，右側第二個Seesaw 門4 受第一個Seesaw 門鏈置換后的輸出鏈4T3，設置吸收該鏈的閾鏈的濃度控制第二個Seesaw 門參與置換的鏈來實現邏輯門的功能，若邏輯門的計算結果為1，則能檢測到第二個Seesaw 門的輸出鏈5T4，為保證有效地檢測到輸出鏈，第二個Seesaw 門設置了Fuel 鏈6T4。

圖2 Seesaw 門級聯實現邏輯門

邏輯與門、或門結構相同，區別在閾鏈濃度不一樣。為了便于討論，我們分別用符號C（濃度）表示參與鏈置換反應的DNA 鏈的濃度，ANDTh表示與門的閾鏈，ORTh 表示或門的閾鏈，一般而言，C（ANDTh）=2 C（ORTh），C（InputN）＞C（ORTh），N=1，2。當邏輯門的輸入Xi=1(i=1，2)時，加入代表Xi=1 的輸入鏈3T1、3T2；反之，若Xi=0(i=1，2)，不加入輸入鏈。顯然，對于邏輯與門而言，若C（Input1）+C（Input2）>C（ANDTh），則必然能夠檢測到第二個Seesaw門的輸出鏈，而這一條件只有當輸入變量均為1、對應輸入鏈均被加入才能成立；對于或門而言，若C（Input1）+C（Input2）>C（ORTh），則必然能夠檢測到第二個Seesaw 門的輸出鏈，而這一條件只須任一輸入變量為1、對應輸入鏈被加入就能成立。

4 討論

DNA 計算自1994年出現，經歷將近二十年的發展，在計算理論、生物技術可靠性上都已取得豐富的成果。雖然目前DNA 計算在運算速度上還不具備優勢，雖然目前還不清楚DNA 計算機能否代替傳統計算機，但對DNA 計算機的研究必定會促進計算機科學、信息學和分子生物學等相關學科的發展、必定會深化人們對生命現象本質的認識。

［1］Adleman L..Molecular Computation of Solution to Combinatorial problems[J].Science，1994，66（11）：1021-1024.

［2］Wang H.Dominoes and AEA case of th decision problem[C]//Proceeding of the symposium Mathematical Theory of Automata.New York，1963：23-55.

［3］Ogihara.M，Ray.Simulation Boolean Circuits ON a DNA computer [J].Algorithmica，1999（25）：239-250.

［4］Wenbin Liu，Xiaolong，Shi，Shenmin Zhang，Xiangrong Liu，Jin Xu，A new DNA computing model for NAND gate based on induced hairpin formation[J].Biosystem，2004，77：87-92.

［5］Cui Jianzhong，Yin Zhixiang，Wang Wei，et .al..Towards Reliable Simulation of Bounded Fan-in Boolean Circuits Using Molecular Beacon [C]//Proceedings of the 6th World Congress on Control and Automation，June 21－23，2006，Dalian，China，5：3910-3914.

［6］Lulu Qian，Winfree E.Scaling up digital circuit computation with DNA strand displacement cascades[J].Science，2011，332：1196－1201.