一種改進(jìn)的自適應(yīng)遺傳算法在多序列比對中的應(yīng)用.pdf

1、生物信息學(xué)是由生物學(xué)、應(yīng)用數(shù)學(xué)和計算機(jī)科學(xué)相互交叉所形成的新型學(xué)科，是當(dāng)今生命科學(xué)和自然科學(xué)的重大前沿領(lǐng)域之一。其中，生物序列比對是生物信息學(xué)中一個最基本的研究方法，而多序列比對又是生物序列比對的最基本的任務(wù)，如何獲得比對質(zhì)量更好、時間空間效率更高的多序列比對算法是生物信息學(xué)研究的一個重要的課題。 多序列比對是NP完全問題，動態(tài)規(guī)劃算法是其基本算法，它可以找到一個得分最高(或代價最小)的序列對比排列，但當(dāng)序列數(shù)量增加時，計算量將

2、呈指數(shù)增長。在實際操作中，算法都會在計算速度和獲得最佳比對值之間尋求平衡。一個有效的方法是用遺傳算法這種近似算法求解，但遺傳算法有著易早熟、穩(wěn)定性差等缺點，所以本文提出一種改進(jìn)的自適應(yīng)遺傳算法，采用了適應(yīng)度值的標(biāo)定，并在進(jìn)化過程中實現(xiàn)了群體多樣性，同時利用構(gòu)造神經(jīng)元激活函數(shù)最常用的sigmoid函數(shù)，對交叉率和突變率進(jìn)行了優(yōu)化，實現(xiàn)了交叉率和突變率的非線性自適應(yīng)調(diào)整，提高了算法的尋優(yōu)能力和穩(wěn)定性。 位爬山算法是一種局部搜索算法，

3、有著較強(qiáng)的局部求精能力，適用于基于二進(jìn)制編碼的函數(shù)優(yōu)化和組合問題，由于遺傳算法的宏觀搜索能力大于局部求精能力，所以本文在改進(jìn)的自適應(yīng)遺傳算法后期采用位爬山策略來提高解的精度。 本文根據(jù)改進(jìn)的自適應(yīng)遺傳算法設(shè)計并開發(fā)了序列比對分析程序，并將其應(yīng)用于具體的核酸多序列及蛋白質(zhì)多序列，通過得到的實驗數(shù)據(jù)，將新算法和標(biāo)準(zhǔn)遺傳算法及傳統(tǒng)自適應(yīng)遺傳算法實現(xiàn)的多序列比對算法進(jìn)行了比較和分析，發(fā)現(xiàn)新算法改善了多序列比對的質(zhì)量，提高了算法的穩(wěn)定性。