蛋白質(zhì)結(jié)構(gòu)預(yù)測的并行模擬退火算法研究.pdf

1、蛋白質(zhì)組研究是后基因組計劃中一個非常重要的內(nèi)容，同時也是生物信息學(xué)領(lǐng)域中極具挑戰(zhàn)性的課題之一。蛋白質(zhì)的生物學(xué)功能在很大程度上由其空間結(jié)構(gòu)決定，所以蛋白質(zhì)結(jié)構(gòu)預(yù)測（Protein Structure Prediction, PSP）是了解蛋白質(zhì)功能的一個重要途徑。隨著蛋白質(zhì)工程技術(shù)的不斷發(fā)展,已知的蛋白質(zhì)序列數(shù)據(jù)遠(yuǎn)遠(yuǎn)超過蛋白質(zhì)空間結(jié)構(gòu)數(shù)據(jù)，而通過實驗測定蛋白質(zhì)空間結(jié)構(gòu)的速度遠(yuǎn)遠(yuǎn)小于測定其氨基酸序列的速度，這使得從理論上對已知序列的蛋白質(zhì)進(jìn)

2、行空間結(jié)構(gòu)上的預(yù)測這一課題變得日益緊迫和重要。
　　由于預(yù)測真實蛋白質(zhì)結(jié)構(gòu)的復(fù)雜性太高，本文研究基于一種簡單而有效的非格點模型，AB模型。由于基于AB模型的PSP問題是NP困難的，設(shè)計高效的全局優(yōu)化算法就成為求解該問題的關(guān)鍵。基于粒子群優(yōu)化（Particle Swarm Optimization, PSO）算法的多agent模擬退火算法（Multi-agent Simulated Annealing, MSA）是一種基于種群的優(yōu)化

3、算法，它采用PSO算法的運動方程進(jìn)行采樣，能有效地解決傳統(tǒng)SA算法收斂速度慢和并行效率取決于所求解問題的可并行性的不足，本文主要研究了PSP問題的MSA算法及其并行化，主要內(nèi)容包括：
　　根據(jù)MSA算法和AB模型的特點，提出了三種反向?qū)W習(xí)的策略：反向速度學(xué)習(xí)（Opposite Velocity Based Learning, OVBL）、反向角度學(xué)習(xí)（Opposite Angle Based Learning, OABL）和反向旋

4、轉(zhuǎn)學(xué)習(xí)（Opposite Rotation Based Learning, ORBL），以提高算法的全局搜索能力，避免陷入局部最優(yōu)解。分別對四條長Fibonacci測試序列、四條較短和兩條較長真實蛋白質(zhì)序列進(jìn)行結(jié)構(gòu)預(yù)測。結(jié)果表明這三種反向?qū)W習(xí)的策略都能增強(qiáng)算法的全局尋優(yōu)能力，有效改進(jìn) MSA算法的性能，其中ORBL策略最好，OVBL次之，OABL最差。
　　研究了MSA算法在多核處理器和Cluster環(huán)境下的并行，仿真結(jié)果表明在多

5、核處理器環(huán)境下，并行MSA算法的加速比接近于核的數(shù)量，在集群環(huán)境下，問題規(guī)模越大，加速比越高，蛋白質(zhì)序列長時可以接近達(dá)到線性加速比。
　　研究了具有不同鄰域拓?fù)浣Y(jié)構(gòu)的并行MSA算法，將環(huán)形3鄰域、環(huán)形5鄰域、網(wǎng)格5鄰域和網(wǎng)格9鄰域這四種經(jīng)典的鄰域結(jié)構(gòu)應(yīng)用于基于ORBL策略的MSA算法。仿真結(jié)果表明在較短的序列中四種經(jīng)典鄰域結(jié)構(gòu)的并行MSA算法和全局版的MSA算法的性能相當(dāng)，都能得到較優(yōu)的能量值和構(gòu)象；在較長的序列中采用鄰域結(jié)構(gòu)的并