資源描述：
《DNA計(jì)算在二次分配問題中的應(yīng)用研究》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、DNA計(jì)算在二次分配問題中的應(yīng)用研究呂聰穎趙剛彬邵艷玲鄭珂呂冠廷（吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長春130012）E-mail:lvcongying0601@126.com摘要：DNA計(jì)算（DNAcomputing）是一種新的計(jì)算方法，其高度并行性和巨大的信息存儲能力為NP－完全問題的解決提供了一種全新的方法。本文采用了該算法去解決二次分配問題（QAP），構(gòu)造了該問題的表達(dá)方法，建立了該問題的算法模型。本文應(yīng)用DNA計(jì)算的方法去解決QAP問題是一種嶄新的嘗試，它對于我們將DNA計(jì)算的方法應(yīng)用于組合優(yōu)化問題無疑具有啟發(fā)性，并為我們進(jìn)一步深入研究奠定了基礎(chǔ)。
2、關(guān)鍵字：DNA計(jì)算、二次分配問題、凝膠電泳、聚合酶鏈?zhǔn)椒磻?yīng)、親和純化中圖分類號：TP31文獻(xiàn)標(biāo)識碼：A文章編號：TheResearchofDNAAlgorithmforQAPCongyingLV，ZhezhouYU，ChunguangZhou，KangpingWang，WeiPang(InstituteofComputerScienceandTechnology,JilinUniversity,Changchun130012,P.R.China)Abstract：Inthispaper，wegiveabriefdescriptionoftherealiz
3、ationmethodsofDNAcomputing,andthenuseaDNAcomputingtosolvethequadraticassignmentproblem，andproposeanovelpresentationfortheproblemandfoundamodelofthecomputing.It’sakindofbrand-newtrythatthepaperusesDNAcomputingtosolveQAPproblem.ItisundoubtedlyenlighteningtoapplytheDNAcomputingtothe
4、othercombinationoptimizationproblems，anditwillestablishthefoundationoffurtherinvestigation。Keywords：DNAcomputing、quadraticassignmentproblem、GelElectrophoresis、polymerasechainreaction、affinityseparation1．引言二次分配問題[1]（quadraticassignmentproblem,簡稱QAP）是一種典型的組合優(yōu)化問題，已被歸入NP－h(huán)ard問題。該問題的描
5、述如下：給定n個設(shè)施和n個地點(diǎn)，要求給每個設(shè)施分配一個位置；定義兩個n*n矩陣，即A=（fij）和B＝(dij),其中fij表示設(shè)施i和設(shè)施j之間的流量，dij表示地點(diǎn)i和地點(diǎn)j之間的距離。目標(biāo)是找到一個排序P=(P1,P2,…Pn)使其：Minimize其中L(i)表示設(shè)施i被分配的地點(diǎn)，P∈∏(n)。目前，該問題已經(jīng)得到深入的研究，進(jìn)化策略(evolutionstrategies)、遺傳算法(geneticalgorithms)、遺傳規(guī)劃(geneticprogramming)、進(jìn)化規(guī)劃(evolutionaryprogramming)等統(tǒng)稱為進(jìn)化計(jì)
6、算[2](evolutionarycomputation)的方法以及螞蟻算法等為該問題的求解提供了獨(dú)特的思路。DNA計(jì)算[2]是一門新的學(xué)科。這門學(xué)科主要研究如何利用DNA分子根據(jù)Watson-Crick互補(bǔ)配對原則進(jìn)行極度并行計(jì)算的特點(diǎn)去解決人類數(shù)學(xué)中的問題。目前已驗(yàn)證有大量的問題可以通過DNA計(jì)算來解決。最早的，也是最著名的是1994年Science上發(fā)表的美國科學(xué)家Adleman的七節(jié)點(diǎn)Hamilton路徑問題的DNA計(jì)算解決辦法。此外，2001年11月22日Nature雜志上關(guān)于威茲曼實(shí)驗(yàn)室制造出自動DNA計(jì)算機(jī)的報(bào)道，再一次向世人證明了DNA分
7、子具有強(qiáng)大的計(jì)算能力。在先前的研究啟示下，本文嘗試著用DNA計(jì)算的方法去解決QAP問題，它對于我們將DNA計(jì)算方法應(yīng)用于其它的組合優(yōu)化問題無疑具有啟發(fā)性，并為我們進(jìn)一步深入研究奠定了基礎(chǔ)。1．DNA計(jì)算概述2．1DNA計(jì)算的關(guān)鍵過程DNA計(jì)算解決問題的基本思想[2]：利用DNA特殊的雙螺旋結(jié)構(gòu)和堿基互補(bǔ)配對原則對問題進(jìn)行編碼，將所要處理的對象映射成DNA分子鏈，在DNA溶液的試管里，在生物酶的作用下，通過可控的生化反應(yīng)生成問題的解空間。最后，利用分子生物技術(shù)如：聚合酶鏈?zhǔn)椒磻?yīng)PCR、親和純化、凝膠電泳和磁珠分離等，破獲運(yùn)算結(jié)果。2．2DNA計(jì)算的數(shù)學(xué)機(jī)理
8、DNA的單鏈可看作由4個不同符號A、G、C和T組成的串，不難發(fā)現(xiàn)，如果給這四個元
