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