麻晶晶 許 進

①(山西財經(jīng)大學(xué)統(tǒng)計學(xué)院 太原 030000)

②(北京大學(xué)信息科學(xué)技術(shù)學(xué)院 北京 100871)

1 引言

納米技術(shù)的研究已經(jīng)取得了很大的進步，尤其是由于DNA所具有的特殊的性質(zhì)，DNA分子已經(jīng)被用來構(gòu)建不同的納米組件和生物材料。DNA納米技術(shù)不僅為納米尺度的材料構(gòu)建提供了新的方法和技術(shù)，而且在DNA計算、納米尺度的生物機器和基因治療等方面也具有特殊的用途。

利用DNA分子構(gòu)建納米尺度的組件是通過自組裝的方式。在自然界中，自組裝是一種非常常見的形成系統(tǒng)的方式。在生物系統(tǒng)中，生物有機體的細胞是由很多種生物分子通過自組裝形成的，同時，生物有機體利用生物化學(xué)方法來控制它自身的分子和化學(xué)活動。分子計算將生物有機體的生物化學(xué)過程與電子微處理器控制電子機械元件的過程聯(lián)系起來，提出了一種生物化學(xué)算法，這是一種全新的計算模型。

DNA自組裝在生物有機體中也是非常常見的，例如兩條具有互補的黏性末端的DNA單鏈能夠雜交形成雙鏈，這個過程是由一系列的非共價鍵實現(xiàn)的，例如氫鍵、范德華力、疏水性作用和靜電力等等。因此分子計算可以通過特定實驗室條件下的DNA分子自組裝的生物化學(xué)過程來實現(xiàn)。

目前，利用DNA的自組裝指導(dǎo)納米顆粒形成3維結(jié)構(gòu)的技術(shù)極大地促進了一些基本的科學(xué)問題的研究。Sharma等人[1]設(shè)計了一種利用DNA-納米金顆粒共聚體的自組裝過程來構(gòu)建一種納米金3維管狀結(jié)構(gòu)的方法，這種方法可以通過控制納米金顆粒的大小構(gòu)建不同的結(jié)構(gòu)。Mastroianni等人[2]報道了一種構(gòu)建3維納米金結(jié)構(gòu)的方法，他們利用修飾了DNA鏈的納米金顆粒的自組裝過程構(gòu)建了一種金字塔結(jié)構(gòu)，并且通過調(diào)整納米金顆粒的大小構(gòu)建了一種3維的手性結(jié)構(gòu)。近年來關(guān)于DNA與納米顆粒的研究也取得了很大的進展[3–9]。Dong等人[10]提出了用于求解圖的連通度問題的DNA-納米顆粒共聚體的自組裝計算模型，列舉了求解7個頂點的圖的連通度問題的具體設(shè)計方法。Zhang等人[11]基于DNA-納米顆粒共聚體的自組裝，構(gòu)建了不同種類的邏輯門，并且用實驗實現(xiàn)了這些邏輯門的計算和檢測。殷志祥等人[12]在DNA折紙基底上建立了一個與非門計算模型，通過DNA折紙基底上是否還保留納米金顆粒來顯示計算結(jié)果的真假。

本文提出一種DNA計算模型，利用DNA-納米金顆粒共聚體的自組裝來解決圖論中的一個NP完全問題——最大匹配問題。根據(jù)模型我們設(shè)計了能夠基于一個具體的圖進行自組裝的特殊的DNA-納米金顆粒共聚體，然后利用一系列的實驗方法來獲得最終的解。這種生物化學(xué)算法可以極大地降低求解最大匹配問題的復(fù)雜度，這將為DNA自組裝計算模型提供一種切實可行的方法。

2 DNA-納米顆粒共聚體

納米顆粒具有特殊的識別性質(zhì)，生物分子具有信息存儲能力，生物分子還能指導(dǎo)納米顆粒形成空間立體結(jié)構(gòu)，因此納米顆粒與生物分子的共聚體在生物診斷和納米技術(shù)領(lǐng)域具有很好的應(yīng)用前景。構(gòu)建納米顆粒和生物分子的共聚體有很多種可行的方法，如使納米顆粒與生物素、抗生物素蛋白、抗體、抗原、多肽、蛋白質(zhì)等結(jié)合。在這些不同的分子中，DNA由于它內(nèi)在的可編程能力吸引了越來越多的注意力。

