智能優(yōu)化理論-第4章DNA計(jì)算

第4章DNA計(jì)算目錄概述DNA的結(jié)構(gòu)DNA計(jì)算的原理DNA與遺傳算法的集成復(fù)習(xí)思考題01概述概述計(jì)算機(jī)技術(shù)被認(rèn)為是20世紀(jì)三大科學(xué)革命之一，電子計(jì)算機(jī)為社會(huì)的發(fā)展起到了巨大的促進(jìn)作用。02計(jì)算機(jī)科學(xué)家們也將計(jì)算的問題劃分為容易、困難和不可計(jì)算三類。03處理容易類的計(jì)算，目前的電子計(jì)算機(jī)能完全勝任，但處理困難類的問題時(shí)，電子計(jì)算機(jī)會(huì)隨著問題規(guī)模的增大，計(jì)算所需的時(shí)間以指數(shù)級增長。01量子物理學(xué)已經(jīng)成功地預(yù)測出芯片微處理器能力的增長不能長期地保持下去。計(jì)算機(jī)的小型化在技術(shù)上存在明顯的限制。分子水平上進(jìn)行計(jì)算的概念最早是在20世紀(jì)60年代早期由RichardFeynman提出的。概述01但是當(dāng)時(shí)尚缺乏適用的材料、工具與方法，F(xiàn)eynman的“超微型計(jì)算機(jī)”想法只能是一種超前的、美好的愿望。02生物領(lǐng)域發(fā)展到了分子水平，使生物學(xué)的研究深入到了分子水平，到了80年代，隨著人們對分子生物學(xué)理論的了解日益加深，現(xiàn)代生物化學(xué)、生物工程技術(shù)的日益完善，分子計(jì)算的條件事實(shí)上巳基本具備。031994年，美國南加州大學(xué)的LeonardM.Adleman博士用DNA計(jì)算的方法解決了有向Hamilton路問題，并成功地利用現(xiàn)代分子生物技術(shù)在DNA溶液的試管中進(jìn)行了實(shí)驗(yàn)。概述概述01這一研究成果很快引起了計(jì)算機(jī)、數(shù)學(xué)、分子生物學(xué)等領(lǐng)域的科學(xué)家們的極大興趣。02它的重要意義不僅在于算法和速度，更在于采用了一種全新的介質(zhì)作為計(jì)算要件。以生物技術(shù)來解決電子計(jì)算機(jī)無法解決的困難問題，并且開發(fā)了這種媒體潛在的并行性。0302DNA的結(jié)構(gòu)DNA中有4種堿基，即腺嘌呤(Adenine，A)、鳥嘌呤(Guanine，G)、胞嘧啶(Cytosine，C)和胸腺嘧啶(Thymine，T)。各種堿基間的不同組合就構(gòu)成了異常豐富的遺傳信息。科學(xué)家們指出．DNA含有大量的遺傳密碼，通過生化反應(yīng)傳遞遺傳信息。DNA鏈主要是由一個(gè)脫氧核苷酸上的5'-磷酸基和另一個(gè)脫氧核苷酸上的3'-羥基共價(jià)鍵連接而成。DNA的結(jié)構(gòu)DNA由兩條極長的核苷酸鏈利用堿基之間的氫鍵結(jié)合在一起，形成一條雙股的螺旋結(jié)構(gòu)，且一股的堿基序列與另一股的堿基序列互補(bǔ)。A和T配對．C和G配對。堿熬的上述配對關(guān)系稱為Watson-Crick（WC）配對。DNA有兩個(gè)最主要的功能：第一個(gè)功能是DNA攜帶遺傳信息，能轉(zhuǎn)錄成RNA，RNA再轉(zhuǎn)譯成蛋白質(zhì)；第二個(gè)功能是自我復(fù)制。DNA的結(jié)構(gòu)DNA一般為長而無分支的雙股線型分子，但有些為環(huán)形，也有少些為單股環(huán)形。每個(gè)染色體是一段雙股螺旋的DNA。遺傳信息以A、T、C和G在核苷酸中的排列順序而體現(xiàn)，其排列順序的多樣性體現(xiàn)了豐富的遺傳信息。從生物DNA到蛋白質(zhì)的形成過程。首先，通過轉(zhuǎn)錄作用將DNA中攜帶的遺傳信息轉(zhuǎn)錄到信使RNA（mRNA）中。DNA的結(jié)構(gòu)在從DNA到蛋白質(zhì)的形成過程中，大多數(shù)堿基并沒有用來合成蛋白質(zhì)．它們首先從DNA上轉(zhuǎn)錄，將沒有用的部分拼接，拼接后就形成了mRNA。密碼子對應(yīng)于氨基酸的遺傳密碼表如表4.1所示。然后，通過翻譯作用，將mRNA中攜帶的遺傳信息轉(zhuǎn)譯成含特定氨基酸序列的蛋白質(zhì)，蛋白質(zhì)則構(gòu)成了細(xì)胞。在生物DNA中，基因是儲(chǔ)存遺傳信息的基本單位，一個(gè)基因開始于起始密碼子ATG，終止于終止密碼子TAA、TAG或TGG。在mRNA中排列著由三個(gè)連續(xù)的堿基組成的密碼子，這些密碼子是合成蛋白質(zhì)的密碼。64種密碼子對應(yīng)20種氨基酸。DNA的結(jié)構(gòu)03DNA計(jì)算的原理DNA計(jì)算是一種新的計(jì)算思維方式，同時(shí)也是關(guān)于化學(xué)和生物的一種新的思維方式。生物與數(shù)學(xué)的過程有各自的復(fù)雜性，但它們具有一個(gè)重要的共性，即生物所具有的復(fù)雜結(jié)構(gòu)實(shí)際上是結(jié)構(gòu)的編碼在DNA序列中的原始信息經(jīng)過一些簡單的生化處理后得到的。求一個(gè)含有變量的可計(jì)算函數(shù)的值也可以通過求一系列含變量的簡單函數(shù)的值來實(shí)現(xiàn)。DNA計(jì)算的原理DNA計(jì)算的本質(zhì)就是利用大量不同的核酸分子雜交，產(chǎn)生類似于某種數(shù)學(xué)過程的一種組合的結(jié)果，并根據(jù)限定條件對其進(jìn)行篩選的。大量隨機(jī)的DNA相互雜交后，每個(gè)DNA鏈所攜帶的原始信息就會(huì)與其他DNA鏈所攜帶的信息重新組合，形成一種類似數(shù)學(xué)組合的結(jié)果。根據(jù)DNA分子之間的Watson-Crick互補(bǔ)原理，不同的DNA分子根據(jù)其不同的末端，從而具有不同的方向性。DNA計(jì)算的原理VS對一種特定的運(yùn)算而言，這種結(jié)果的獲得是通過對DNA進(jìn)行一系列的連續(xù)操作來實(shí)現(xiàn)的。DNA計(jì)算就是利用不同形式的DNA鏈編碼信息，然后將攜有編碼信息的DNA鏈進(jìn)行互補(bǔ)雜交，最后，利用分子生物技術(shù)，如聚合酶鏈?zhǔn)椒磻?yīng)PCR(PolymerizeChainReaction)、并行重疊組裝技術(shù)POA(ParallelOverlapAssembly)、超聲波降解、親和層析、克隆、誘變、分子純化、凝膠電泳、磁珠分離等，捕獲運(yùn)算結(jié)果。DNA計(jì)算的原理經(jīng)典的計(jì)算科學(xué)理論是建立在一系列重要操作上的，大部分自動(dòng)機(jī)語言理論模型都是這樣的。DNA計(jì)算也是建立在一系列連續(xù)的分子操作上的，這些用于計(jì)算目的的分子生物操作在形式上具有多樣性：切割、粘貼、分離、連接、插入和刪除等。從理論上來講，合理地使用這些分子生物操作可以建立與圖靈機(jī)一樣強(qiáng)大的新的計(jì)算模型。DNA計(jì)算的原理DNA計(jì)算的原理從DNA的原理和一些生物操作工具來看，DNA計(jì)算與數(shù)學(xué)操作非常相似。DNA單鏈可看做由四個(gè)不同符號A、G、C和T組成的鏈。它在數(shù)學(xué)上就像計(jì)算機(jī)中的編碼“0”和“1”一樣，可表示成四個(gè)字母的集合∑={A，G，C，T）來編碼信息。04DNA與遺傳算法的集成DNA鏈（染色體）表現(xiàn)型DNA湯（群體）倒位基因型遺傳子座是多個(gè)遺傳因子的集合，由A、T、C、G編碼集合組成。是遺傳物質(zhì)的主要載體。DNA鏈上遺傳因子的位置，各個(gè)位置決定所遺傳的信息。是形成DNA鏈的內(nèi)部表現(xiàn)，它決定了生物體的性狀和特征。由DNA鏈決定形狀的外部表現(xiàn)，或者說是根據(jù)基因型形成的個(gè)體。DNA鏈帶有特征的個(gè)體的集合，該集合內(nèi)的DNA鏈的多少為DNA湯的大小。在DNA鏈中兩個(gè)隨機(jī)選擇位置之問的某些堿基序列進(jìn)行倒位。它可以使在父代中離得很遠(yuǎn)的位在后代中靠在一起．相當(dāng)于重新定義基因塊。基本概念和術(shù)語不過一個(gè)是用試管在分子生物學(xué)實(shí)驗(yàn)室里實(shí)施運(yùn)算，一個(gè)是用程序語言實(shí)現(xiàn)運(yùn)算，圖4.2給出了它們基本運(yùn)算框架的異同。啟發(fā)人們從兩個(gè)不同的領(lǐng)域相互借鑒，利用分子生物學(xué)新理論、新技術(shù)進(jìn)行遺傳算法的擴(kuò)展。遺傳算法和DNA計(jì)算有很多相似之處，如對特定符號集編碼的符號串進(jìn)行操作、具有很高的并行性等。DNA遺傳算法的關(guān)系和假設(shè)一些學(xué)者提出了基于DNA機(jī)理的改進(jìn)的遺傳算法，如帶有雙串DNA的遺傳算法用于促進(jìn)DNA復(fù)制的非對換變異。還提出了基于生物學(xué)DNA編碼方法的遺傳算法，這種方法具有DNA染包體中的重復(fù)性和基因表達(dá)的重疊性．并使交叉和變異操作變得容易。為了避免在DNA計(jì)算中，由于核酸堿基之間化學(xué)反應(yīng)帶來的誤差，一些研究者提出了用于DNA進(jìn)化計(jì)算中好的DNA譯碼算法。DNA遺傳算法的關(guān)系和假設(shè)遺傳算法可以直接使用DNA計(jì)算方法來實(shí)現(xiàn)，如JunghueiChen等人就成功地使用對DNA分子進(jìn)行操作的遺傳算法解決了一個(gè)最大數(shù)問題。目前有關(guān)遺傳算法和DNA計(jì)算兩者交叉領(lǐng)域的研究成果并不多見，但鑒于遺傳算法已取得的巨大成功和DNA計(jì)算具有的極大潛力，未來二者結(jié)合會(huì)對生物計(jì)算技術(shù)以及相關(guān)領(lǐng)域產(chǎn)生革命性的推進(jìn)作用。DNA遺傳算法的關(guān)系和假設(shè)使用n個(gè)具有任意DNA鏈的個(gè)體組成初始代群體(DNA湯)一條DNA鏈由4種堿基A、T、C、G的結(jié)合體構(gòu)成．可以表示多個(gè)基因。按編碼規(guī)則，將DNA湯中每一個(gè)DNA鏈的密碼子按表4.2（或表4.3）轉(zhuǎn)化成所對應(yīng)的參數(shù)值用于求解問題，并按某一標(biāo)準(zhǔn)計(jì)算其評價(jià)函數(shù)。DNA遺傳算法的實(shí)現(xiàn)適應(yīng)度的評價(jià)初始化及DNA鏈編碼若其評價(jià)函數(shù)值高，表示該DNA鏈有較高的適應(yīng)度。由于將DNA的4個(gè)堿基中的3個(gè)組合成密碼子的情況有64種．在翻譯參數(shù)時(shí)可將這64種組合對應(yīng)于[0,63]區(qū)間上的任意一個(gè)數(shù)，用于問題的求解。這里考慮的翻譯關(guān)系與生物DNA的遺傳密碼表不同，即不同的密碼子對應(yīng)于不同的參數(shù)。而在生物DNA中．允許不同的密碼子對應(yīng)相同的氨基酸（參見表4.2）。若其值在預(yù)定的范圍內(nèi)變化．那么密碼子的參數(shù)和實(shí)際參數(shù)值之間的轉(zhuǎn)換關(guān)系為式中，x∈[-9,9]。DNA遺傳算法的實(shí)現(xiàn)函數(shù)有許多局部極值點(diǎn)，其最大值在x=0.126附近。在采用DNA-GA對此函數(shù)尋優(yōu)的計(jì)算機(jī)仿真中，采用6位DNA編碼，交叉率和變異率分別選取為0.9和0.1，每代個(gè)體為30個(gè)。以上結(jié)果是比較滿意且合理的，同時(shí)也說明了DNA-GA在函數(shù)尋優(yōu)中是有效的。DNA-GA收斂后，對此函數(shù)尋優(yōu)得到的結(jié)果在x=0.125處取最大值。為了驗(yàn)證DNA-GA的有效性，我們以一個(gè)函數(shù)尋優(yōu)的例子來加以驗(yàn)證。DNA遺傳算法在函數(shù)尋優(yōu)中的應(yīng)用DNA-GA的結(jié)構(gòu)與常見遺傳算法的類似，是常規(guī)遺傳算法的發(fā)展，包含著常規(guī)遺傳算法所固有的優(yōu)點(diǎn)。DNA-GA對參數(shù)編碼進(jìn)行優(yōu)化，而不是直接操作參數(shù)本身，因此可以解決常規(guī)優(yōu)化方法難以解決的問題。DNA-GA利用適應(yīng)度進(jìn)行搜索，無需導(dǎo)數(shù)等其他信息，利用隨機(jī)操作指導(dǎo)著向最優(yōu)化方向前進(jìn)的搜索。010203與常規(guī)遺傳算法的比較與常規(guī)遺傳算法的比較DNA-GA具有智能化，即具有自組織、自適應(yīng)和自學(xué)習(xí)性等，具有隱性并行性，使相對少的編碼對應(yīng)范圍極大的解區(qū)域。DNA-GA比傳統(tǒng)的二進(jìn)制編碼方法有很大的改進(jìn)，更適合復(fù)雜知識的表達(dá)方式，且比較靈活，長度也大大縮短。由于編碼的豐富性及譯碼的多樣性，即使在變異概率低的情況下，也能保持一定水平的多樣性。123更便于引入基因級操作，發(fā)展遺傳操作算子，如倒位、分離、異位、多倍體結(jié)構(gòu)等，能大大地豐富進(jìn)化手段。例如倒位可以使在父代中離得很