李 燕，鐘 磊

（南京信息工程大學(xué) 計(jì)算機(jī)與軟件學(xué)院，江蘇 南京 210044）

0 引言

NP完全問(wèn)題是不確定性圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)能解決的問(wèn)題，是國(guó)內(nèi)外算法研究領(lǐng)域的熱點(diǎn)和難點(diǎn)。P＝？NP問(wèn)題的研究受到科學(xué)家們的高度重視，開(kāi)辟模擬生物智能的新路已成為人們研究NP問(wèn)題的新方向。在智能化領(lǐng)域的探索過(guò)程中，人們意識(shí)到研究智能的最好方式是模仿生物特性向人類自身學(xué)習(xí)。美國(guó)加州工學(xué)院物理學(xué)家Hopfield采用Hopfiled神經(jīng)網(wǎng)絡(luò)模型，對(duì)旅行商最優(yōu)路徑問(wèn)題進(jìn)行了研究。美國(guó) Michigan大學(xué)的 Holland［1］教授，以達(dá)爾文的生物進(jìn)化論和孟德?tīng)柕倪z傳變異理論為基礎(chǔ)，提出了遺傳算法，在思路上突破了原有最優(yōu)化方法的框架。這對(duì)NP問(wèn)題的研究起到了極大的促進(jìn)作用，很多學(xué)者紛紛采用這種模擬生物系統(tǒng)的方法解決NP問(wèn)題，但對(duì)于NP完全問(wèn)題仍然沒(méi)有有效的通用解決辦法。1994年，美國(guó)加利福尼亞大學(xué)的Adleman［2］教授第一次利用現(xiàn)代分子生物技術(shù)，提出了有向哈密爾頓路徑問(wèn)題的DNA（deox－yribonucleic）分子計(jì)算方法，并成功地在DNA溶液的試管中進(jìn)行了實(shí)驗(yàn)，這一實(shí)驗(yàn)在國(guó)際上引起了巨大的反響?？茖W(xué)家認(rèn)為將DNA分子堿基排列的性質(zhì)用于嘗試數(shù)學(xué)計(jì)算，是跨生命科學(xué)與計(jì)算科學(xué)兩大學(xué)科的一個(gè)嶄新的研究領(lǐng)域。從遺傳進(jìn)化、人工神經(jīng)網(wǎng)絡(luò)和DNA分子生物技術(shù)對(duì)智能的模擬過(guò)程來(lái)看，它們分別對(duì)應(yīng)生物群體、生物神經(jīng)元和生物分子3個(gè)截然不同的層次。由此可以看到，DNA計(jì)算的研究不僅是解決復(fù)雜類問(wèn)題的突破口，而且有可能更深刻地揭示智能形成的本質(zhì)［3－8］。

本文主要介紹DNA分子的結(jié)構(gòu)及計(jì)算模型，針對(duì)目前初始化過(guò)程存在的不足，提出數(shù)據(jù)初始化模型，給出了DNA分子初始化模型的算法描述；闡述DNA計(jì)算系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)，該系統(tǒng)成功地模擬生物DNA計(jì)算過(guò)程，避免了生物實(shí)驗(yàn)中的誤差。

1 DNA計(jì)算模型

1.1 DNA分子的結(jié)構(gòu)

DNA是一種高分子化合物，稱為脫氧核糖核酸，是遺傳信息存儲(chǔ)的媒介，它的分子結(jié)構(gòu)圖如圖1所示。

圖1 DNA分子結(jié)構(gòu)圖Fig.1 Structure of DNA molecules

組成DNA的基本單位是脫氧核苷酸，組成脫氧核苷酸的含氮堿基有4種，它們是腺嘌呤（A）、鳥(niǎo)嘌呤（G）、胞嘧啶（C）和胸腺嘧啶（T）［5］。多個(gè)脫氧核苷酸一個(gè)連一個(gè)，形成脫氧核苷酸鏈。DNA大分子是由2條頭尾方向相反的脫氧核苷酸長(zhǎng)鏈，以右手螺旋的方式盤繞著同一中心軸而形成的。2條鏈上的堿基通過(guò)氫鍵連接起來(lái)，堿基對(duì)的連接嚴(yán)格依據(jù)堿基互補(bǔ)配對(duì)原則，即腺嘌呤（A）通過(guò)2個(gè)氫鍵與胸腺嘧啶（T）配對(duì)，鳥(niǎo)嘌呤（G）通過(guò)3個(gè)氫鍵與胞嘧啶（C）配對(duì)。反過(guò)來(lái)也必定是T與A配對(duì)、C與G配對(duì)。遺傳信息是以A，T，C，G在核苷酸中的排列順序而體現(xiàn)的，其排列的多樣性構(gòu)成了豐富的遺傳信息。

