基于DNA鏈置換的贏家通吃神經網絡

王 賓李 亞 趙宏偉

(大連大學先進設計與智能計算省部共建教育部重點實驗室 大連 116622)

1 引言

隨著大數據時代的到來，計算機需要處理大量的數據。雖然當前的電子計算機能較好地處理這些數據，但是在并行計算和存儲能力方面也面臨著發展的瓶頸，因此設計具有并行性、運算快和大容量的DNA計算機成為必然的趨勢。自Adleman[1]解決了哈密頓路徑問題以來，DNA計算受到越來越多學者的關注。一些重要的DNA計算技術和計算模型被提出，其中DNA鏈置換是重要的技術之一。

DNA鏈置換[2,3]操作簡單，具有自主性[4]。目前，DNA鏈置換已廣泛用于生物邏輯電路[5–7]、催化放大器[8]以及DNA編碼等領域[9–12]。例如，Seelig等人[13]基于DNA鏈置換設計了AND,OR和NOT門，這為邏輯電路的發展奠定了基礎。Zhang等人[14]實現了一個用于放大信號的電路，包括具有動態特性的前饋級聯電路和具有指數增長動態特性的正反饋電路。另外，Lakin等人[15]提出了一個監督學習框架，使用緩沖的DNA鏈置換網絡開發自適應分子電路，該框架擴展了現有的DNA鏈置換電路架構。Song等人[16]構建了加法、減法和乘法的基本門，基于這些門，描述了如何構建用于計算輸入多項式函數的DNA電路。

近年來，DNA鏈置換用來構造神經網絡取得了令人矚目的成果。例如，Qian等人[17]使用112條DNA鏈進行級聯，設計了一個4神經元的Hopfield聯想記憶。然而由于Hopfield聯想記憶在實現“猜心術”游戲時，網絡規模較大，Genot等人[18]通過贏家通吃(Winner-Take-All,WTA)效應推廣到僅含DNA鏈的電路，縮小了電路并展示只有23條DNA鏈構造的“猜心術”游戲。緊接著，Shi等人[19]設計了智能的DNA分子系統，可以自動地執行邏輯運算，該系統由一些特定的“DNA神經元”串聯組成。之后，Cherry等人[20]通過使用seesaw門，證明基于WTA的DNA神經網絡的可以識別手寫數字分為多達9類。

本文提出基于DNA鏈置換實現的WTA神經網絡，采用湮滅進行競爭得到最后的結果。由于不需要進行信號的放大和恢復，這不僅減少了DNA鏈的數量，提高了工作效率，對于實驗操作具有重要意義。將神經元實現的邏輯運算AND,NAND和OR級聯解決了線性不可分的分類問題。通過與別人結果的對比，證明本文方法的有效性。為了進一步檢驗神經元級聯的可擴展性，本文構建了一個3人表決器。然后，基于DNA鏈置換實現了科學家的分類。最后通過對比Visual DSD[21]的實驗結果，驗證了本文的準確率明顯高于其他的方法。本文的其余部分安排如下：第2部分介紹Visual DSD和實驗結果,第3部分對文章進行總結。

2 應用與仿真

2.1 Visual DSD

Visual DSD是一種編程語言，可以用于實現DNA電路的組裝。它的基本組成要素包括Domain,Toeholds和Branch migration。這種語言假設使用的DNA鏈中不包含任何2級結構，并且可以把某個功能模塊封裝成一個含有參數的函數模塊，從而可以方便地設計大規模的邏輯電路。其中Table選項卡具有輸出表格形式的功能，選項卡中的數據可以被保存成為CSV文件或TSV文件。除了將DNA分子編譯為化學反應之外，該工具針對模擬器有3種選擇，包括Stochastic模擬器、Deterministic模擬器和準時(Just In Time,JIT)模擬器。

本文使用的是Deterministic模擬器，通過時間的推移產生光滑、確定的圖像，運行Visual DSD時默認選擇的語義模型為default，分子被識別為分支遷移。采用的反應參數如下：泄漏反應的反應速率常數為10–18mol·s–1·L–1，其中toehold的堿基長度為6個，綁定速率常數為3.0×10–13mol·s–1·L–1，釋放速率常數為0.1126 s–1。

2.2 邏輯運算的實現

