最大團(tuán)問題的可編程的DNA分子系統(tǒng)計(jì)算模型①

嚴(yán)洋洋, 殷志祥

(安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001)

0 引 言

自從電子自計(jì)算機(jī)問世以來，為人類社會(huì)帶來了巨大的便利，漸漸已經(jīng)成為社會(huì)發(fā)展中不可或缺的一部分。可隨著科技的發(fā)展變遷，對(duì)電子計(jì)算機(jī)的各種要求越來越高，尤其是在智能化，運(yùn)算速度，存儲(chǔ)等方面，一些問題也難以得到很好的解決，如NP—問題，使得人們不得不尋找新的計(jì)算方法。經(jīng)過一系列的研究，DNA分子開始進(jìn)入研究員的視野。DNA分子具有高并行性，高存儲(chǔ)，高特異性，易操作等特性。伴隨著生物化學(xué)與分子生物學(xué)技術(shù)的不斷發(fā)展，以DNA分子這些良好的特性為橋梁的新型計(jì)算方法，使得DNA計(jì)算成為了研究員們的熱點(diǎn)研究領(lǐng)域[1]。

DNA計(jì)算是一種在分子層面借助生物分子技術(shù)進(jìn)行計(jì)算的新方法，具有高容量，高度并行性，微小性等特點(diǎn)，為解決非線性問題提供了一條新的道路。Adelman借助DNA編碼解決了7頂點(diǎn)Hamilton路徑問題，開創(chuàng)了DNA計(jì)算的首例。[2]目前，在DNA計(jì)算領(lǐng)域已經(jīng)取得了巨大的成就，極大的促進(jìn)了計(jì)算機(jī)科學(xué)、生物科學(xué)、化學(xué)、數(shù)學(xué)等學(xué)科的的發(fā)展。DNA自組裝理論的建立，是DNA計(jì)算的亮點(diǎn)之一，由此，研究員利用其特性解決最大團(tuán)問題[3-4]、二部圖完全匹配問題[5]等問題。文獻(xiàn)[6]利用DNA計(jì)算計(jì)算求解可滿足性問題以及文獻(xiàn)[7]中邏輯門模型的構(gòu)建。由于DNA鏈置換反應(yīng)具有很強(qiáng)的靈敏性、高準(zhǔn)確性、自發(fā)性等特點(diǎn)，使得DNA鏈置換技術(shù)成為DNA自組裝發(fā)展中最具特色的一部分。[8-9]

在這里，設(shè)計(jì)了一種基于可編程的DNA分子系統(tǒng)[10]求解最大團(tuán)問題的模型，可以對(duì)該分子系統(tǒng)進(jìn)行編程，編程程序是由一系列DNA指令組成定義反應(yīng)順序的鏈。在該分子系統(tǒng)中，設(shè)計(jì)了在環(huán)部分具有識(shí)別區(qū)域的莖環(huán)結(jié)構(gòu)，將起始雙鏈體作為引發(fā)劑，與化學(xué)發(fā)夾和指令發(fā)夾發(fā)生鏈置換反應(yīng)，形成多聚化學(xué)鏈。首先，借助圖的頂點(diǎn)排列組合出所有可能性組合，生成所有的數(shù)據(jù)池。然后，借助分子系統(tǒng)進(jìn)行篩選，得到滿足團(tuán)定義的所有可能性組合。接著，再檢測(cè)滿足條件的多聚化學(xué)鏈上低聚物，判斷和讀取最大團(tuán)。

1 可編程的DNA分子系統(tǒng)

該DNA分子系統(tǒng)的的匯編程序是由一系列DNA指令組成定義反應(yīng)順序的鏈，合成具有確定序列的低聚物。只需要更改指令集就可重新編程，以進(jìn)行組合合成。

起始雙鏈體(圖1a)具有誘發(fā)作用，它是由一條3′端帶有增長(zhǎng)的低聚物(帶顏色的小圓圈表示)的貨物(Cargo)單鏈與單鏈I形成的雙鏈體結(jié)構(gòu)，并且在鏈I的3′端帶有確定的腳趾。化學(xué)發(fā)夾與指令發(fā)夾，上半部分是其環(huán)區(qū)域，并且有確定的堿基對(duì)序列，在交錯(cuò)反應(yīng)中，能夠與下方的延伸出的腳趾區(qū)互補(bǔ)配對(duì)。在其徑區(qū)域化學(xué)發(fā)夾與指令發(fā)夾的堿基對(duì)序列是相同的，同樣也與起始雙鏈體的莖區(qū)域的堿基對(duì)序列相同。編程的順序最主要依賴于指令發(fā)夾的組裝。指令發(fā)夾的方向是確定的，如：指令發(fā)夾I>A，識(shí)別鏈I，并將其鏈接到A上，指令發(fā)夾A>B，識(shí)別鏈A，并將其鏈接到B上，。兩個(gè)發(fā)夾的單鏈腳趾區(qū)域用于啟動(dòng)發(fā)生雜交反應(yīng)，同時(shí)控制組裝順序，即組裝順序是通過成對(duì)的互補(bǔ)腳趾之間相互作用進(jìn)行編程。終止發(fā)夾是指令發(fā)夾的一種，其作用是用來終止鏈的擴(kuò)張。

