崔建中,殷志祥,楊 靜

(1. 安徽理工大學(xué)電氣與信息工程學(xué)院, 安徽 淮南 232001; 2.淮南聯(lián)合大學(xué)計算機系, 安徽 淮南 232038; 3.安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院, 安徽 淮南 232001)

DNA鏈置換是一種新穎的動態(tài)自組裝技術(shù)。利用DNA鏈置換來設(shè)計納米級的智能裝置是目前納米技術(shù)、DNA自組裝等許多領(lǐng)域的研究熱點。文獻(xiàn)[1]基于鏈置換設(shè)計了可‘行走’的DNA鑷子。文獻(xiàn)[2]利用鏈置換實現(xiàn)了Hopfield神經(jīng)網(wǎng)絡(luò)，可在分子尺度上進(jìn)行識別、決策。文獻(xiàn)[3]利用鏈置換設(shè)計了一種分子運輸裝置，可順時針或逆時針旋轉(zhuǎn)。文獻(xiàn)[4]利用兩種發(fā)夾結(jié)構(gòu)的DNA作為模板，線性結(jié)構(gòu)的DNA單鏈誘發(fā)鏈置換，設(shè)計了納米尺度的鍵盤鎖。文獻(xiàn)[5]首次在自組裝模型中將DNA鏈置換和熒光標(biāo)記結(jié)合，解決了0-1規(guī)劃問題。DNA 電路由于其高度的可編程性和多功能性而被廣泛用于開發(fā)生物計算設(shè)備，因此文獻(xiàn)[6]提出基于DNA鏈置換的模擬計算DNA電路系統(tǒng)。文獻(xiàn)[7]提出了統(tǒng)計推理模型，使用鏈置換實現(xiàn)該模型，并模擬求解了“Read your mind”。

早期的DNA自組裝主要圍繞著以DNA分子作為組裝材料，通過設(shè)計DNA編碼，依據(jù)堿基互補配對規(guī)則，DNA分子會自發(fā)形成具有一定剛性的初級結(jié)構(gòu)，并以此結(jié)構(gòu)作為基本單元，進(jìn)一步組裝成具有一定幾何形狀的二維、或三維結(jié)構(gòu)。近年來出現(xiàn)的DNA鏈置換技術(shù)是建立在反應(yīng)的動力學(xué)平衡基礎(chǔ)上，具有原理簡單，反應(yīng)過程可編程，易模塊化，可靈活地組成級聯(lián)電路等特點，從而引起了來自多學(xué)科眾多學(xué)者廣泛的關(guān)注[8-12]。

本文基于鏈置換，提出了利用DNA鏈的濃度來判斷某種0-1組合是否為可行解的計算模型。該計算模型將背包問題的約束條件轉(zhuǎn)化為對應(yīng)數(shù)據(jù)池中不同種DNA鏈的濃度，根據(jù)可行解不會產(chǎn)生熒光來并行地搜索所有可行解，最終得到背包問題的最優(yōu)解。該模型嘗試解決目前DNA計算領(lǐng)域存在的問題，如：計算的中間結(jié)果需要多次分離、需要人工干預(yù)計算過程，從而造成計算的自動化程度低。這些問題的解決必定會大大提高DNA計算的可靠性和所求問題的規(guī)模。

1 鏈置換

支點介導(dǎo)的DNA鏈置換(Toehold-Mediated DNA strand displacement)按反應(yīng)過程分為兩類：不可逆鏈置換和可逆鏈置換。其中不可逆鏈置換是指， 輸入DNA鏈與模板鏈的支點(Toehold)結(jié)合，隨后分支遷移(Branch Migration)結(jié)合模板的識別序列，置換出模板上已雜交的鏈的過程?？赡骀溨脫Q是指多條DNA鏈競爭結(jié)合與之互補的模板鏈。原理如圖1所示。圖中實心、空心箭頭表示反應(yīng)的方向。