當(dāng)DNA分子的堿基對大約是12個時，它們在室溫下是熱力學(xué)穩(wěn)定的。12個堿基對的長度大約是4 nm，基本上接近一個納米顆粒的大小，并且這些堿基對已經(jīng)足夠用來指導(dǎo)納米顆粒完成預(yù)先設(shè)計好的自組裝過程。這種卓越的性能已經(jīng)被用來形成納米晶體的3維聚集[13]，將納米晶體連接在表面[14]，構(gòu)建納米晶體的小集合[15–17]等。在這些類似的研究中，DNA-納米顆粒共聚體的共同特點是如圖1所示的一個納米顆粒上連接了很多條DNA單鏈。

圖1 DNA-納米顆粒共聚體

對于診斷學(xué)來說，精確地控制每一個納米顆粒上連接的寡核苷酸鏈的數(shù)目是至關(guān)重要的，因為有時僅僅檢測是否存在某些序列是不夠的，而定量地分析雜交的狀況通常是十分必要的。Zanchet等人[18]展示了一種通過電泳來分離連接了圖2所示的不同數(shù)目的寡核苷酸單鏈的納米顆粒的方法。該方法通過電泳來分離不同的DNA-納米金顆粒共聚體。納米金顆粒在高離子強度的緩沖溶液中是非常穩(wěn)定的，而這種緩沖溶液對于DNA的雜交反應(yīng)來說是一種必要的條件。除此之外，在DNA鏈的末端修飾一個巰基，通過巰基將DNA連接到納米金顆粒上也是簡便易行的。通過調(diào)整DNA與金顆粒的比例，可以控制每個金顆粒上連接的DNA鏈的數(shù)目。

圖2 連接了不同數(shù)目DNA單鏈的DNA-納米金顆粒共聚體

凝膠電泳在生物學(xué)中是一項非常有用的技術(shù)，例如在分離不同大小的DNA分子時。在凝膠電泳中，帶電的顆粒在電場下的凝膠中移動，顆粒的遷移率取決于顆粒的電荷和大小。圖3展示了由于納米顆粒上連接了不同數(shù)目的DNA鏈，納米顆粒的遷移率也發(fā)生了很大的變化。

圖3 瓊脂糖凝膠電泳中連接了不同數(shù)目的DNA鏈的納米顆粒的位置

盡管文獻[18]的方法能夠控制每一個納米金顆粒上連接的DNA鏈的數(shù)目，但是每一個納米金顆粒上連接的DNA鏈的種類都是相同的。2013年，Zhang等人[19]展示了一種新的方法，該方法能夠選擇性地控制每一個納米金顆粒上連接的DNA鏈的數(shù)目和種類，即具有不同序列的DNA鏈能同時連接到一個納米金顆粒上。

3 最大匹配問題

無向圖G=(V,E)中具有頂點集V={v1,v2,···,vn}和邊集E={e1,e2,···,em}，其中m為邊數(shù)，n為頂點數(shù)。圖G的子圖Gsub=(Vsub,Esub)滿足Vsub∈V,Esub∈E。若圖Gsub中任意兩條邊ek,ed在G中沒有公共的頂點，則Esub為G的一個匹配。具有最多邊的匹配稱為圖G的最大匹配。求解圖的最大匹配是一個NP完全問題。本文以圖4中的簡單無向圖G為例來說明基于DNA-納米顆粒共聚體求解最大匹配問題的算法。

圖4 簡單無向圖G

4 基于DNA-納米顆粒共聚體求解最大匹配問題的算法

用DNA-納米顆粒共聚體代表圖G的每一個頂點，用DNA單鏈代表圖G的每一條邊。通過DNA-納米顆粒共聚體與DNA單鏈分子的自組裝形成代表圖G信息的圖結(jié)構(gòu)。然后利用鏈置換反應(yīng)來刪除邊。刪除邊后的子圖Gsub是否為圖G的最大匹配，本文通過瓊脂糖凝膠電泳實驗來檢測。計算的過程包括以下4步：(1)編碼DNA鏈和構(gòu)建自組裝過程中所需的DNA-納米顆粒共聚體；(2)通過退火形成代表圖G信息的自組裝結(jié)構(gòu)；(3)通過鏈置換反應(yīng)刪除邊；(4)檢測正確的解。

4.1 編碼

