嚴洋洋, 殷志祥

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

0 引 言

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

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

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

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

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

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

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

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

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

2 最大團問題的可編程的DNA計算模型

2.1 最大團的基本定義

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

2.2 最大團基本算法

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

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

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

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

3 實例應(yīng)用

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

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

圖3 5頂點的簡單圖

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

Step2結(jié)合2.2中的Step2，檢測數(shù)據(jù)池，各個頂點子集進行判斷。本例中k的最大值為k=5。對頂點進行編碼，用符號表示為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 判斷頂點集V=(1,2,3,4,5)

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

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

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

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

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

4 結(jié) 論

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