一種新的求解最小生成樹問題的DNA算法

摘要:基于生化反應的生物智能計算是現(xiàn)階段計算領域研究的熱點，DNA計算是通過DNA分子之間的生化反應來進行計算的一種計算模式，憑借運算巨大的并行性和海量存儲的優(yōu)勢，DNA計算在解決復雜運算問題方面的計算能力顯而易見。設計了一種利用DNA計算來求解圖的最小生成樹的計算模型，采用一種特殊的編碼方式來對頂點，邊和權值進行編碼，并且描述了MSTP解的計算過程。

關鍵詞:DNA計算;最小生成樹;K-臂分子;粘貼模型

中圖分類號:TP301文獻標識碼:A文章編號:1009-3044(2010)01-188-03

A New DNA Algorithm Solving Minimum Spanning Tree Problem

WANG Qing-Hu， ZHENG Hong

(Computer Science and Engineering College， Changchun Univ. of Tech.， Changchun 130012， China)

Abstract: Bio-intelligent computing based on biochemical reactions is a hotspot in recent research of computing field. DNA computing is a computing model by using DNA molecule and biochemical reaction. Because of the advantages of DNA computing， such as parallelism and mass storage， it can be used to solve complex problem. In this paper， a method to solve minimum spanning tree problem based on DNA computing is proposed. The encoding method and solving process are described in the paper.

Key words: DNA computing; MST; k-arm molecular; sticker model

計算智能是當今國際上迅速發(fā)展的前沿交叉學科，它是模擬人的智能行為來進行計算，對于解決不確定、非線性、復雜的各類問題，具有非常廣闊的應用前景。尤其自從Adleman提出DNA計算模型以來[1]，更加拓展了計算智能的研究領域。DNA計算是一種以DNA鏈與相關的某些生物酶等作為最基本材料的、基于某些生化反應原理的一種新型的分子生物計算方法。利用DNA計算已經解決很多的NP完全問題，但在圖論中對圖的最小生成樹問題(MSTP)的研究不是很多，本文設計了一種DNA計算模型來解決這個問題，尤其在編碼的策略上給出了一些創(chuàng)新的思路。

1 DNA計算模型

本文提出的MSTP計算模型采用K-臂DNA計算模型，問題的求解過程基于粘貼計算。

1.1K-臂DNA計算模型

1999年，Jonoska等人提出來的一種DNA計算模型 — K-臂模型[2]。K-臂模型中所使用的DNA分子為不完全的雙鏈分子，圖1描述了1-臂、2-臂、3-臂、4-臂等DNA分子。目前的研究表明，自然界中已經存在類似于K-臂的DNA分子，如Holliday中間體，并且3-臂和4-臂DNA分子比較穩(wěn)定[3]。

從圖1中 K-臂DNA分子的結構可以看出，通過連接酶，我們可以利用K-臂(K≤4)DNA分子構造出任意頂點的最大度為4的圖。正是利用這一思想，我們用K-臂分子來表示圖或樹中度為n(n≤4)的頂點的結構，來實現(xiàn)MSTP解的節(jié)點結構。

1.2 粘貼運算的計算模型

在求解最小生成樹問題計算模型的編碼方案中，使用的DNA分子是由單鏈和雙鏈進行混合編碼的不完全分子，類似于圖2的多米諾骨牌，結構中x部分為雙鏈。

實驗中的生物操作類似于粘貼運算，粘貼運算實質就是在連接酶的作用下進行不完全分子的連接，這里我們給出粘貼運算的連接結構圖，如圖3所示。在粘貼計算中，基本的生物操作是合并、分離、設置與清除[4]。

2 問題描述

最小生成樹問題是圖論中相當重要的、基本的問題，它常用于網絡規(guī)劃中，尤其在求解實際問題或其它復雜性問題中具有相當廣泛的應用，比如其在網絡設計中的應用。當前求解圖的最小生成樹問題普遍使用貪婪算法，其中Kruskal算法較為常用。圖的最小生成樹問題可以描述如下:

給定連通圖G =(V; E)，其中V={v1，v2，…，vm}為頂點集合，E={e1，e2，…en}為邊的集合，則|V|=m且|E|=n，W={w1，w2，…wn}是圖的權值的集合，則G的生成樹為T=(V;E(T))， 其中E(T)?哿E，W(T)是T的權，最小生成樹問題就是在圖G的支撐樹中尋找那些權值最小的生成樹。

3 MSTP編碼的分子結構

本節(jié)將介紹MSTP中頂點、支架分子、權值和邊的編碼方式，以圖4的連通圖為例。

3.1 頂點及頂點支架分子編碼

對頂點的編碼采用單鏈等長的編碼方式，對于頂點Vi，其編碼為兩部分Vi'和Vi''， Vi'為前置序列，Vi''為后置序列，這兩部分是等長的，我們這里采用的單鏈的長度為20 mer，另外需要指明的問題是在對頂點編碼的時候一定要保證編碼的唯一性約束。模擬實驗中對圖4所示的圖G我們將頂點編碼如表1。

