運用DNA計算解決最短路徑問題

張喆

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

關鍵詞關鍵詞：最短路；DNA計算；單鏈；k-臂分子

DOIDOI：10.11907/rjdk.1431049

中圖分類號：TP301

文獻標識碼：A文章編號文章編號：16727800（2015）004003902

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

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

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

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

2DNA計算算法步驟

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

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

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

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

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

鏈分離。因為之前已經(jīng)在頂點和終點插入了探針，所以運用探針照明技術即可找出同時含有V1、V5的子鏈。最后利用凝膠電泳篩選出長度最短的子鏈，再利用探針照明分析出頂點構成即可（此時的探針和之前的探針有所不同，可以對各個點賦予不同顏色）。

3前景展望

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

參考文獻參考文獻：

[1]張成，楊靜，許進，等.縮短法計算模型求解最大獨立集問題[J].科學通報，2009，54（24）：3913.

[2]張社民，方剛.連通度問題的三維DNA結構進化算法[J].計算機工程與應用，2007，43（7）：41.

[3]高琳，許進，張軍英.DNA計算的研究進展與展望[J].電子學報，2001，29（7）：973977.

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

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

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

責任編輯（責任編輯：黃?。?