1.2 DNA剪接操作

DNA分子重組包括2個(gè)步驟：第1步，2個(gè)DNA雙鏈分子在限制性核酸內(nèi)切酶識(shí)別的位置上被分別切割；第2步，在連接酶的作用下重組粘接，形成新的DNA分子。剪接操作是DNA分子重組的數(shù)學(xué)抽象［9］，它只表示分子上鏈的變換，通過(guò)互補(bǔ)關(guān)系可推出下鏈的分子序列。上鏈的默認(rèn)方向是5′→3′。形式化描述剪接操作需引入符號(hào)：字母表Σ以及Σ上的2個(gè)字符串x和y分別表示DNA分子a和DNA分子b，剪接規(guī)則r是Σ上形式為α1＃β1＄α2＃β2的字符串，其中，α1，β1，α2，β2∈Σ＊，＄，＃ ?Σ，＄ 和＃僅作為標(biāo)記符號(hào)。2個(gè)表示DNA分子的字符串x＝x1α1β1x2與y＝y(tǒng)1α2β2y2，按照 剪 接 規(guī) 則r＝α1＃β1＄α2＃β2，單輸出的剪接操作表示為（x1α1｜β1x2，y1α2｜β2y2）?x1α1β2y2。

定義1 剪接計(jì)算模型為四聯(lián)體Ψ＝ （Σ，T，A，R），其中：

（1）Σ是字母表；

（2）T?Σ是終結(jié)符號(hào)；

（3）A?Σ＊是開(kāi)始符號(hào)的集合；

（4）R?Σ＊＃Σ＊＄Σ＊＃Σ＊是規(guī)則集合。

定理1 任意一個(gè)遞歸可枚舉型語(yǔ)言，都可由相應(yīng)的剪接計(jì)算模型來(lái)產(chǎn)生。

證明 設(shè)G＝ （N，T，S，P）為0型文法。構(gòu)造剪接模型Ψ＝ （Σ，T，A，R），其中：Σ＝N∪T∪｛B，B′，S0，E，C，C1，C2｝∪ ｛Eα｜α∈N∪T∪｛S0｝｝。符號(hào)B，B′作為剪接字符串的最左端標(biāo)記；符號(hào)E，Eα作為剪接字符串的最右端的標(biāo)記；符號(hào)S0用于標(biāo)記文法G中被模擬推導(dǎo)的字符串開(kāi)始位置。

規(guī)則集R包含以下限制規(guī)則：

模擬規(guī)則：模擬文法G中產(chǎn)生式u→v∈P。

（1）r＝ （＃uE＄C＃vE；｛B｝，φ）。

移動(dòng)規(guī)則：將字符串中的u移到右端。

（2）r＝ （＃αE＄C＃Eα；｛B｝，φ）。

（3）r＝ （B＃＄B′α＃C；｛Eα｝，φ）。

（4）r＝ （＃Eα＄C＃E；｛B′｝，φ）。

（5）r＝ （B′?！鏐＃C；｛E｝，φ）。

終止規(guī)則：結(jié)束剪接操作。

（6）r＝ （BS0?！纾′；｛E｝，φ）。

（7）r＝ （＃E＄C″＃；φ，φ）。

剪接模型的模擬推導(dǎo)從字符串BS0SE開(kāi)始。如果當(dāng)前字符串的形式為Bx1S0x2uE，可使用模擬規(guī)則（1）來(lái)模擬文法G中的產(chǎn)生式規(guī)則u→v∈P。否則，通過(guò)轉(zhuǎn)換規(guī)則（2），（3），（4），（5）將u移動(dòng)到字符串的右端。轉(zhuǎn)換過(guò)程如下。

設(shè)u右邊的字符串為α，α∈N∪T∪｛S0｝，符號(hào)BwαE表示整個(gè)字符串，w∈ （N∪T∪ ｛S0｝）＊。

按照 規(guī) 則 （2），（Bw｜αE，C｜Eα）?（BwEα，CαE），Eα保存了被切割掉的內(nèi)容。這個(gè)操作生成了2個(gè)新的字符串，由于BwEα包含Eα，符合規(guī)則（3）的限制條件，所以字符串BwEα參與下一步的剪接操作。

按 照 規(guī) 則 （3）， （B｜wEα，B′α｜C）?（BC，B′αwEα），這里的α與規(guī)則（2）的α內(nèi)容相同。新字符串中的B′αwEα符合規(guī)則（4）的限制條件。