在給定了頂點的DNA編碼后，我們就可以確定支架分子的結構，若頂點的度為d(Vi)=k，那么該頂點的支架分子結構就選用圖1中類似結構的k-臂分子，且k-臂分子的延長端為對應上述頂點的前置序列的補鏈。

3.2 權值編碼

權值編碼是整個編碼方案的重點，編碼后的權值并不是直接參與生化反應的獨立實體，而是作為邊編碼的一部分。這里將采用雙鏈編碼的方式來表示權值。MSTP中需要能夠通過檢測生成的DNA雙鏈分子來獲得MSTP中生成樹的代價，所以權值的編碼要能夠合理的攜帶表述權值大小的信息。在此我們將考慮利用權值編碼中堿基C，G的含量來表示權值的大小關系，我們將采用雙鏈等長的編碼方式，在通過分析問題域的給定權值集合后，為使所有的權值的編碼長度分布在一個我們預想的實數(shù)范圍內，設定一個編碼長度因子θ，若初始權值集合中每一個權值Wi×θ取整(記為[Wi×θ])后，形成的新的集合的規(guī)模沒有縮小，則選取新集合中值最大的元素Max作為等長編碼的長度，否則調整長度因子θ，繼續(xù)上面的操作直到權值集合的規(guī)模不再變化，則每一個權值的C，G含量為[Wi*θ]/Max。對于圖4給出的圖G，其權值的集合為{3，4，5，6，7，8，10}，我們選擇長度因子θ=1，則編碼長度為10bp，而每一個權值編碼中CG堿基對的數(shù)目就為其權值的數(shù)目。這里我們不單獨給出權值的編碼，稍后的邊編碼中一同給出。

3.3 邊編碼的分子結構

邊編碼我們將采用不完全分子結構，即在雙鏈的兩側帶有粘性末端，基于上述的頂點編碼和權值編碼，下面給出邊編碼的分子結構。表示邊編碼的不完全分子由三部分組成:a) 出邊頂點的后置序列的互補鏈，是一段單鏈。b) 代表該邊權值的權值編碼，是一段雙鏈分子。c) 入邊頂點的前置序列的互補鏈，是一段單鏈。由于給出的圖是無向圖，因此如V2—>V1和V1—> V2表示了兩條不同的邊。且對于每條邊又要分為兩種情形，分子兩端的單鏈要區(qū)分為3'端延伸和5’端延伸兩種情況。表2給出了邊的分子結構(表中只給出了3'端延伸的情況，5'端延伸類似)。

4 MSTP算法描述

步驟1:通過對問題域的抽象后，對圖的頂點，權值和邊進行編碼，按照頂點編碼構造頂點的支架分子，并按照權值的大小構造邊序列{e3，e4，e7，e5，e2，e1，e6}。

步驟2:混合初始溶液。在初始溶液T中混合多份的頂點支架分子，頂點的單鏈和T4連接酶。并在初始溶液中加入表示邊e3和e4不完全分子，降低溫度，則具有互補端的頂點支架分子和頂點單鏈，以及不完全分子邊會通過T4連接酶的作用，按照互補規(guī)則進行雜交和連接，由于圖G是簡單圖，則雜交和連接后不會形成含圈的圖結構。這里我們將給出探測圈是否存在的方法。對每個頂點進行熒光標記，在加入一個表示邊的不完全分子后，若在形成的新的圖結構中，熒光標記的頂點沒有增加，則有圈存在，否則不含圈。

步驟3:將得到的溶液分為兩份T1和T2。

步驟4:在溶液T1中加入表示邊e3的不完全分子，通過連接酶形成新的圖結構。

步驟5:檢測T1溶液中是否包含圈，若不包含圈，則令T=T1+T2;否則令T=T2。向溶液T中加入表示邊e7，e5，e2，e1，e6的不完全分子，重復執(zhí)行步驟3，4，5。

步驟6:檢測解空間。在所有的解中選擇滿足CG含量最小的分子即為MSTP的解。

5 結論

本文設計了一種基于DNA計算求解MSTP問題的編碼方案，并利用該模型求解了圖的最小支撐樹。DNA計算是一個新的研究方向，不僅會對計算機及其它學科的研究產生巨大的影響，而且也會拓展人們對于計算概念的理解。但是，也應該看到，DNA計算機的研究還面臨著許多具有挑戰(zhàn)性的問題，本文所給出的算法模型也可以進行進一步的拓展，來減少生物實驗中解分離的復雜度。

參考文獻:

[1] Adleman L. Molecular computation of solution to combinatorial problems[J].Science，1994，66(11):1021-1024.

[2] Jonoska N， Karl S A， Saito M. Three dimensional DNA structures in computing[J].Biosystems， 1999(52):143-153.

[3] 許進，譚鋼軍，范月科，等.DNA計算機原理、進展及難點(IV)——論DNA計算模型[J].計算機學報，2007，36(7):881-893.

[4] 支凌迎，殷志祥，黃曉慧，等.DNA計算研究概述與分析[J].系統(tǒng)工程與電子技術，2009，31(6):1462-1466.