張喆

摘要摘要：用通俗易懂的語言解釋了最短路概念以及解決多頂點(diǎn)最短路問題面臨的困境，介紹了DNA計(jì)算的研究背景，闡明了DNA計(jì)算解決最短路的優(yōu)勢以及算法步驟，并對DNA計(jì)算的未來發(fā)展作出展望。

關(guān)鍵詞關(guān)鍵詞：最短路；DNA計(jì)算；單鏈；k-臂分子

DOIDOI：10.11907/rjdk.1431049

中圖分類號：TP301

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2015）004003902

1最短路概念及其傳統(tǒng)解法

求解最短路的過程即尋求一個(gè)圖中任意兩節(jié)點(diǎn)之間最短距離的過程。以某人從第1個(gè)城市到第5個(gè)城市為例，中間有2、3、4三個(gè)城市，需要尋找到第5個(gè)城市的最短路徑。最短路的求法一般有兩種：確定性算法和啟發(fā)式算法。確定性算法的含義是，將這些城市看成不同的點(diǎn)，并對點(diǎn)與點(diǎn)之間的距離進(jìn)行賦值。若想找到點(diǎn)V1到V5的最短距離，可以開始從V1開始搜索。比如d1=d{V1，V2}=5，d2=d{V1，V3}=2。V1到V4、V5不存在交通方式（當(dāng)然這在如今社會幾乎是不可能的），認(rèn)為距離為正無窮大，自然優(yōu)選d2。此時(shí)臨時(shí)可行解的集合里囊括了V1、V3個(gè)點(diǎn)。再進(jìn)行搜索，此時(shí)的搜索要對V1、V3連接的所有邊進(jìn)行搜索。比如d1=d{V1，V2}=5，d3={V2，V3}=1，d4={V2，V4}=5，d5={V2，V5}=5。此時(shí)，優(yōu)先選擇d3，即將V2囊入集合中。此時(shí)最短路的一部分已經(jīng)浮出水面，即d2+d3。重復(fù)上述過程，直到找出V1到V5的最短距離?？梢钥闯?，當(dāng)點(diǎn)足夠多時(shí)，這種算法的步驟將呈現(xiàn)指數(shù)爆炸的傾向，實(shí)際操作的可能性不大。若采用啟發(fā)式算法，通過迭代可以大大減少計(jì)算量，但往往只能得到局部最優(yōu)解，如圖1所示。

例如目標(biāo)要找到最低點(diǎn)A4，當(dāng)經(jīng)過一系列迭代后，尋找到了A2，但從A2再進(jìn)行搜索時(shí)，會發(fā)現(xiàn)它周圍的點(diǎn)都高于它本身，于是搜索會在此時(shí)停止，而真正的最優(yōu)解A5卻被排除在外，只得到了局部最優(yōu)解A2。雖然模擬退火法會讓這種現(xiàn)象大大減少，但啟發(fā)式算法陷入局部最優(yōu)解的概率仍然存在。

基于以上原因，尋求一種新的方法解決最短路徑問題則顯得格外重要。近年來，國內(nèi)外學(xué)者通過研究和實(shí)驗(yàn)發(fā)現(xiàn)運(yùn)用DNA自組裝方法解決此類問題非常有效。

2DNA計(jì)算算法步驟

1994年，Adleman提出了用DNA分子解決7節(jié)點(diǎn)的Hamilton路徑問題，這是有關(guān)DNA計(jì)算的開山之作。之后Lipton在Adleman的思想啟發(fā)下，通過構(gòu)造一個(gè)接觸網(wǎng)絡(luò)圖G，將可滿足性問題（SAT）的解空間映射成通過接觸網(wǎng)絡(luò)G的始點(diǎn)到終點(diǎn)的所有Hamilton路徑，然后對有向圖中的頂點(diǎn)和邊進(jìn)行編碼，用DNA計(jì)算解決了3-變量的可滿足性問題；1997年，Ouyang等[1]提出了用DNA計(jì)算求解最大環(huán)問題的方法，為DNA計(jì)算解決NP問題提供了又一佐證；2000年，F(xiàn)aulhammer等[2]提出了用RNA分子取代DNA分子進(jìn)行計(jì)算，求解騎士問題；同年，liu等人[3]提出了在固體表面進(jìn)行DNA計(jì)算的方法，改變了過去在試管溶液中進(jìn)行DNA計(jì)算的生物操作方法，進(jìn)一步提高了DNA計(jì)算的可靠性和效率。隨著該技術(shù)的進(jìn)一步發(fā)展，2009年，國內(nèi)的許進(jìn)等人[4]設(shè)計(jì)了閉環(huán)求解最大團(tuán)問題的算法；2010年，周康等人設(shè)計(jì)了基于粘貼模型的最大團(tuán)問題算法，Brun采用自組裝DNA計(jì)算給出了路徑尋找問題以及可滿足性問題的自組裝計(jì)算模型的解決方案；2011年，楊靜等人[5]將Aunp自組裝聚合色變與DNA計(jì)算相結(jié)合，構(gòu)建了系列基本邏輯計(jì)算模型；2012年，李肯力等人[6]設(shè)計(jì)出了結(jié)合DAE塊的DNA自組裝模型求解最大團(tuán)問題的算法，并在2013年進(jìn)一步改進(jìn)，等等。