圖1a 起始雙鏈體(I：Cargo) 圖1b化學(xué)發(fā)夾

圖1c 指令發(fā)夾 圖1d 終止發(fā)夾

該分子系統(tǒng)的組裝(圖2)是由交錯(cuò)排列的開放的化學(xué)發(fā)夾與指令發(fā)夾通過DNA鏈置換反應(yīng)形成的線性雙鏈體，是一維的雜交鏈反應(yīng)。起始雙鏈體(I：Cargo)，與第一個(gè)指令發(fā)夾I>A的互補(bǔ)的腳趾進(jìn)行DNA雜交反應(yīng)，莖鏈被打開進(jìn)行遷移(沿著紅色箭頭方向)，進(jìn)而導(dǎo)致發(fā)夾的環(huán)區(qū)域開放，形成了四臂分支結(jié)構(gòu)。環(huán)開放后，激活腳趾區(qū)，該區(qū)域指定下一步要添加化學(xué)發(fā)夾A。這時(shí)化學(xué)發(fā)夾A的沒有攜帶貨物的腳趾區(qū)域插入，完成鏈接，形成四臂分支結(jié)構(gòu)。當(dāng)每個(gè)發(fā)夾添加到鏈中時(shí)，其環(huán)開放，然后通過腳趾區(qū)域進(jìn)行鏈雜交，進(jìn)而啟動(dòng)下一階段鏈的增長(zhǎng)，這說明了通過交替添加指令發(fā)夾與化學(xué)發(fā)夾進(jìn)行鏈的擴(kuò)張。形成的雙鏈體的每條鏈都是不連續(xù)的，一條鏈由化學(xué)發(fā)夾組成，一條有指令發(fā)夾組成，組裝的順序是通過成對(duì)的互補(bǔ)腳趾之間相互作用形成進(jìn)行編程的。當(dāng)每個(gè)發(fā)夾添加到鏈中時(shí)，貨物通過遷移，鏈接到新添加的發(fā)夾上，整個(gè)鏈的擴(kuò)張由Ti>Tend,終止。

2 最大團(tuán)問題的可編程的DNA計(jì)算模型

2.1 最大團(tuán)的基本定義

設(shè)簡(jiǎn)單圖G=(V,E)，其中非空集合V是頂點(diǎn)集，E是邊集。給定一個(gè)圖，其任意頂點(diǎn)子集都有可能是G的團(tuán)。設(shè)U是G的一個(gè)頂點(diǎn)子集，對(duì)于頂點(diǎn)子集U中任意兩頂點(diǎn)u,v，均與E中的邊鄰接，則U是G的團(tuán)。若圖G中的任意團(tuán)都有|U′||U|，則U是G的最大團(tuán)。

2.2 最大團(tuán)基本算法

對(duì)于一個(gè)n頂點(diǎn)的簡(jiǎn)單圖G=(V,E)，其中V={V1,V2,…,Vn}，若G的任意頂點(diǎn)子集都不是G的團(tuán)，則該圖的任意兩頂點(diǎn)都不是鄰接的。

Step1 每個(gè)頂點(diǎn)用一個(gè)化學(xué)發(fā)夾來表示，利用DNA分子系統(tǒng)對(duì)圖G的頂點(diǎn)進(jìn)行設(shè)計(jì)、編碼。排列組合出所有的可能性組合，對(duì)于n頂點(diǎn)的簡(jiǎn)單圖的頂點(diǎn)子集共有2n個(gè)，即生成數(shù)據(jù)池。

Step2 為滿足團(tuán)的定義對(duì)數(shù)據(jù)池進(jìn)行檢測(cè)。借助可編程的DNA分子系統(tǒng)對(duì)圖中任意一個(gè)頂點(diǎn)子集進(jìn)行篩選。不失一般性，設(shè)頂點(diǎn)集Vi={Vi1,Vi2,…,Vik}，其中k≥2。若是Vi在圖G的一個(gè)團(tuán)中，則Vi中任意兩點(diǎn)都是鄰接的。即若兩頂點(diǎn)在同一個(gè)團(tuán)中，則這兩頂點(diǎn)必定鄰接。開始，加入起始雙鏈體(I：Cargo)，與指令發(fā)夾進(jìn)行匹配，激活腳趾區(qū)，然后在腳趾區(qū)進(jìn)行雜交反應(yīng)，進(jìn)而開放發(fā)夾的環(huán)區(qū)域，根據(jù)指定的順序，加入化學(xué)發(fā)夾。于是化學(xué)發(fā)夾由具有識(shí)別作用的腳趾區(qū)開始插入，進(jìn)行雜交反應(yīng)，使得增長(zhǎng)性的低聚物發(fā)生遷移。然后繼續(xù)加入指令發(fā)夾，進(jìn)入下一階段的鏈的擴(kuò)張，最后添加的終止發(fā)夾停止，形成線性雙鏈體。對(duì)k(n≥k≥2)，從大到小逐次檢驗(yàn)，在檢驗(yàn)過程中，需要多次對(duì)圖的頂點(diǎn)進(jìn)行編碼。刪除低聚物不能連接在一起的線性雙鏈體，剩下的都滿足團(tuán)的定義。