圖1 可逆鏈置換反應(yīng)的原理示意圖

為方便討論，引入記號<…>來表示單鏈。如在圖1中，DNA鏈5’-2-T-1-3’(左上)，省略5’和3’端、并保留鏈的極性，簡記為<2，T，1>。有時為突出某條鏈上的一段序列，用不帶<…>符號的字母或數(shù)字表示該序列，如支點序列T*。輸出鏈<3，T，2>先與模板鏈結(jié)合形成部分雙鏈的結(jié)構(gòu)。圖中T*為T的補(右上)。該結(jié)構(gòu)中，輸出鏈的序列3仍是單鏈，中間是T2序列形成的雙鏈部分，模板鏈5’端的T*序列為單鏈，記該結(jié)構(gòu)為<3，2∶2*>，冒號代表該部分形成雙鏈(省略了雙鏈中支點序列和模板5’端的支點序列)。因為可逆鏈置換中，支點序列的編碼是唯一的。鏈<3，T，2>結(jié)合<3，2∶2*>的支點T*(圖1第二行)，隨后發(fā)生分支遷移逐漸結(jié)合識別序列2*(圖1第三行)，置換出鏈<3，T， 2>， 同時形成<2∶2*，1>。冒號的位置表示在新的DNA鏈中，序列1在3’端。該反應(yīng)過程在圖1中用實心箭頭表示。隨著反應(yīng)進(jìn)行，鏈<2，T，1>數(shù)量不斷減少，被置換出的鏈<3，T，2>數(shù)量逐漸增加，鏈置換反向進(jìn)行，直至動力學(xué)平衡，該反應(yīng)過程在圖1中用空心箭頭表示。將可逆鏈置換用動力學(xué)方程表示如下

<2，T，1>+<3，2∶2*>?<3，T，2>+<2∶2*，1>

鏈置換反應(yīng)的速率可通過支點的長度和序列組成進(jìn)行調(diào)控。研究結(jié)果表明，支點長度為0～6個堿基時，反應(yīng)的速率呈指數(shù)增加，并在6個堿基時達(dá)到最大。另外，支點的序列組成中，G/C含量越高，反應(yīng)速率越快。巧妙地設(shè)計支點的長度，序列組成及鏈的相對濃度可以對反應(yīng)進(jìn)行較精確地控制，如圖2所示。

圖2 支點長度控制反應(yīng)原理示意圖

(1)若<2，T，1>C小于<2∶2*>C

<2，T，1>+<3，2∶2*>+<2∶2*>?<3，2∶

(2) 若<2，T，1>C大于<2∶2*>C

可逆鏈置換組成級聯(lián)電路進(jìn)行運算時，往往要求需要對鏈進(jìn)行放大，且放大倍數(shù)能根據(jù)問題的要求靈活地設(shè)置。圖3給出了利用DNA鏈的相對濃度來實現(xiàn)對輸入鏈放大ω倍的原理。

圖3 輸入鏈的放大

圖3中，鏈<2，T，1>作為輸入鏈，<3，T，2>作為輸出鏈，引入燃料鏈<4，T，2>，它與輸入鏈、輸出鏈競爭模板鏈。圖3第2行給出了輸入鏈<2，T，1>置換輸出鏈<3，T，2>，圖3第3行給出了燃料鏈<4，T， 2>反向置換輸入鏈<2，T， 1>。設(shè)輸入鏈的初始濃度為1×，輸出鏈與模板鏈的初始濃度為ω×(ω>1)，燃料鏈的初始濃度為2ω×。未加入輸入鏈時，輸出鏈與模板鏈形成的結(jié)構(gòu)<3，2∶2*>與燃料鏈<4，T，2>穩(wěn)定共存。加入輸入鏈時，誘發(fā)鏈置換。輸入鏈每次置換出一條輸出鏈，燃料鏈再次將輸入鏈反向置換出來。輸出鏈也參與競爭模板鏈。 但由于燃料鏈的相對濃度大于輸出鏈，反應(yīng)更傾向燃料鏈。達(dá)到動力學(xué)平衡時，輸入鏈的相對濃度幾乎不變，仍然為1×， 燃料鏈近似為(2ω-ω)×，輸出鏈<3，T， 2>從結(jié)構(gòu)<3，2∶2*>中置換出，相對濃度近似為ω×，燃料鏈與模板形成結(jié)構(gòu)<4，2∶2*>的相對濃度近似為ω×。上述輸入鏈放大ω倍可用動力學(xué)方程表示如下