DNA計(jì)算具有高度并行性，即給予一定數(shù)量的試管，相應(yīng)實(shí)驗(yàn)可以在這些試管里同時(shí)進(jìn)行，從而大大減少了計(jì)算時(shí)間。不僅如此，DNA本身的堿基配對原則使最優(yōu)解的選擇變得很簡單，即不需要去“計(jì)算”最優(yōu)解，只需要看到底哪條子鏈和對應(yīng)的子鏈配對成功即可，這種效率是其它計(jì)算遠(yuǎn)不能比擬的。因此，運(yùn)用k-臂分子解決最短路徑問題具有極大的優(yōu)勢。具體操作過程如下：

（1）將所要研究的問題簡化，即將具體事物轉(zhuǎn)化為點(diǎn)，事物與事物之間存在聯(lián)系則表示點(diǎn)與點(diǎn)之間有邊相連，否則無邊。根據(jù)事物與事物之間的“距離”關(guān)系，對邊進(jìn)行賦值。

（2）設(shè)計(jì)DNA鏈。設(shè)計(jì)的DNA滿足以下幾個(gè)原則：一個(gè)點(diǎn)有幾個(gè)邊相連，則設(shè)計(jì)成幾臂分子；賦值越大，則設(shè)計(jì)的DNA鏈越長（可以對權(quán)值進(jìn)行單位化，便于計(jì)算）；所有的DNA鏈都設(shè)計(jì)為單鏈形式，方便配對；根據(jù)堿基配對原則，同時(shí)設(shè)計(jì)出各個(gè)邊對應(yīng)的子鏈；對頂點(diǎn)和終點(diǎn)設(shè)計(jì)探針，以便最后用探針處理結(jié)果。設(shè)計(jì)的4-臂分子如圖2所示。

（3）復(fù)制相同的試管T，在試管中投放根據(jù)圖2設(shè)計(jì)的DNA-k臂分子鏈，通過雜交技術(shù)，讓單鏈與其對應(yīng)的單鏈配對，再通過退火的方式，讓試管冷卻，即將單鏈與單

鏈分離。因?yàn)橹耙呀?jīng)在頂點(diǎn)和終點(diǎn)插入了探針，所以運(yùn)用探針照明技術(shù)即可找出同時(shí)含有V1、V5的子鏈。最后利用凝膠電泳篩選出長度最短的子鏈，再利用探針照明分析出頂點(diǎn)構(gòu)成即可（此時(shí)的探針和之前的探針有所不同，可以對各個(gè)點(diǎn)賦予不同顏色）。

3前景展望

在解決最短路問題中，DNA的合成與編碼，以及如何運(yùn)用盡量簡單的方式形成解空間是待解決的重要問題，同時(shí)如何剔除“偽解”和“錯解”，篩選出最優(yōu)解也非常重要。對于模型的頂點(diǎn)、邊以及頂點(diǎn)和邊的映射關(guān)系等進(jìn)行DNA編碼與合成，并在試管中形成解空間，進(jìn)行合并、分離、設(shè)置、清除等生物操作，最后對篩選出的解進(jìn)行檢測，并轉(zhuǎn)換成問題的實(shí)用解。本文用k—臂分子建立了解決最短路問題的模型，具有一定可行性，但是時(shí)間操作仍需不斷改進(jìn)。DNA計(jì)算的應(yīng)用范圍極其廣泛，只要解決了以上問題，DNA計(jì)算在未來很多領(lǐng)域都將占據(jù)一席之地。

參考文獻(xiàn)參考文獻(xiàn)：

[1]張成，楊靜，許進(jìn)，等.縮短法計(jì)算模型求解最大獨(dú)立集問題[J].科學(xué)通報(bào)，2009，54（24）：3913.

[2]張社民，方剛.連通度問題的三維DNA結(jié)構(gòu)進(jìn)化算法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（7）：41.

[3]高琳，許進(jìn)，張軍英.DNA計(jì)算的研究進(jìn)展與展望[J].電子學(xué)報(bào)，2001，29（7）：973977.

[4]姜泊，張亞歷，周殿元.分子生物學(xué)常用實(shí)驗(yàn)方法[M].北京：人民軍醫(yī)出版社，2000.

[5]周康，劉朔.基于粘貼模型的最大團(tuán)問題算法[J].華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，38（9）：8992.

[6]黃布毅.DNA計(jì)算中若干理論問題的研究[D].武漢：華中科技大學(xué)，2005.

責(zé)任編輯（責(zé)任編輯：黃?。?