本文通過化學反應來實現邏輯運算。根據輸入的邏輯值設置輸入的DNA信號濃度。A的輸入代表是否存在邏輯值。如果不存在A，則A的邏輯值表示為“0”，將不會產生E。如果存在A，則A的邏輯值表示為“1”,E的最終濃度將由D的初始濃度確定。權重門必須設計成具有相同的結構，該設計是為了使每個門對每組輸入產生不同的響應。其中式(1)和式(2)分別表示權重反應的過程。單鏈B和權重門D執行鏈置換反應，為下一次求和做準備。邏輯值“1”或“0”用于表示輸入鏈B以及C是否存在。其中D為權重門，箭頭右側E,F為輸出，G表示產生的廢物鏈。C與B具有同樣的功能，代表輸入鏈

當實現邏輯運算AND時，生成的DNA鏈E和F相加來實現求和的過程。式(3)為反應公式，L表示權重之和

然后，通過“成對湮滅”進行比較來確定最后的贏家。加入湮滅鏈(用字母M表示)和幫助鏈(用字母N表示)，與生成的鏈L發生反應。其中M限制了輸出鏈的再次生成，同時也促進了競爭反應的發生。式(4)代表反應進行湮滅的過程。在這些過程的基礎上，本文實現的神經元結構如圖1所示。

圖1 神經元結構圖

WTA是一種非線性動力學效應，它可以選擇性地放大某一個輸出。本文將從基于Genot等人[18]實施的電路進行改變，實現的過程如圖2所示。從網絡形式上來說，本文實現的是前饋網絡，前饋相比反饋速度較快，在需要得到一個輸出時，輸入信號可以被事先推算出來。在網絡趨于穩定時，通過最后物種的量顯示出結果。這與以反饋形式實現的有所不同[17]，反饋電路會有物種不斷生成，然后上一步的輸出作為下一次反應的輸入。就反應的時間而言，相比帶有反饋的電路反應的時間更長，然而本文采用的方法需要的時間則更短。通過控制輸入量和M的值來控制反應時間。其次，WTA神經網絡不需要添加雙軌，這也減少了DNA鏈的數量，降低了整個網絡運行的復雜性。并且WTA神經網絡具有普遍的全局效應：一個輸出的變化會立即影響所有其他輸出的復制速度。

圖2 實現AND的過程

首先通過單鏈,與雙鏈{A11^*}:[2],{A22^*}:[2]發生鏈置換反應，其中置換出的單鏈<2 Y1^>是基于DNA鏈置換的質量作用動力學完成求和操作。最重要的一點是在電路中加入了N單鏈，與上一步置換出的求和單鏈<2 Y1^>通過湮滅鏈[2*2*]發生湮滅反應。當N單鏈與求和單鏈<2 Y1^>的競爭趨于穩定狀態時，得到最終的結果。WTA神經網絡先進行求和，然后DNA鏈之間進行競爭，這些過程避免了DNA鏈的再生，使電路容易實現。仿真結果如圖3所示，神經元實現邏輯運算AND。圖3(b)、圖3(c)、圖3(d)中單鏈<2 Y1^>首先呈現出上升趨勢，其原因是實現求和的一個過程，然后進一步與加入的N鏈發生競爭。最后通過DNA鏈的相互抵消呈下降趨勢，當趨于穩定時得到最后的結果。單鏈<2 Y1^>代表正信號“1”，單鏈代表負信號“0”。在圖3(a)中輸入為“00”，圖3(b)中輸入為“01”，圖3(c)中輸入為“10”，此時單鏈變為“on”，表示輸出信號為“0”。在圖3(d)中輸入為“11”，單鏈<2 Y1^>變為“on”，表示輸出信號為“1”。

圖3 神經元實現邏輯運算AND

通過利用神經元實現邏輯運算NAND，它的仿真結果與AND相反，不同的是在此基礎上又增加了一條N鏈。通過使用神經元實現邏輯運算OR，與AND過程的實現一致，但是需要調整M的值。

單個神經元可以實現單層感知器的功能，即實現線性可分的分類。如邏輯運算AND,NAND和OR能夠進行分類。但是，對于線性不可分的問題，這種方法就不是那么方便。因此，在神經元實現邏輯運算AND,NAND和OR的基礎上，可以級聯形成WTA神經網絡，來解決復雜的線性不可分問題。通過WTA將兩個相同的輸入分為一個類，將另外兩個不同的輸入分為另一個類，因此應用WTA神經網絡可以解決線性不可分問題。在實現邏輯運算XOR時，第1層用神經元實現邏輯運算NAND和OR，其輸出作為下一層邏輯運算AND的輸入。仿真結果如圖4所示。WTA神經網絡實現邏輯運算XOR。輸出單鏈<2 Z1^>表示信號“1”，單鏈表示信號“0”。在圖4(a)中輸入為“00”，圖4(d)中輸入為“11”，單鏈的狀態為“on”，表明當輸入為相同時，輸出信號為“0”。在圖4(b)中輸入為“01”，圖4(c)中輸入為“10”，單鏈<2 Z1^>的狀態為“on”，表明當輸入不同時，輸出信號為“1”。

