崔建中

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

0 引言

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

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

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

1 DNA 計算

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

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

2 邏輯門在DNA 計算中的實現(xiàn)

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

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

3 鏈置換技術(shù)和邏輯門實現(xiàn)

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

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

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

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

圖2 Seesaw 門級聯(lián)實現(xiàn)邏輯門

邏輯與門、或門結(jié)構(gòu)相同，區(qū)別在閾鏈濃度不一樣。為了便于討論，我們分別用符號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年出現(xiàn)，經(jīng)歷將近二十年的發(fā)展，在計算理論、生物技術(shù)可靠性上都已取得豐富的成果。雖然目前DNA 計算在運算速度上還不具備優(yōu)勢，雖然目前還不清楚DNA 計算機能否代替?zhèn)鹘y(tǒng)計算機，但對DNA 計算機的研究必定會促進計算機科學、信息學和分子生物學等相關(guān)學科的發(fā)展、必定會深化人們對生命現(xiàn)象本質(zhì)的認識。

［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.