圖5展示了代表頂點的DNA-納米顆粒共聚體結(jié)構(gòu)和代表邊的DNA鏈以及它們的雜交方式。每一個頂點都由一個DNA-納米顆粒共聚體結(jié)構(gòu)來表示。DNA-納米顆粒共聚體結(jié)構(gòu)根據(jù)圖G中具體的頂點進行設(shè)計。如圖5所示，以頂點v1和頂點v4為例來展示我們所設(shè)計的DNA-納米顆粒共聚體結(jié)構(gòu)。頂點v1的度數(shù)是2，因此圖5中連接了兩條DNA單鏈的DNA-納米顆粒共聚體結(jié)構(gòu)表示頂點v1。頂點v4的度數(shù)是3，因此圖5中連接了3條DNA單鏈的DNA-納米顆粒共聚體結(jié)構(gòu)表示頂點v4。頂點v1和頂點v4之間以邊e4相連，因此用圖5中所示的一條DNA單鏈表示邊e4。如圖5所示，代表邊e4的DNA單鏈能分別與代表頂點v1和頂點v4的DNA-納米顆粒共聚體結(jié)構(gòu)的相應(yīng)序列雜交。此外，在設(shè)計代表邊的DNA單鏈時，還要在單鏈中間設(shè)計一段序列(圖5中代表e4的DNA單鏈上的粉色線段)用于之后需要進行的鏈置換反應(yīng)。實驗中所需的DNA鏈從提供引物合成的生物公司購買，構(gòu)建自組裝過程中所需的DNA-納米顆粒共聚體采用我們在文獻[19]中使用的實驗方法。

圖5 代表頂點的DNA-納米顆粒共聚體和代表邊的DNA鏈及它們的雜交方式

4.2 退火

將代表頂點的所有DNA-納米顆粒共聚體和代表邊的所有DNA鏈在一定的緩沖溶液中混合，在適當(dāng)?shù)臏囟葪l件下DNA序列就可以特異地雜交，這個依據(jù)堿基互補配對的規(guī)則進行特異性雜交過程就是退火反應(yīng)的過程，如圖6所示，退火反應(yīng)之后代表圖G信息的自組裝結(jié)構(gòu)就形成了。

圖6 退火后形成的代表圖G信息的自組裝結(jié)構(gòu)

4.3 鏈置換反應(yīng)刪除邊

求解最大匹配問題的一般算法是依次刪除邊，并測試刪除邊后的子圖是否為最大匹配。以圖G為例，刪除邊的組合數(shù)為26-8，因此需要根據(jù)這些組合分別刪除邊。圖7展示了所用的刪除邊方法，即鏈置換反應(yīng)。在上一步退火反應(yīng)形成的自組裝結(jié)構(gòu)中，為了刪除DTR所代表的一條邊，需要加入其取代鏈dtr。dtr與DTR完全互補，因此能形成圖7所示的雙螺旋結(jié)構(gòu)，并使原來連接在一起的兩個頂點分開。鏈置換反應(yīng)的實驗條件與退火反應(yīng)的實驗條件一樣，均是在合適的溫度條件和緩沖液濃度條件下進行的。

圖7 刪除邊的鏈置換反應(yīng)

圖8展示了刪除邊e1、邊e3和邊e6后的結(jié)構(gòu)。用鏈置換的方法加入邊e1、邊e3和邊e6的取代鏈后，原來退火反應(yīng)形成的自組裝結(jié)構(gòu)就變?yōu)閳D8所示的結(jié)構(gòu)。虛線橢圓圈住的結(jié)構(gòu)為仍然連接在一起的頂點和邊的結(jié)構(gòu)。小橢圓圈住的為頂點v2,v3及邊e2連接在一起的結(jié)構(gòu)，即綠色實線框中所示的兩個納米金顆粒連接在一起的二聚體結(jié)構(gòu)。大橢圓圈住的為頂點v1,v4,v5及邊e4,e5連接在一起的結(jié)構(gòu)，即藍色實線框中所示的3個納米金顆粒連接在一起的三聚體結(jié)構(gòu)。此外，鏈置換反應(yīng)刪除頂點后還形成了代表頂點v6的結(jié)構(gòu)，即紅色實線框中的單個納米金顆粒與DNA連接的共聚體。二聚體結(jié)構(gòu)可以看作一條邊。三聚體結(jié)構(gòu)可以看作具有一個公共頂點的兩條邊。刪除邊e1、邊e3和邊e6后出現(xiàn)了三聚體結(jié)構(gòu)，說明子圖中存在具有公共頂點的兩條邊，也就是說刪除邊e1、邊e3和邊e6后的子圖不是一個匹配。