圖4 WTA實現XOR的仿真圖

在本文中，對比了Wang等人[22]的工作。關于電路的輸入，Wang等人[22]采用雙軌作為輸入，如圖5所示。然而我們采用單軌，通過級聯神經元構造的邏輯運算AND,NAND和OR來實現XOR，其中WTA神經網絡抽象結構如圖6所示。其次，雙鏈的結構也有所不同，Wang等人[22]使用帶tether的雙鏈，本文利用普通鏈置換反應的雙鏈。盡管Wang等人[22]實現了對邏輯運算XOR的分類，但是在橫坐標中，可以看到它的反應時間較長，相比我們的反應時間更短。因此，本文分析，雙軌的加入以及帶有tether的雙鏈都是影響最終反應時間的因素。在本文的實驗中，NAND的實現不僅解決了NOT門問題，而且避免了雙軌，電路結構簡單，從而證明本文采用方法的有效性。

圖5 采用AND和OR實現的雙軌XOR

圖6 WTA神經網絡實現XOR

2.3 3人表決器的實現

為了驗證神經元級聯的可擴展性，本文將電路從單層WTA延伸到多層，設計了一個3人表決器，簡化的神經網絡結構如圖7所示。在這里用字母A,B和C分別表示3位評委，每位評委都有投票權，然后根據投票結果判定是贊成還是反對。如果評委A投票通過，則用邏輯值“1”表示輸入。評委B,C沒有投票通過，這意味著輸入為邏輯值“0”。3位評委A,B和C每個人的投票結果作為輸入，字母F表示3位評委最后的投票結果。在3位評委進行投票時遵守少數服從多數的規則，即只有兩個或兩個以上的評委投票贊成，則代表挑戰者挑戰成功(輸出為“1”)；否則，挑戰者將被淘汰(輸出為“0”)。3人表決器的仿真結果如圖8所示。

圖7 3人表決器的WTA簡化結構圖

從圖8可以看出，圖8(d)中輸入為“011”，圖8(f)中輸入為“111”，此時獲得的票數為兩個或兩個以上時，輸出為用邏輯值“1”表示，這意味著3位評委均同意，結果表明挑戰者挑戰成功。如圖8(a)中輸入為“000”，圖8(b)中輸入為“001”，圖8(c)中輸入為“010”，圖8(e)中輸入為“100”，說明當評委沒有進行投票或只有一票時，輸出為<2 M0^>用邏輯值“0”表示，表明挑戰者以失敗而告終。另外，當輸入為“101”和“110”時，也會表現出同樣的效果。

圖8 3人表決器的仿真圖

2.4 科學家預測的實現

為了驗證WTA神經網絡的計算能力，本文實現了對科學家的分類，分類電路的結構如圖9所示。圖9(a)展示了問題與科學家的對應關系。當肯定回答時，即“1”；當否定回答時，即“0”；當不確定時，顯示“?”。圖9(b)中，當輸入為0011時，可以判斷為第3位科學家S3，設計了WTA神經網絡的抽象圖。圖10顯示了如何使用與Cherry等人[20]相同的結構來競爭實施WTA神經網絡。本文使用前饋電路，上一層的輸出發送到下一層，并且每一層之間沒有反饋。也就是說，電路上的任何點都將朝該方向前進，并且不會返回到原始點。

圖9(a)問題與科學家的對應關系。通過回答問題，每個科學家都擁有一個屬于自己的編號，如科學家香農由(0011)表示。圖9(b)WTA神經網絡抽象圖。通過判斷輸入鏈X1～X4，直到整個網絡響應穩定，判斷出最后的獲勝者。

圖9 分類電路的結構