按照規(guī)則（4），（B′αw｜Eα，C｜E）?（B′αwE，CEα）。新字符串中B′αwE符合規(guī)則（5）限制條件。

按 照 規(guī) 則 （5），（B′｜αwE，B｜C）?（B′C，BαwE），通過(guò)轉(zhuǎn)換規(guī)則，字符串BwαE轉(zhuǎn)換成了BαwE，此時(shí)u移動(dòng)到了αw的右端，可以使用規(guī)則（1）進(jìn)行剪接操作。

按照規(guī)則（1），（Bw｜uE，C｜vE）?（BwvE，CuE）。

模擬規(guī)則和轉(zhuǎn)換規(guī)則可以根據(jù)需要，迭代使用。

按照結(jié)束規(guī)則進(jìn)行剪接操作，可得到終結(jié)符串。

按照 規(guī) 則 （6），（BS0｜wE，｜C′）?（BS0C′，wE），w?T＊。

按規(guī)則（7），（w｜E，C″｜）?（w，C″E），w?T＊。

通過(guò)上述的推導(dǎo)過(guò)程可知，凡是文法G能產(chǎn)生的語(yǔ)言，剪接模型都能產(chǎn)生。所有圖靈機(jī)可計(jì)算的問(wèn)題理論上都可以通過(guò)DNA計(jì)算來(lái)完成。

1.3 DNA計(jì)算過(guò)程

完整的DNA計(jì)算過(guò)程包括數(shù)據(jù)輸入、運(yùn)算以及結(jié)果的輸出［10－11］。具體步驟如下：

步驟1 通過(guò)對(duì)問(wèn)題的分析，設(shè)計(jì)合理的編碼模式，將問(wèn)題空間的對(duì)象映射成DNA分子鏈，在試管中構(gòu)建出所有可能解的初始數(shù)據(jù)，形成初始數(shù)據(jù)集合。

步驟2 利用DNA分子鏈的高度并行運(yùn)算的特點(diǎn)，用可控的分子生物操作完成正確答案的篩選，不同的計(jì)算模型，選擇的操作過(guò)程及技術(shù)不同。

步驟3 結(jié)果的輸出。這一步通過(guò)測(cè)定來(lái)判斷是否有解，如果有解則將DNA鏈進(jìn)行譯碼，就是所求問(wèn)題的解。

以上計(jì)算涉及到的分子生物技術(shù)有：聚合酶鏈?zhǔn)椒磻?yīng)、凝膠電泳、親和層析、加熱／退火、克隆、磁珠分離、標(biāo)記、合并、連接、切割、檢測(cè)等。

1.4 數(shù)據(jù)初始化模型

DNA計(jì)算處于起步階段，充滿機(jī)遇和挑戰(zhàn)。一些研究人員曾經(jīng)重復(fù)了Adleman的試驗(yàn)，他們按照Adleman的設(shè)計(jì)方法及步驟嚴(yán)格進(jìn)行了試驗(yàn)，但沒(méi)得到計(jì)算結(jié)果。這說(shuō)明除了實(shí)物試驗(yàn)方面存在的誤差外，還有可能是初始化數(shù)據(jù)不理想，在初始數(shù)據(jù)隨機(jī)組合時(shí)，沒(méi)有產(chǎn)生表示實(shí)際解的DNA鏈，那么無(wú)論怎樣篩選都不會(huì)找到問(wèn)題的解。為解決這一問(wèn)題，本文提出了數(shù)據(jù)初始化模型，該模型通過(guò)編碼控制方式控制數(shù)據(jù)的初始化。

將表示問(wèn)題解的DNA鏈的編碼模式設(shè)計(jì)為v1ek1v2ek2…vnekn的形式。其中，vi表示第i個(gè)位置的編碼，i∈1，2，…，n。eki表示第i個(gè)位置所攜帶的信息編碼。令表示問(wèn)題的所有信息短鏈的編碼集合為E，第i個(gè)位置所攜帶的信息編碼的集合為Ei，Ei?E。用符號(hào)card（Ei）表示集合Ei中所包含的元素個(gè)數(shù)。集合Ei中的元素按照1，2，…，card（Ei）的順序依次排列，每一個(gè)位置i只能攜帶集合Ei中的一個(gè)元素eki，k∈1，2，…，card（Ei）。模型中需要用到的分子操作方法有：

（1）集 合 復(fù) 制，Copy（｛T1，T2，…，Tn｝，T）。并行地將試管T中的DNA分子全部復(fù)制，產(chǎn)生n個(gè)與T中的內(nèi)容相同的試管Ti，即產(chǎn)生與集合T內(nèi)容相同的n個(gè)集合Ti。

