DNA-納米顆粒共聚體在最大匹配問題中的應(yīng)用

麻晶晶 許 進(jìn)

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

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

1 引言

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

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

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

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

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

2 DNA-納米顆粒共聚體

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

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

圖1 DNA-納米顆粒共聚體

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

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

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

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

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

3 最大匹配問題

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

圖4 簡單無向圖G

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

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

4.1 編碼

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

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

4.2 退火

將代表頂點(diǎn)的所有DNA-納米顆粒共聚體和代表邊的所有DNA鏈在一定的緩沖溶液中混合，在適當(dāng)?shù)臏囟葪l件下DNA序列就可以特異地雜交，這個(gè)依據(jù)堿基互補(bǔ)配對的規(guī)則進(jìn)行特異性雜交過程就是退火反應(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完全互補(bǔ)，因此能形成圖7所示的雙螺旋結(jié)構(gòu)，并使原來連接在一起的兩個(gè)頂點(diǎn)分開。鏈置換反應(yīng)的實(shí)驗(yàn)條件與退火反應(yīng)的實(shí)驗(yàn)條件一樣，均是在合適的溫度條件和緩沖液濃度條件下進(jìn)行的。

圖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)為仍然連接在一起的頂點(diǎn)和邊的結(jié)構(gòu)。小橢圓圈住的為頂點(diǎn)v2,v3及邊e2連接在一起的結(jié)構(gòu)，即綠色實(shí)線框中所示的兩個(gè)納米金顆粒連接在一起的二聚體結(jié)構(gòu)。大橢圓圈住的為頂點(diǎn)v1,v4,v5及邊e4,e5連接在一起的結(jié)構(gòu)，即藍(lán)色實(shí)線框中所示的3個(gè)納米金顆粒連接在一起的三聚體結(jié)構(gòu)。此外，鏈置換反應(yīng)刪除頂點(diǎn)后還形成了代表頂點(diǎn)v6的結(jié)構(gòu)，即紅色實(shí)線框中的單個(gè)納米金顆粒與DNA連接的共聚體。二聚體結(jié)構(gòu)可以看作一條邊。三聚體結(jié)構(gòu)可以看作具有一個(gè)公共頂點(diǎn)的兩條邊。刪除邊e1、邊e3和邊e6后出現(xiàn)了三聚體結(jié)構(gòu)，說明子圖中存在具有公共頂點(diǎn)的兩條邊，也就是說刪除邊e1、邊e3和邊e6后的子圖不是一個(gè)匹配。

圖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)為仍然連接在一起的頂點(diǎn)和邊的結(jié)構(gòu)。從圖9可以看出，刪除邊e2、邊e4和邊e5后，原來退火反應(yīng)形成的自組裝結(jié)構(gòu)變?yōu)槿渴莾蓚€(gè)納米金顆粒連接在一起的結(jié)構(gòu)，即紅色框中所示的兩個(gè)納米金顆粒連接在一起的二聚體結(jié)構(gòu)。二聚體結(jié)構(gòu)可以看作一條邊，并且沒有三聚體結(jié)構(gòu)出現(xiàn)，說明刪除邊e2、邊e4和邊e5后子圖中的邊都沒有公共頂點(diǎn)，即說明子圖是一個(gè)匹配。

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

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

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

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

為了測試子圖是否為圖的匹配，就需要分別將子圖進(jìn)行瓊脂糖凝膠電泳實(shí)驗(yàn)，與對照相比，如果一個(gè)子圖的瓊脂糖凝膠電泳結(jié)果出現(xiàn)了三聚體結(jié)構(gòu)的電泳帶就說明該子圖不是圖的匹配，因?yàn)槿垠w結(jié)構(gòu)表示具有一個(gè)公共頂點(diǎn)的兩條邊的結(jié)構(gòu)。值得注意的是，如果一個(gè)子圖的電泳結(jié)果出現(xiàn)的電泳帶比三聚體的電泳帶更靠下，說明該子圖也不是圖的匹配，因?yàn)楦肯碌膸Э赡苁撬木垠w或更多聚體的情況，都代表子圖的邊具有公共頂點(diǎn)的情況。

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

5 結(jié)束語

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