一種改進的自適應遺傳算法在多序列比對中的應用.pdf

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

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

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