Step3 觀察最后的線性雙鏈體中低聚物的個(gè)數(shù)，通過DNA測(cè)序，讀出圖的最大團(tuán)及其頂點(diǎn)。

3 實(shí)例應(yīng)用

以圖3，5頂點(diǎn)簡(jiǎn)單圖為例，頂點(diǎn)集V={1,2,3,4,5}，邊集E={(1,2),(2,3),(3,4),(4,5),(2,5)(2,4)(3,5)}，利用該DNA分子系統(tǒng)進(jìn)行最大團(tuán)問題的求解。

圖2 DNA分子系統(tǒng)組裝機(jī)制

圖3 5頂點(diǎn)的簡(jiǎn)單圖

Step1 將這五個(gè)頂點(diǎn)用分別用五個(gè)化學(xué)發(fā)夾表示，排列出這些頂點(diǎn)的所有可能性組合，生成數(shù)據(jù)池，頂點(diǎn)子集個(gè)數(shù)共有32個(gè)。

Step2結(jié)合2.2中的Step2，檢測(cè)數(shù)據(jù)池，各個(gè)頂點(diǎn)子集進(jìn)行判斷。本例中k的最大值為k=5。對(duì)頂點(diǎn)進(jìn)行編碼，用符號(hào)表示為V1:A，V2：B，V3：C，V4：D，V5:Ti，加入起始雙鏈體(I：Cargo)，開始雜交反應(yīng)，此后按照I>A→A→I>B→B→B>C→C→C>D→D→D>T5→T5→T5>Tend的順序逐次加入。最后加入的T5>Tend用于終止反應(yīng)，形成了線性雙鏈體。

圖4 判斷頂點(diǎn)集V=(1,2,3,4,5)

僅有起始雙鏈體貨物的在鏈上進(jìn)行了遷移，其它代表圖的各個(gè)頂點(diǎn)的發(fā)夾上的貨物沒有完成遷移。因此，該圖本身不是是團(tuán)。

下面逐次對(duì)k(4≥k≥2)進(jìn)行檢驗(yàn)，其中一個(gè)最大的頂點(diǎn)子集V=(2,3,4,5)，判斷是否為圖的團(tuán)。對(duì)圖的各個(gè)頂點(diǎn)重新編碼，用符號(hào)表示為：V2：B'，V3：C′，V4：D′，V5:T5′依照上述步驟，按照I>B′→B′→B′>C′→C′→C′>D′→D′→D′>T5′→T5′>Tend的順序逐次加入進(jìn)行操作。最后可以的得到如圖5所示的線性雙鏈體。鏈上的貨物發(fā)生遷移，增長(zhǎng)的低聚物連接在一起，可以判定頂點(diǎn)集V=(2,3,4,5)可以構(gòu)成圖的一個(gè)團(tuán)。

圖5 判斷頂點(diǎn)子集V=(2,3,4,5)

將低聚物不能連接到一起的線性雙鏈體移除，剩下的都滿足團(tuán)定義。

Step3，最后觀察，滿足團(tuán)定義的線性雙鏈體，讀出最大團(tuán)。經(jīng)過驗(yàn)證，該實(shí)例的最大團(tuán)由頂點(diǎn)集V=(2,3,4,5)構(gòu)成。

4 結(jié) 論

借助DNA計(jì)算求解NP完全問題，可編程性、自主、高并行性，是十分重要的追求。在前文中，主要借助可編程的DNA分子系統(tǒng)求解最大團(tuán)問題。通過起始雙鏈體的誘發(fā)，由化學(xué)發(fā)夾和指令發(fā)夾雜交反應(yīng)交錯(cuò)排列構(gòu)成線性雙鏈體，通過鏈的遷移將可增長(zhǎng)的低聚物轉(zhuǎn)移到每個(gè)發(fā)夾上，最終檢測(cè)低聚物的個(gè)數(shù)來讀取最大團(tuán)。在理論上，對(duì)于圖的規(guī)模沒有限制，技術(shù)上也已經(jīng)成熟，操作簡(jiǎn)單、便利。相信，隨著生物技術(shù)的發(fā)展，DNA計(jì)算將會(huì)用更廣闊的舞臺(tái)，DNA分子自組裝在數(shù)據(jù)存儲(chǔ)、智能機(jī)器也將展現(xiàn)它的巨大潛力。