組合優(yōu)化中的DNA計算殷志祥董亞非許進(華中科技大學控制科學與工程系,武漢430074 )E-mail zxyin@mail.hust.edu.cn摘要由于電子計算機的存貯量小運算速度慢智能化低特別是制造工藝趨于極限等特點,因此,目前采用DNA計算的可能性引起了人們的廣泛關(guān)注尤其是它的良好的并行性。該文在簡要介紹DNA計算的實施方法后探討了DNA計算及其相關(guān)的數(shù)學模型指出了DNA計算的優(yōu)點及存在的問題。最后簡述了DNA計算與圖論、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)、納米材料等的聯(lián)系。關(guān)鍵詞圖論遺傳算法 人工神經(jīng)網(wǎng)絡(luò) 納米科技 計算文章編號1002 -8331-( 2002 )19- -0025- -03文獻標識碼 A中圖分類號 TP301.6DNA Computing in Combination and OptimizationYin Zhixiang Dong Yafei Xu Jin( Department of Control Science and Engineering ,Huazhong University ofScience and Technology ,Wuhan 430074 )Abstract: Due to electronie computer of small storage capacity slow operation speed and low intelligence particularlylimited manufacture technics recently ,the possibility of using DNA as a computing tool arouses abroad interests ofresearchers.Especially it is highly parallel.After a brief introduction on implementation of DNA computing ,this paperdiscusses DNA computing and correlational mathematics models.The paper points out the advantages and existingproblems.Finally it simply introduces the contact between DNA computing and graph theory Genetic algorithm artificialneural networks and Le meter material.Keywords : Graph theory ,Genetic algorithm Artificial neural networks Le meter material ,Computing1引言過交叉互相交換鏈.上的核苷酸。從DNA的原理來看,它與數(shù)學電子計算機在人類社會起到了巨大的促進作用但由于電操作非常類似,單連DNA可看作由四個不同符號A、T、C、G組子計算機的存貯量小運算速度慢智能化低導致人們迫切希成的串。它在數(shù)學上就像電子計算機中編碼0”和1"一樣可望尋找一種能克服上述缺點的新型計算機。1953 年Waston和表示成四字母的集E={A T C G)來譯碼信息。DNA鏈可作為Crick發(fā)現(xiàn)DNA之后,人們發(fā)現(xiàn)許多操作DNA的方法。如酶譯碼信息酶可看作模擬在DNA鏈上簡單的計算。不同的酶用切、粘、貼、電泳、聚合鏈反應(yīng)、加熱、退火等。這些操作DNA的于不同的算子,如,限制內(nèi)切酸酶可作為分離算子,DNA 連結(jié)方法有助于人們解決內(nèi)存及信息的輸入和接收。酶可作為聯(lián)結(jié)算子,DNA 聚合酶可作為復(fù)制算子,外 切酶可作為刪除算子等。2計算的原理DNA計算的研究涉及許多方面,DNA 計算具有通用性、時DNA是重要的基因物質(zhì),它攜帶著生物的遺傳信息。DNA空復(fù)雜性、有效性及容錯性。由于DNA分子計算技術(shù)的應(yīng)用潛的基本元素是核苷酸。由于化學結(jié)構(gòu)的不同核苷酸劃分為四力十分巨大,DNA計算機的構(gòu)想是一種創(chuàng)新 ,它的運算速度極類堿基:腺嘌呤(A )鳥嘌呤(G)胞嘧啶(C )和胸腺嘧啶(T)?？烊绻麅蓚€分子DNA的連接被看作一次運算那么這種基于DNA是由兩條極長的單鏈核苷酸組成,這兩條極長的單鏈核DNA分子的運算每秒鐘可大約進行10'5 次或更多次,其運算苷酸利用堿基之間的氫鍵而結(jié)合在一起形成-條雙鏈的螺旋速度超過當前超級計算機1000倍淇次其存貯量巨大,1立結(jié)構(gòu),且一條單鏈中的堿基序列與另-條單鏈中的堿基序列互方米的DNA溶液可存儲1萬億位二進制的數(shù)據(jù),超過當前所補A和T配對C和G配對。每個染色體是-段雙鏈螺旋的有計算機的存貯量;另外它的高度并行性及極低的能耗(DNADNA.遺傳信息以A、T、C、G在核苷酸中的排列順序而體現(xiàn)其運算反應(yīng)過程中所消耗的能量只有-臺普通的計算機的十億.排列順序的多樣性構(gòu)成了豐富的遺傳信息細胞利用遺傳信息分之一)。Agsymetrix公司制造的生物芯片能正確地診斷出主要有三種復(fù)制、轉(zhuǎn)錄和翻譯。通過DNA的復(fù)制而保留遺傳BACAI基因中國煤化工博土等的試驗室使信息。遺傳信息從細胞核傳到細胞質(zhì),是把DNA轉(zhuǎn)錄成mR-用已知的39!YHCNMHGE經(jīng)制備了-種Ag-NA。tRNA起調(diào)節(jié)作用將氨基酸插入到多聚氨基酸的合適位gy metrix芯片，開且止在研究更新的心片。其可以攜帶2000置。重組或交叉是DNA交換遺傳信息的過程，兩條DNA鏈通.種位點變異的樣本,這類芯片進行遺傳病家譜的研究。Aggy基金項目:國家自然科學基金資助(編號:60174047 60103021 )作者簡介:殷志祥男副教授博士主要從事圖論與DNA計算的研究。計算機工程與應(yīng)用2002.19 2metrix公司正在嘗試將更多的DNA探針放到芯片上,通過壓DNA計算與遺傳算法的集成遺傳算法(GA)用于模擬生縮DNA探針生產(chǎn)出160萬DNA探針的芯片。這為DNA計算命的自適應(yīng)和進化被用于設(shè)計好的機器和編制自進化的計算機的產(chǎn)生提供了有力的依據(jù)。機程序,由于常規(guī)GA用于實際問題,尤其是處理復(fù)雜的、混淆的和多任務(wù)問題時不夠靈活,且計算速度慢,- 些學者提出了3計算與組合優(yōu)化問題基于DNA機理的改進的GA。如帶有雙鏈DNA的GA用于促1994年Adleman首次用試驗顯示了DNA計算的可能性,進DNA復(fù)制的非對換變異21類似DNA編碼的系統(tǒng)描述"用介紹了采用DNA進行特定目的計算的可行性"成功地解決了于各種進化系統(tǒng)細胞特定化的模型叫。在細胞特定化的過程中,有向圖的Hamilton 路徑問題。先將圖中各個頂點口;用一個任每個細胞具有相同的DNA,硬件建模和計算機仿真顯示了細意的20個堿基單鏈DNA片斷來代替D0; 弧分別用0;頂點的胞特定化具有自組織特性。另外還提出了基于生物學DNA編后10個堿基的互補堿基和n;的前10個堿基的互補堿基構(gòu)成碼方法的GA.這種方法具有DNA染色體中的重復(fù)性和基因表的DNA片斷來代替。然后將足量的上述DNA片斷放入溶液達的重疊性并使交叉和變異操作變得容易。模糊系統(tǒng)在許多中通過連接反應(yīng)隨機生成若干條有向路徑。再利用引物通過領(lǐng)域中已獲得成功應(yīng)用,但對于復(fù)雜的多輸入多輸出模糊系統(tǒng)PCR技術(shù)對上一步的產(chǎn)物進行擴增就可以有選擇地擴增那些目前仍缺乏有效的設(shè)計方法。雖然常規(guī)GA能用于獲取模糊控自起點到終點的鏈。接下來利用瓊脂糖凝膠電泳得到的140制規(guī)則,但有時難以勝任復(fù)雜系統(tǒng),如多輸入多輸出模糊系統(tǒng)堿基對的譜帶就是恰恰經(jīng)過7個頂點的路徑的DNA鏈。割下的優(yōu)化工作。故一些作者提出了基于DNA編碼機理的GA并這條帶浸入雙蒸水中提取DNA(凝膠分離)PCR擴增及凝膠用于多變量模糊系統(tǒng)的優(yōu)化。它能用于模糊系統(tǒng)的輸入變量的分離多次重復(fù)可有效提高純度。然后利用探針挑選出只經(jīng)過選擇和映射函數(shù)參數(shù)的調(diào)整,從而自動獲取模糊控制規(guī)則。并每個頂點一次的DNA鏈最后用凝膠電泳檢測它的存在性。且病毒和酶操作也用于這種DNA編碼方法。機器人運動控制1995年Lipton在Adleman的試驗基礎(chǔ)上,解決了更有趣的研究中初步顯示了這種方法的可行性。集成生物的神經(jīng)組織的NP完備問題(可滿足問題尸。首先利用DNA鏈表示問題的.的生成和功能受DNA遺傳信息作用故DNA遺傳信息可用于所有可能解然后利用生物反應(yīng)刪除無效解,從而表明了DNA神經(jīng)網(wǎng)絡(luò)的建模和優(yōu)化。-種采用DNA序列譯碼的框架被用計算能起到高效搜尋機制的作用。對于計算機科學與數(shù)學在于建立神經(jīng)網(wǎng)絡(luò)(NN)模型。這種神經(jīng)網(wǎng)絡(luò)模型與采用常用尋找適當?shù)膯栴}和有效分子算法去解決更為復(fù)雜的系統(tǒng)模型CODE-4譯碼框架的神經(jīng)網(wǎng)絡(luò)相比能更好地預(yù)測分開DNA序的計算問題。Adleman和Lipton分別解決了有向圖的Hamilton列的topoisomerase可能性,且該網(wǎng)絡(luò)大小是后者的1/4 ,因而路徑問題和求解SAT問題。T.Head等解決了最大獨立集問題叭。該神經(jīng)網(wǎng)絡(luò)模型的參數(shù)數(shù)目減少了近75%。納米技術(shù)為DNA而且以上所述問題都是用DNA計算來完成的。不僅如此用提供了可行性和理論依據(jù),它使得人們能在極小的芯片上集成DNA計算還能解決最小覆蓋問題圖著色問題圖的可平面性大量的DNA探針,從而可以利用DNA芯片進行復(fù)雜的計算和問題,圖同構(gòu)問題,Ramsey 問題等等著名的NP問題和一些待大量的信息存儲,納米芯片的提出及進展將直接推動DNA計解決問題。Qinhua Liu 等成功地解決了SAT問題4這象征著算機的研制和產(chǎn)生。DNA計算向DNA計算機邁進了更大一步。Beave 提出了如何建立和操作含單個DNA分子的圖靈機凹Smith和Scheweitzer表5DNA的優(yōu)點及目前存在的問題明DNA分子和標準實驗室技術(shù)可用于建立一個非確定性圖靈DNA計算的優(yōu)點主要在于DNA具有高度的并行性,目 前機問,Winfree描述了一種基于自裝配單鏈核酸鏈網(wǎng)絡(luò)的空間圖最快的巨型機每秒能執(zhí)行102個操作。而DNA計算機的重要靈機”。另外連結(jié)方法也被用于模擬圖靈機。Daum 顯示了使特點在于它的巨大并行處理。在LAdleman的初始實驗中通用DNA和分子生物學工具能達到編碼1020 個字的聯(lián)想記過適當估計,DNA鏈的并行操作數(shù)目可達104。 雖然DNA計算憶%。RooB和Wagner則表明,若沒有時間限制Lipton模型能.的每個操作本身與電子實現(xiàn)相比很慢,但DNA反應(yīng)的巨大并處理任何計算問題[叫,Yinetal給出了中國郵遞員問題的DNA行性足以滿足當前巨型機或更強的計算挑戰(zhàn),其次DNA計算計算模型這些證明顯示了存在DNA計算機的許多可能結(jié)構(gòu)。有很高的能量效率和存貯容量,電子計算機操作過程效率非常同時科學家正在利用遺傳DNA研制-種全新概念的計算機。低,巨型機執(zhí)行10° 個操作需要1焦耳能量,而用于實現(xiàn)DNA他們認為這種計算機的運算速度和信息存儲量大大超過目前計算操作的酶是在進化中產(chǎn)生的具有很高的能量效率,1焦的計算機?？茖W家們指出DNA含有大量的遺傳密碼他通過生耳的能量足以執(zhí)行2x109個操作,DNA分子允許非常高的信息化反應(yīng)傳遞遺傳信息。DNA分子中的密碼相當于存儲的數(shù)據(jù)存貯密度:1 位/nm3 ,而當前錄像帶的信息存貯密度僅為1位/DNA分子之間可以在某種酶的作用下瞬間完成生物化學反.12nm2。計算目前還存在許多問題盡管DNA計算的研究已取應(yīng),從一種基因代碼變?yōu)榱?種基因代碼。反應(yīng)前的基因代碼得一些進展,但DNA計算還有許多實際和理論問題有待解決?？梢钥醋鬏斎氲臄?shù)據(jù),反應(yīng)后的基因代碼可看作運算的結(jié)果,首先在DNA計算實驗中如何選擇實際操作參數(shù)的數(shù)目、個體如果控制得當那么就可以利用這種過程制作-種新型的計算的操作速度、個體操作和序列操作的可靠性、信息載體的穩(wěn)定機?？茖W家們認為這種新型的計算機將在5年內(nèi)取得實質(zhì)性的進展。從實際角度來看,自然科學的兩個前沿領(lǐng)域分子生物學電子計算機中國煤化工技術(shù)及納米技術(shù)的進和計算機科學的有機結(jié)合,一定會創(chuàng)造出驚人的遺傳奇跡。-步發(fā)展等。|YCNMHGDNA計算機- :旦產(chǎn)生諸多NP問題和待解決問題都將可以直接進行計算R(55和R(66就有可能在幾分鐘內(nèi)解決。參考文獻1.AdlemanLM.MolecularComputationoSolutionstoCombinatorialProblems[J]4計算與其它模型.Science ,1994 266( 5187 ):1021-102326 2002.19 計算機工程與 應(yīng)用2.Lipton R J.DNA Solution of Hard Computation Problem[J.Sience ,1995 ( 268 ) 583~5859.Baum E B.Building an Associative Memory Vastly Larger than the3.T head et al.Computing with DNA by operating on plasmids[].Bio-Brain[J.Science ,1995 ( 268 ) 583~585Systems 2000 (57 )87-9310.Roo β D ,Wagner K W.On the Power of DNA-Computing[J.Infor-4.Qinhua liu et al.DNA computing on surfaces[J].Nature ,2000 ;403 :mation and Computation 1996 ;131( 2) 95~109175-17911.Zhixiang Yin ,Fengyue Zhang Jin Xu.A Chinese Postman Problem5.Beave D.Computing with DNA[J].Journal of Computational Biology ,Based on DNA Computing[J]Journal of Chemical Infomation and Con-1995 2(1 ):1~8puter Sciences 2002 ;42( 2)222~2246.Smith w Schweitzer A.DNA Computers in Vivo[C].In :DIMACS Work-12.DoiH ,FurusawaM Evolutionis Promotedby Asymmetrial Mutationsinshop on DNA Bead Computing Princeton ,1995DNA Replication-Genetic Algorithmwith Double- -Stranded DNAJ.Fu-7.Winfree EOn the Computational Power of DNA Annealing and Li-jitsu Scientificand Technical Journal ,1996 3x 2 ) 248~255gation[C.In E B Baumand R J Lipton editors DNA based Computers ,13.NakanoKetal.ASelf-OrganizingSystemwithell-Specialization[C].In Pro-American Mathematical Society ,1996ceedings of 1997 IEEE Intermational Conference on Evolutionary Com-8.Rothemund P A.DNA and Restriction Enyme Implementation of Tur-putation ,Indianapolis IN USA ,1997-04 279~284ing Machine[C].In E B Baumand R J Lipton editors DNA based Com-(上接18頁)制導致網(wǎng)絡(luò)擁塞增加和數(shù)據(jù)傳輸效率的降低,從而引起端到端到端平均時延指源節(jié)點有數(shù)據(jù)發(fā)送至接收節(jié)點收到數(shù)端平均時延的增加。flooding協(xié)議在低帶寬MPRN上會產(chǎn)生嚴據(jù)之間的時間,包括建立路由時間和數(shù)據(jù)轉(zhuǎn)發(fā)時間。重的網(wǎng)絡(luò)擁塞，因而大大增加了端到端平均時延。嘎2 分組遞交成功率(%度化情況移動速度多 播組成員節(jié)點數(shù)5結(jié)束語(km/h) 5 10 20 30flooding該文提出了應(yīng)用于移動分組無線網(wǎng)的多播路由算法及其87.5 73.0 63.0 65.0 72.8實現(xiàn)方法?？紤]到節(jié)點的移動性和無線通信帶寬的限制采用2091.2 74.5 69.0 66.2 72.7了按需路由發(fā)現(xiàn)策略減小控制開銷提高算法的執(zhí)行效率,使4091.275.0 66.0 67.0 72.0之能夠適應(yīng)具有較低帶寬的大規(guī)模動態(tài)網(wǎng)絡(luò)環(huán)境。從模擬實驗500.0 75.0 66.0 67.2 72.58090.0 75.0 68.0 67.5_ 71.3結(jié)果來看,在網(wǎng)絡(luò)帶寬有限和網(wǎng)絡(luò)拓撲結(jié)構(gòu)變化的條件下具表2列出了在不同多播組成員個數(shù)的情況下,分組遞交成有穩(wěn)定的分組轉(zhuǎn)發(fā)成功率和良好的伸縮性獲得了較好的多播功率隨著節(jié)點移動速度變化而變化的情況。在表中可以看出。數(shù)據(jù)傳輸質(zhì)量。同時還需要進-步分析網(wǎng)絡(luò)和算法的各個參數(shù)當多播組成員較少時,分組轉(zhuǎn)發(fā)成功率在87.5%以上。隨著多對路由性能的影響，實現(xiàn)各個參數(shù)的合理配置,以進一步提高播組成員數(shù)量的增加,雖然建立的轉(zhuǎn)發(fā)組網(wǎng)格會產(chǎn)生更多的數(shù)路由效率和可靠性。(收稿日期:2002年6月)據(jù)傳輸冗余鏈路,有助于提高分組傳輸?shù)目煽啃?。但由于網(wǎng)絡(luò)帶寬的限制及擁塞的增加，使得分組轉(zhuǎn)發(fā)成功率有所下降最參考文獻后穩(wěn)定在60%至70%間。flooding協(xié)議的分組遞交成功率在1.Deering s E ,Cheriton D R.Multicast routing in datagram internet-72%左右。另外,節(jié)點移動速度的變化對分組遞交成功率的影works and extended lans [J].ACM Transactions on Computer Systems ,1990 &(2 )85~110響較小。2.Moy JMulticast Routing Extensions for OSPF [J].Communications of表3端到端平均時 延( ms變化情況the ACM ,1994 37(8)61-66移動速度多播組成員節(jié)點數(shù)3.Deering S ,Estrin D L ,Farinacci D et al.The PIM architecture for(km/h)_5_1020二30- foodingwide-area multicast routingJ]IEEE/ACM Transactions on Networking ,78 81 140.0 1351996 ;( 2):153-1626566.7 126.5 160.0 154.04.Lee Sung- Ju Su W lliamn ,Gerla Mario.On- Demand mulicast routing70 77.2 935 168.0 200.0protocol( ODMRP )Yor ad hoc networks.IETF Intemet Draft [EB/OL].60 71.2 125.4 113.7 207.265 66.9 104.7 181.2 225.5http /ww..t.org/internet drafs/ratft-itf- manet -dmrp- -02.txt 2000-端到端平均時延包括路由請求時間和數(shù)據(jù)傳輸時延。路由7-12/2001-12-14請求時間主要用于路由信息的產(chǎn)生和刷新上,由于需要泛洪請5.Johnson David B ,Maltz Davis A.The dynamic source routing protocolfor mobile ad hoe networks IETF Internet Draft EB/OL.htp ://www.求分組來建立路由路由請求時間受組成員數(shù)量、網(wǎng)絡(luò)拓撲結(jié)ietf.org/ internet- -drafts/ draft- ietf- -manet- -dsr- _03.txt ,1999-10- -8/2001-構(gòu)的變化和節(jié)點移動速度的影響較小路由請求時間-般保持12-14在34至35ms之間。數(shù)據(jù)傳輸時延由于受到拓撲結(jié)構(gòu)變化和6.Ucla compu中國煤化工mputing laboratory and傳輸帶寬的限制,變化較大。從表3中可以看出隨著多播組成wireless ac:A scalable simulationC NMHG員節(jié)點數(shù)量的增加端到端平均時延從67.6ms(5個組節(jié)點)增environment:YHIstems [EB/0L.http ://加到151.4ms(30個組節(jié)點)，這是由于受到無線信道帶寬的限pel.cs.ucla.edu/ projects/domains/glomosim.html 2000 -9- 12/2001-12-14計算機工程與應(yīng)用2002.19 27