基于ＤＮＡ算法的獨立數問題的求解
2006-12-31 00:00:00孫川朱翔鷗劉文斌
計算機應用研究 2006年10期
摘 要：在構造了一種鏈接鏈及一種新型的“類發夾式”探針的基礎上，給出了圖的獨立數問題的一種DNA算法。利用頂點的簡單編碼及鏈接鏈，該算法直接生成數據池，使用常規的生物操作即可完成解空間的產生及最終解的分離。
關鍵詞：DNA算法; 獨立數; 探針; 編碼
中圖法分類號：TP18 文獻標識碼：A 文章編號：1001-3695(2006)10-0020-02
Method of Solving Independent Number Based on DNA Algorithm
SUN Chuan1， ZHU Xiangou2， LIU Wenbin2
(1.College of Mechanic Electronic Engineering， Huangshi Institute of Technology， Huangshi Hubei 435003， China; 2.College of Computer Science Engineering， Wenzhou University， Wenzhou Zhejiang 325027， China)
Abstract:A newstyle link chain and a newstyle prehairpin type probe have been constructed， and a DNA algorithm for the graph independent number problem has been presented. With the proper coding and link chain， the data pool of the problem can be produced directly by this algorithm. The produce of solution space and separation of finally solution can be successful in regular biology operation.
Key words:DNA Algorithm; Independent Number; Probe; Encoding
1 引言
(1)DNA計算。1994年Adleman首次提出用DNA計算解決實際問題，設計出一種全新的計算模式——模擬生物分子DNA結構，并借助于分子生物技術進行計算，使得NPhard問題的求解可能得到解決[1]。圖論中許多NPhard問題，如最大團、最小頂點覆蓋、最大匹配、頂點著色等問題，均有研究者給出了相應的DNA算法[2~12]。圖的獨立數問題，即指求取無向圖G的最大獨立集，這個問題便是著名的NPhard問題，目前它尚無完全有效的算法。
（2）問題數學描述。給定圖G=(V，E)，其中V為G的頂點集，E為G的邊集。頂點集V′V稱為G的一個獨立集，如果V′中任意兩點均不相鄰接，記圖G中的全體獨立集構成的集合為Ψ(V′)。圖G的最大獨立集所含元素個數α(G)稱為G的獨立數。圖G的最大獨立集可能不唯一，但α(G)是唯一的。對任意的圖G，求其獨立數α(G)是一個NPhard問題[13]。
2 DNA算法設計
2．1 頂點編碼
頂點間的相鄰關系由鏈接鏈進行標志，因而頂點編碼的目的只是為了標志不同頂點，所以只需使用簡單的DNA片段即可。DNA片段長度L(堿基個數)由圖G頂點個數確定，要求具有一定的碼距，以能確保正確標志不同頂點為準，如M=GATCTGCTAG可作為某一頂點的標志編碼。
2．2 算法原理
利用生物技術將彼此不相鄰的頂點編碼(DNA片段)無重復地鏈接起來形成DNA長鏈Ml，則每一條這樣的DNA長鏈Ml所對應的頂點集均為圖G的一個獨立集V′，記所有這樣構成的DNA長鏈Ml的全體為Ψ(Ml)，則有滿映射
σ:ψ(Ml)|→ψ(V′);Ml→V′;Ml∈ψ(Ml)
可見Ψ(Ml)即為解空間。在解空間Ψ(Ml)中輸出所有鏈長最大者，則由映射σ即可獲得G的最大獨立集，由其鏈長即可得最大獨立數α(G)。顯然，Ml∈ψ(Ml)，|Ml|≤|V|×L(M)，Ml→V′，交換其中任兩頂點編碼所得新鏈M′l∈ψ(Ml)，因而σ(Ml)=σ(M′l)。
2．3 DNA算法設計
算法步驟如下：
（1）產生頂點編碼；
（2）建立數據池，獲得DNA計算的輸入數據；
（3）建立解空間；
（4）搜索滿足條件的數據集并輸出運算結果；
（5）對運算結果進行DNA序列測定，獲得結果α(G)；
（6）End。
3 算法DNA實現
為使DNA算法生物實現成為可能，必須進行生物制備。本算法所需生物制備主要是鏈接鏈與探針。
3．1 鏈接鏈
為了產生數據池，必須進行不相鄰頂點DNA片段的鏈接，以生成反映滿足解條件的DNA長鏈。不相鄰頂點DNA片段的鏈接利用鏈接鏈來完成，鏈接鏈記為Lv1v2。設兩個不相鄰頂點v1與v2的編碼分別為M1與M2，則其對應的鏈接鏈為由M1與M2的補碼生成的長鏈，即Lv1v2=M1M2。
由鏈接鏈的定義可知，鏈接鏈可同時標志頂點的不相鄰關系，這一性質極大地簡化了頂點的編碼。在建立數據池時，若v1與v2，v2與v3不相鄰，則其對應編碼(DNA片段)M1與M2，M2與M3分別由鏈接鏈Lv1v2與Lv2v3鏈接，生成DNA長鏈，如圖1所示。由此可見，利用鏈接鏈即可建立數據池。
3．2 探針
探針就化學或生物學意義而言，是指一種只與某種特異靶分子明顯相互作用，并在這種相互作用后有方法檢測到的分子，如蛋白質探針(如抗體)與核酸探針[14]。由于只有核酸探針才具有退火特性，因而用于DNA計算的探針只能是核酸探針。本算法需要制備兩種用于刪除操作的核酸探針，即單點頂點探針(記為Pv)與雙點頂點探針(記為Pv1v2，頂點v1與v2相鄰)。頂點探針Pv與Pv1v2均由三部分構成，即主體、前綴與后綴?？紤]到分子間的引力，主體X是長度為L(X)＞(|V|+1)L(M)的DNA單鏈，且N與所有頂點的編碼M具有足夠大的碼距。Pv的前綴與后綴均為對應頂點的編碼M，Pv1v2的前綴與后綴分別為對應頂點v1與v2的編碼M1與M2。顯然，Pv是Pv1v2當v1=v2時的特殊情況，可統一記為Pv1v2。
對數據池中任一長度不大于|V|×L(M)的DNA長鏈，若該鏈含有相鄰頂點v1與vk+1對應的DNA片段M1與Mk+1，或該鏈含有同一頂點v的DNA片段M次數不小于兩次(v1=vk+1)，則探針Pv1v2即可與其鏈接鏈作用，形成類發夾結構形式，從而可完成將其刪除的操作，如圖2所示。
3．3 算法生物實現
（1）產生頂點編碼。生成全部頂點的所有編碼(DNA片段)M，放入初始試管T0中，并將其復制若干份備用。
（2）生成數據池。在試管T0中加入連接酶及圖G對應的所有鏈接鏈Lv1v2進行鏈接反應，生成DNA長鏈。
（3）建立解空間。
①刪除不必要的長鏈數據。由算法原理知，數據池中長度大于|V|×L(M)的DNA長鏈必不屬于解空間Ψ(Ml)，應當將其刪除。在試管T0中加入緩沖溶液，對DNA鏈進行凝膠電泳即可對長度大于|V|×L(M)的DNA長鏈進行分離，從而可完成刪除操作。將所得的所有長度不大于|V|×L(M)的DNA長鏈進行PCR擴增，獲得試管T1。T1僅含有長度不大于|V|×L(M)的DNA長鏈。
②刪除錯誤數據。當圖G中出現v1與v2，v2與v3，…，vk與v1(k<|V|)不相鄰時，由數據池生成方式可知，試管T1中必含有v1，v2，v3，…，vk，v1，…對應的DNA長鏈S1=…M1M2M3…MkM1…。同樣，當圖G中出現v1與v2，v2與v3，…，vk與vk+1不相鄰，但vk+1與v1相鄰時，T1中含有對應的DNA長鏈S2=…M1M2M3…MkMk+1…(如圖3所示，圖G所對應的T1中含有長鏈M1M3M1，M1M3M1M4，M1M3M5，M3M1M4M2等)。鏈S1與S2顯然均不屬于解空間Ψ(Ml)，應當將其刪除。由Pv的構造可知，在T1中利用全部單點頂點探針Pv與雙點頂點探針Pv1v2，并加入緩沖溶液進行雜交反應。非解鏈S1與S2分別與Pv和Pv1v2雜交，留在了探針上，因而可刪除所有這種非解DNA長鏈S1與S2獲得試管T2。試管T2即為操作解空間(數據池)Ψ(Ml)。
（4）搜索滿足著色條件的數據集，并輸出運算結果。
①將最終試管T2中加入緩沖溶液，對DNA鏈進行凝膠電泳。
②得到分子量最大的DNA鏈，該鏈即為輸出結果。
(5)對運算結果進行DNA序列測定，獲得結果α(G)。將輸出結果的DNA鏈去掉凝膠，讀出結果鏈的堿基序列。
（6）End。
4 結束語
在充分利用DNA分子結構的特征及常規生物操作的基礎上，本文利用簡單編碼及特殊探針設計獲得了針對圖獨立數問題的一種有效的DNA算法，將數學問題的求解與生物技術密切結合起來。本算法利用設計的鏈接鏈直接生成數據池，進而利用探針進行簡單的刪除操作，即可獲得解空間。由于設計了獨特的探針，頂點編碼十分簡單，因而該算法具有可操作性與可實現性，可直接求得G的所有最大獨立集。
本算法進一步研究的問題是探針數目較多，因而計算代價較大，需要進一步簡化。其次，DNA計算的本質是以空間復雜度換取時間復雜度，以大規模的并行運算及巨大的信息存儲能力，使求解NP完全問題的計算時間由指數復雜度降為多項式復雜度，但空間復雜度仍是“指數爆炸”的。本算法雖然具有可操作性與可實現性，但仍未能完全克服解空間的指數爆炸問題，從目前的研究結果來看，DNA遺傳算法是克服指數爆炸的一個比較有前景的方向[10，15]。但是這方面的研究目前面臨許多理論和生物技術方面的難題，因此，在探索DNA遺傳算法的同時，尋找其他有效算法（Volume Efficient Algorithm）仍將是DNA計算迫切需要解決的問題。另外，雖然DNA分子的合成、鏈接、雜交、變性、PCR擴增及電泳均是DNA重組技術的常規操作，但是現有的DNA重組技術仍不是十分完備的，均存在一定的誤差，需要用各種方法來減少誤差的積累并消除對解的干擾。因此，DNA計算還需要分子生物學技術的進一步發展，使得差錯率控制在一定的范圍之內。
參考文獻：
[1]Adleman L. Molecular Computation of Solution to Combinatorial Problems[J]. Science，1994，266(11):10211024.
[2]許進，張軍英，保錚.基于Hopfield網絡的圖的著色算法[J].電子學報，2005，24(10):813.
[3]Shenshen Gu， Songnian Yu. A Chaotic Neural Network for the Graph Coloring Problem in VLSI Channel Routing[C].ICCCAS， vol 21， 2004.10941098.
[4]Di Blas A， Jagota A， Hughey R. Energy Functionbased Approaches to Graph Coloring[J]. IEEE Transactions on Neural Networks， 2002，13(1):81-91.
[5]Mahonen P， Riihijarvi J， Petrova M. Automatic Channel Allocation for Small Wireless Local Area Networks Using Graph Colouring Algorithm Approach[C]. PIMRC， 2004.536-539.
[6]Fangwan Huang， Guolong Chen. A Symmetrybreaking Approach of the Graph Coloring Problem with Gas， vol 2[C]. The 8th International Conference on Computer Supported Cooperative Work in Design， 2004.717-719.
[7]Wenbin Liu， Fengyue Zhang， Jin Xu. A DNA Algorithm for the Graph Coloring Problem[J]. Journal of Chemical Information and Computers， 2002，42(5):11761178.
[8]高琳，許進.圖的頂點著色問題的DNA算法[J].電子學報，2003， 31(4):494-497.
[9]金迅嬰，劉光武，潘林強.圖著色問題的表面DNA算法[J].交通與計算機，2003，21(1):6-8.
[10]霍紅衛，許進，保錚.分組遺傳算法用于圖的著色[J].西北民族學院學報(自然科學版)，2000，21(1):511.
[11]劉文斌，高琳，王淑棟，等.最大匹配問題的DNA表面計算模型[J].電子學報，2003，31(10):14961499.
[12]馬潤年，張強，高琳，等.圖的最大權團的DNA計算[J].電子學報，2004，32(1):1316.
[13]孫惠泉.圖論及其應用[M].北京:科學出版社，2004.108117.
[14][美]Keller G H， Manak M M.DNA探針技術[M].北京:科學出版社，1992.115.
[15]Deaton R. A DNA Based Implementation of an Evolutionary Search for Good Encodings for DNA Computation[C]. Indianapolis: Proceedings of IEEE International Conference on Evolutionary Computation， 1997.267271.
作者簡介：
孫川(1959-)，男，湖北黃岡人，副教授，碩士，主要研究方向為人工智能及神經網絡；朱翔鷗(1969-)，男，講師，碩士，主要研究方向為智能計算及生物信息學；劉文斌(1969-)，男，副教授，博士，主要研究方向為DNA分子生物計算、遺傳算法及其在組合優化問題中的應用。
注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文