（2）DNA鏈右邊追加短鏈，Rappend（T，x）。并行地將試管中所有DNA鏈的右端連接DNA短鏈x，Tx：＝｛wx｜w∈T｝。即將集合T中的所有元素添加一個(gè)后綴x。追加前試管T可以為空。

（3）合并，Union（T，｛T1，T2，…，Tn｝）。并行地將n個(gè)試管中的DNA溶液合并到試管T中，T：＝T1∪T2…∪Tn，即n個(gè)集合Ti合并產(chǎn)生了集合T。

（4）析取，Extract（T，x）。并行地析取出試管T中包含有子串x的DNA分子鏈。

數(shù)據(jù)初始化模型Initialization（T）的算法描述如下：

begin

fori＝1 tondo

begin

Copy（｛T1，T2，…，Tcard（Ei）｝，T）；

fork＝1，2，…，card（Ei）in parallel do

Rappend（Tk，vieki）；

Union（T，｛T1，T2，…，Tcard（Ei）｝）；

end

end

應(yīng)用上述數(shù)據(jù)初始化模型控制數(shù)據(jù)的初始化過(guò)程，保證了初始數(shù)據(jù)的完整性，不會(huì)造成解的丟失，也不會(huì)產(chǎn)生與實(shí)際解的模式不相同的DNA鏈。該模型不僅為后續(xù)的計(jì)算過(guò)程奠定了良好的基礎(chǔ)，而且減少了計(jì)算過(guò)程中參與篩選的DNA鏈的數(shù)量，從而減小了計(jì)算誤差。

2 DNA計(jì)算系統(tǒng)

2.1 系統(tǒng)概述

因受現(xiàn)有生物技術(shù)限制，活性DNA反應(yīng)時(shí)間較長(zhǎng)，材料成本高，在實(shí)驗(yàn)室較難完成實(shí)際分子計(jì)算過(guò)程。針對(duì)這一現(xiàn)狀，開(kāi)發(fā)了仿生DNA計(jì)算系統(tǒng)，系統(tǒng)開(kāi)發(fā)工具為Vc＋＋6.0。DNA計(jì)算系統(tǒng)應(yīng)用DNA分子的結(jié)構(gòu)特性和常用分子生物操作過(guò)程，以DNA編碼串作為信息的載體，以生物操作為算子，采用上述數(shù)據(jù)初始化模型產(chǎn)生初始數(shù)據(jù)，模擬DNA分子計(jì)算過(guò)程。DNA計(jì)算系統(tǒng)包括5大模塊：

（1）DNA基礎(chǔ)知識(shí)。介紹DNA分子雙螺旋結(jié)構(gòu)、特性。

（2）常用DNA分子操作技術(shù)。

（3）DNA計(jì)算模型。包括DNA分子的演算過(guò)程、DNA自動(dòng)機(jī)、DNA分布式計(jì)算以及算法描述。

（4）DNA計(jì)算系統(tǒng)仿真。該模塊模擬DNA生物操作過(guò)程解決計(jì)算問(wèn)題，包括問(wèn)題的輸入、計(jì)算過(guò)程模擬、結(jié)果輸出。

（5）開(kāi)放性問(wèn)題探討。應(yīng)用網(wǎng)絡(luò)資源廣泛進(jìn)行交流和探討。

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

本文以查找6個(gè)城市間的哈密爾頓路徑問(wèn)題為例，介紹DNA計(jì)算過(guò)程。數(shù)字0，1，2，3，4，5分別代表6個(gè)城市，假設(shè)城市1為起點(diǎn)，城市4為終點(diǎn)，如圖2所示。

DNA計(jì)算系統(tǒng)仿真過(guò)程如下。

步驟1 問(wèn)題輸入。分別輸入節(jié)點(diǎn)數(shù)、節(jié)點(diǎn)名稱、邊、起點(diǎn)和終點(diǎn)。節(jié)點(diǎn)編碼分別由4種堿基A，T，C，G組成的DNA鏈表示，用戶可以手工輸入各個(gè)節(jié)點(diǎn)編碼，也可以點(diǎn)擊按鈕，由系統(tǒng)自動(dòng)生成編碼。本例的節(jié)點(diǎn)編碼由8位DNA堿基序列構(gòu)成。點(diǎn)擊“城市名稱”按鈕，可自動(dòng)生成分別表示6個(gè)城市名稱的DNA編碼。系統(tǒng)模擬生物操作過(guò)程執(zhí)行數(shù)據(jù)初始化算法組合路經(jīng)，生成初始數(shù)據(jù)集合。