這里實現分為3個步驟。首先，在圖10(a)中，輸入鏈Xi催化與權重Wij進行反應，并轉化成中間產物。為了連續產生輸入，下游連接的燃料對雙鏈進行催化。只要有足夠的燃料鏈，輸入鏈就不會受到影響。其次，從圖10(b)開始，同一神經元內的所有中間物種與權重發生鏈置換反應，實現求和Sm。最終，由鏈置換產生的總和物種彼此之間將相互破壞，直到一個獲勝者最終脫穎而出。電路如圖10(c)所示。如果僅存在Sm，它將與湮滅發生反應，并且不會消耗任何物種。同樣，產物Sn的存在也是僅與湮滅反應，并且不會被消耗。只有當生成的兩個物種同時存在時，才顯現出湮滅存在的價值。在本文中DNA鏈之間以湮滅的形式實現，從某一個程度上說，這就是它比Genot等人[18]的方法獲得更好結果的原因。基于對不完整信息的“喚醒”，實現了對科學家的分類。輸入值采用Qian等人[17]的補充材料圖S17a。其中，在網絡加權算法和輸入鏈的濃度均與Genot等人[18]的實現一致，通過更改網絡結構，輸入不完整的信息可以對科學家進行正確分類。

圖10(a)釋放中間物質。輸入鏈與權重反應生成中間物種，從而為下一步求和創造了條件。燃料鏈的加入催化生成的雙鏈不斷產生輸入單鏈。圖10(b)求和。中間物種與雙鏈發生鏈置換反應以執行求和運算。圖10(c)湮滅。所得的求和物種發生成對湮滅反應，最后通過剩余數量確定結果，判別具體的某一位科學家。

圖10 WTA神經網絡的DNA實現

作為比較，Genot等人[18]實現的電路使用了28條DNA鏈，本文的輸入使用了34條。就鏈的數量而言，盡管不如Genot等人[18]的簡化。但從最終效果來看，Genot等人[18]的14個輸入中只有兩個可以分類。然而對于同樣的輸入，在本文中采用的方式能夠對其中的13個輸入進行正確的分類。通過計算最終完成的任務量，他們的方法僅完成了14%的任務(14個圖僅實現2個)。然而通過計算任務完成量，本文達到了92%(14個圖實現了13個)。執行的仿真結果如圖11所示。因此，湮滅鏈的選擇有很重要的意義，湮滅鏈的加入使得網絡更出色地完成任務。另外，由于缺乏輸入信息以及特殊的結構，Qian等人[17]未能對補充材料S17a進行正確的分類。

由圖11得知，當圖11(b)中輸入為???0，被分為第1類；當圖11(a)中輸入為????、圖11(c)中輸入為??1?、圖11(e)中輸入為1???、圖11(f)中輸入為???1時，被分為第2類；當圖11(d)中輸入為?0??，被分為第3類；在其他的8種情況中，除了輸入?0?0無法識別，網絡對其余輸入都能夠進行分類。[Fuel][0]=1700 nmol·L–1,[N][0]=440 nmol·L–1,[M1][0]=850 nmol·L–1,[M2][0]=3400 nmol·L–1,[M3][0]=1800 nmol·L–1,[M4][0]=1700 nmol·L–1。

圖11 湮滅方法實現科學家模擬圖

3 結束語

本文通過對Genot等人[18]實施的“猜心術”游戲的電路進行改變，設計了以神經元形式實現的基本邏輯運算AND,NAND和OR。由于非線性計算成本高昂，所以本文中神經元在執行AND,NAND和OR邏輯運算時，不涉及非線性計算。通過將神經元級聯為WTA神經網絡完成了復雜的線性不可分問題。另外，為了驗證實現神經元級聯的可擴展性，創建了一個3人表決器，并在Visual DSD上對電路進行仿真，獲得很好的實驗結果。然而，為了驗證所采用方法的可擴展性，還實現了科學家的分類，并且通過與前人工作的比較證明了該方法的有效性。通過使用DNA鏈置換電路實現WTA網絡時，避免采用雙軌作為輸入。這不僅減少了DNA鏈的數量，也降低了網絡的復雜度，這樣提高了工作效率。

神經網絡中權值的設置是處理信息的重要方式之一，但是在DNA生化反應中不斷更新權值是不容易實現的。因此本文是采用灌輸式學習，將權值設置為固定值，此外這種學習是一次性的。另外，由于采用的濃度都是正值，這種設計的局限性在于不容易處理負值。盡管本文實現的網絡規模相對較小,但最后的結果還是能夠說明:DNA鏈置換技術在分子計算領域具有的潛在能力。此外，通過DNA鏈置換技術構建的神經網絡一方面借助可變增益放大器[23]，用于處理模擬輸入，從而可以進行更廣泛的信號分類任務。另一方面，還可以應用核酸反饋控制[24]，使用發夾的可再生蹺蹺板結構[25]等。在未來的工作中，提高鏈利用率和負值的加入，盡可能減少可逆反應，將仍是我們研究的重點。將邏輯運算與神經網絡、納米技術等結合，以構建更復雜的計算，DNA鏈置換將具有更廣闊的前景。