圖8 刪除邊e1、邊e3和邊e6后的結(jié)構(gòu)

圖9展示了刪除邊e2、邊e4和邊e5后的結(jié)構(gòu)。用鏈置換的方法加入邊e2、邊e4和邊e5的取代鏈后，原來退火反應(yīng)形成的自組裝結(jié)構(gòu)就變?yōu)閳D9所示的結(jié)構(gòu)。虛線橢圓圈住的結(jié)構(gòu)為仍然連接在一起的頂點和邊的結(jié)構(gòu)。從圖9可以看出，刪除邊e2、邊e4和邊e5后，原來退火反應(yīng)形成的自組裝結(jié)構(gòu)變?yōu)槿渴莾蓚€納米金顆粒連接在一起的結(jié)構(gòu)，即紅色框中所示的兩個納米金顆粒連接在一起的二聚體結(jié)構(gòu)。二聚體結(jié)構(gòu)可以看作一條邊，并且沒有三聚體結(jié)構(gòu)出現(xiàn)，說明刪除邊e2、邊e4和邊e5后子圖中的邊都沒有公共頂點，即說明子圖是一個匹配。

圖9 刪除邊e2、邊e4和邊e5后的結(jié)構(gòu)

4.4 瓊脂糖凝膠電泳檢測結(jié)果

經(jīng)過上一步鏈置換反應(yīng)刪除邊后就形成了各種子圖，測試子圖是否為圖的匹配通過瓊脂糖凝膠電泳實驗來進行。具體的方法是預(yù)先合成圖10所示的3種對照。藍色實線框中的是3個納米金顆粒通過兩條DNA單鏈雜交而成的三聚體結(jié)構(gòu)。綠色實線框中的是兩個納米金顆粒通過一條DNA單鏈雜交而成二聚體結(jié)構(gòu)。紅色實線框中的是一個納米金顆粒與DNA的共聚體結(jié)構(gòu)。在瓊脂糖凝膠電泳中，如圖10左側(cè)粉色所示，由于分子量的不同，三聚體結(jié)構(gòu)的電泳帶位于最下方，二聚體結(jié)構(gòu)電泳帶位于中間，最上方的電泳帶是單顆粒的DNA-納米金顆粒共聚體。

圖10 瓊脂糖凝膠電泳的對照

為了測試子圖是否為圖的匹配，就需要分別將子圖進行瓊脂糖凝膠電泳實驗，與對照相比，如果一個子圖的瓊脂糖凝膠電泳結(jié)果出現(xiàn)了三聚體結(jié)構(gòu)的電泳帶就說明該子圖不是圖的匹配，因為三聚體結(jié)構(gòu)表示具有一個公共頂點的兩條邊的結(jié)構(gòu)。值得注意的是，如果一個子圖的電泳結(jié)果出現(xiàn)的電泳帶比三聚體的電泳帶更靠下，說明該子圖也不是圖的匹配，因為更靠下的帶可能是四聚體或更多聚體的情況，都代表子圖的邊具有公共頂點的情況。

如果一個子圖的瓊脂糖凝膠電泳結(jié)果出現(xiàn)了二聚體結(jié)構(gòu)的電泳帶和最上方的單顆粒DNA-納米金顆粒共聚體的電泳帶，并且沒有出現(xiàn)三聚體結(jié)構(gòu)或更高聚體結(jié)構(gòu)的電泳帶，就說明該子圖是圖的匹配，因為沒有出現(xiàn)三聚體結(jié)構(gòu)或更高聚體結(jié)構(gòu)的電泳帶就說明子圖中的邊都沒有公共頂點。檢查具有最多邊數(shù)的匹配即為圖的最大匹配。

5 結(jié)束語

本文用DNA-納米顆粒共聚體代表圖G的每一個頂點，用DNA單鏈代表圖G的每一條邊。通過DNA-納米顆粒共聚體與DNA單鏈分子的自組裝形成代表圖G信息的自組裝結(jié)構(gòu)。然后利用鏈置換反應(yīng)來刪除邊，并通過瓊脂糖凝膠電泳實驗來檢測刪除邊后的子圖是否為圖的最大匹配。本文方法利用了DNA納米技術(shù)的方法和技術(shù)，具有高度的并行性和可靠的結(jié)果檢測能力，極大地降低了求解圖的最大匹配問題的復(fù)雜度。