進(jìn)化算法及其在生物信息中的應(yīng)用.pdf

1、進(jìn)化算法是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法,主要包括遺傳算法(Genetic Algorithm,GA)、遺傳規(guī)劃(Genetic Programming,GP)、進(jìn)化策略(Evolutionary Strategies,ES)、進(jìn)化規(guī)劃(Evolutionary Programming,EP)、粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法以及近年出現(xiàn)的量子粒子群優(yōu)化(Quantum

2、-behared Particle Swarm optimization,QPSO)算法,它們通過一系列的進(jìn)化算子和進(jìn)化方程,尋找問題的最優(yōu)解。本文把上述的進(jìn)化算法及其改進(jìn)的進(jìn)化算法,結(jié)合數(shù)學(xué)模型,用于解決生物信息中的各種問題。主要工作概括如下:
　　 (1)針對QPSO算法會出現(xiàn)早熟收斂的缺點(diǎn),結(jié)合選擇操作,提出兩種改進(jìn)的QPSO算法,并且施加到全局最優(yōu)位置上來提高算法搜索能力,一種是基于錦標(biāo)賽選擇的QPSO算法,另一種是基于

3、輪盤賭選擇的QPSO算法。并且從理論上證明了此算法的全局收斂性。實(shí)驗(yàn)中用了20個標(biāo)準(zhǔn)的單模多模、帶旋轉(zhuǎn)的單模和多模、帶偏移的單模和多模測試函數(shù)對算法進(jìn)行全面的測試,實(shí)驗(yàn)結(jié)果表明,基于選擇操作的QPSO算法尋優(yōu)能力強(qiáng),搜索能力高。
　　 (2)解決生物信息中多序列比對的問題,多序列比對是生物序列分析中的一個基本的重要的內(nèi)容。本文提出兩種方法來解決多序列比對問題,一種方法為,使用二進(jìn)制的PSO和二進(jìn)制的QPSO進(jìn)行序列的比對,為了避

4、免算法的早熟,在算法中還加入了變異算子;另一種方法為,使用QPSO算法和改進(jìn)的QPSO算法,結(jié)合隱馬爾可夫模型進(jìn)行序列的比對。核酸序列和蛋白質(zhì)序列的比對結(jié)果表明,上述兩種方法可以找出較優(yōu)的比對結(jié)果。
　　 (3)解決代謝網(wǎng)絡(luò)中代謝流的評估問題,代謝流的評估問題是一個帶約束的優(yōu)化問題,其目標(biāo)函數(shù)是一個非線性,不可微的并且存在多個局部最小點(diǎn)的復(fù)雜函數(shù),文中也采用兩種方法來解決此問題,一種為進(jìn)化算法加單值分解,一種為QPSO算法和基于

5、選擇操作的QPSO算法加罰函數(shù)。谷氨酸棒桿菌(Corynebacterium glutamicum)的內(nèi)部代謝流的評估結(jié)果表明了兩種算法能夠以較快的收斂速度找到較好的接近最優(yōu)點(diǎn)的量化值。
　　 (4)針對發(fā)酵中培養(yǎng)基的優(yōu)化問題,利用GP的方法來建立優(yōu)化模型,并使用QPSO算法分別來優(yōu)化模型的系數(shù)和模型的系數(shù),實(shí)驗(yàn)結(jié)果表明GP-QPSO算法能產(chǎn)生最大的透明質(zhì)酸產(chǎn)量,盡管響應(yīng)面分析法(response surface methodo