目前鏈置換的研究主要是設(shè)計組合電路的基本單元，用這些單元搭建電路來實現(xiàn)特定的功能，如自然數(shù)素性判定問題[13]、編碼器邏輯運算[14]。利用鏈置換來求解組合優(yōu)化問題，國內(nèi)還鮮見報道。本文提出了一種背包問題的計算模型，模型的初始數(shù)據(jù)池中僅有O(n)種單鏈DNA，熒光判解，計算過程可自動進(jìn)行，無需人工干預(yù)。

2 背包問題的計算模型

背包問題由Dantzig在1956年提出，是組合優(yōu)化中一個NP-難問題。2014年，文獻(xiàn)[15]利用三鏈結(jié)構(gòu)相對更穩(wěn)定的特點，給出該問題的DNA三鏈計算模型。

背包問題描述為：給定一個可容納重量為c的背包和n種物品，每種物品的重量為ωi(i=1，2，…，n)單價為pi(i=1，2，…，n)。設(shè)若物品i被選擇放入背包，則xi=1；否則xi=0(i=1，2，…，n)。如何選擇物品使背包的總價最高? 即

(1)

xi=0，1

下面討論(1)所對應(yīng)的背包問題的算法。

步驟1：編碼；

步驟2：根據(jù)背包問題的約束條件確定每種鏈的相對濃度，建立初始數(shù)據(jù)池；

步驟3：對每種可能的物品選擇，根據(jù)熒光判斷是否為可行解；

步驟4：比較各可行解對應(yīng)的目標(biāo)函數(shù)值，從而得到最優(yōu)解。

對應(yīng)算法的步驟4，將可行解對應(yīng)的目標(biāo)函數(shù)加以比較，最終得到所給背包問題的最優(yōu)解。

3 結(jié)論

生物計算模型的空間復(fù)雜度用DNA鏈的種類來衡量。對于本文提出的背包問題的計算模型，需要編碼3n+3種寡聚核苷酸片斷，利用這些編碼合成2n+3種鏈DNA構(gòu)成初始數(shù)據(jù)池，數(shù)據(jù)池中DNA鏈種類正比于背包問題所含變量個數(shù)。 因此， (1)該模型的空間復(fù)雜度為O(n)； 為判斷某0-1組合是否為可行解，需要將表示該0-1組合的DNA鏈被加入到數(shù)據(jù)池誘發(fā)鏈置換，再根據(jù)是否會產(chǎn)生熒光來判斷該組合是否為可行解。所有解的判斷可并行完成。在這一過程中，計算的中間結(jié)果無須分離、計算過程可自動完成，無須人工干預(yù)。因此，(2)該模型的時間復(fù)雜度是O(1)；另外，由于該模型僅使用了DNA鏈置換和熒光讀解這兩種相對成熟的生物技術(shù)，因而(3)該模型的可靠性高。

本文對組合優(yōu)化中一個NP-難問題、背包問題給出了鏈置換的計算模型。該計算模型將背包問題的約束條件轉(zhuǎn)化為對應(yīng)數(shù)據(jù)池中不同種DNA鏈的濃度，根據(jù)可行解不會產(chǎn)生熒光來并行地搜索所有可行解，最終得到背包問題的最優(yōu)解。