步驟2 DNA計(jì)算過(guò)程。點(diǎn)擊“找哈密爾頓路”按鈕，模擬生物操作過(guò)程，依次比較節(jié)點(diǎn)和邊的連通序列，按約束規(guī)則求解問(wèn)題，該過(guò)程是DNA計(jì)算系統(tǒng)仿真模塊中最主要環(huán)節(jié)。仿真模擬界面如圖3所示。

圖2 6個(gè)城市的哈密爾頓路徑問(wèn)題圖Fig.2 Hamilton path problem in 6cities

圖3 仿真模擬界面Fig.3 Simulation interface

步驟3 輸出結(jié)果。執(zhí)行步驟2后，如果找到路徑，彈出的對(duì)話框給出從起始城市到終點(diǎn)城市的哈密爾頓路徑；若沒(méi)找到路徑，對(duì)話框提示該問(wèn)題無(wú)解。本例找到的路徑編碼序列為TCAAAATT—TGCAATCA—TTAGACTA—GAGCTCAC—CTCCGTCG—TGTTATAG，解碼譯成相應(yīng)的城市名稱，1—3—2—0—5—4就是所求結(jié)果（見(jiàn)圖4）。

3 小結(jié)

作為新生事物的DNA計(jì)算方法，引起了科學(xué)家們的廣泛重視，人們對(duì)DNA計(jì)算的前景充滿希望。DNA計(jì)算拓寬了人們對(duì)自然計(jì)算現(xiàn)象的理解，特別是對(duì)計(jì)算本質(zhì)的理解。通過(guò)模擬生物DNA分子操作技術(shù)抽象出的DNA計(jì)算模型，使人們認(rèn)識(shí)到DNA計(jì)算也是一種遞歸計(jì)算。就計(jì)算本質(zhì)而言，它同人類有史以來(lái)的一切計(jì)算都是等價(jià)的、一致的。所有圖靈機(jī)可計(jì)算的問(wèn)題理論上都可以通過(guò)DNA計(jì)算來(lái)完成。但由于是起步階段，DNA計(jì)算還存在著許多亟待解決的問(wèn)題。仿生DNA計(jì)算系統(tǒng)成功地模擬生物DNA計(jì)算過(guò)程，避免了生物實(shí)驗(yàn)誤差，節(jié)約材料成本，減少活性分子在試管溶液中的反應(yīng)時(shí)間，為DNA計(jì)算從原理性的實(shí)驗(yàn)向?qū)嶋H應(yīng)用奠定基礎(chǔ)。相信隨著科研人員的不懈努力和探索，DNA計(jì)算一定會(huì)真正應(yīng)用于工程實(shí)踐中。

圖4 DNA計(jì)算結(jié)果圖Fig.4 DNA computing result

［1］ HOLLAND J H.Adaptation in Natural and Artificial System：An Introduction Analysis with Application to Biology，Control and Artificial Intelligence［M］.Michigan：the University of Michigan Press，1975.

［2］ ADLEMAN L M.Molecular computation of solutions to combinatorial problems［J］.Science，1994，266：1021－1024.

［3］ LIU Q H.DNA computing on surfaces［J］.Nature，2000，403：175－179.

［4］ LIM H W，LEE S H，YANG K A，et al.In vitro molecular pattern classification via DNA－based weightedsum operation［J］.Biosystems，2010，100：1－7.

［5］ DAREHMIRAKI M.A new solution for maximal clique problem based sticker model［J］.Biosystems，2009，95：145－149.

［6］ SMITH D H，ABOLUION N，MONTEMANNI R，et al.Linear and nonlinear constructions of DNA codes with Hamming distanced and constant GC－content［J］.Discrete Mathematics，2011，311：1207－1219.

［7］ 周康，同小軍，劉文斌，等.最短路問(wèn)題的閉環(huán)DNA算法［J］.系統(tǒng)工程與電子技術(shù)，2008，30（3）：556－560.

［8］ MARDINAN R，SEKIYAMA K，F(xiàn)UKUDA T.Approaching mathematical model of the immune network based DNA strand displacement system［J］.Biosystems，2013，114（3）：245－252.

［9］ KARI L.DNA computing：arrival of biological mathematics［J］.The Mathematical Intelligence，1997，19（2）：9－22.

［10］ 周旭，李肯立，樂(lè)光學(xué)，等.一種最大匹配問(wèn)題DNA計(jì)算算法［J］.計(jì)算機(jī)研究與發(fā)展，2011，48（11）：2147－2154.

［11］ 薛潔，劉希玉.基于DNA計(jì)算的層次圖聚類算法［J］.計(jì)算機(jī)工程，2012，38（12）：188－190.