论文部分内容阅读
蛋白质组研究是后基因组计划中一个非常重要的内容,同时也是生物信息学领域中极具挑战性的课题之一。蛋白质的生物学功能在很大程度上由其空间结构决定,所以蛋白质结构预测(Protein Structure Prediction, PSP)是了解蛋白质功能的一个重要途径。随着蛋白质工程技术的不断发展,已知的蛋白质序列数据远远超过蛋白质空间结构数据,而通过实验测定蛋白质空间结构的速度远远小于测定其氨基酸序列的速度,这使得从理论上对已知序列的蛋白质进行空间结构上的预测这一课题变得日益紧迫和重要。由于预测真实蛋白质结构的复杂性太高,本文研究基于一种简单而有效的非格点模型,AB模型。由于基于AB模型的PSP问题是NP困难的,设计高效的全局优化算法就成为求解该问题的关键。基于粒子群优化(Particle SwarmOptimization, PSO)算法的多agent模拟退火算法(Multi-agent SimulatedAnnealing, MSA)是一种基于种群的优化算法,它采用PSO算法的运动方程进行采样,能有效地解决传统SA算法收敛速度慢和并行效率取决于所求解问题的可并行性的不足,本文主要研究了PSP问题的MSA算法及其并行化,主要内容包括:根据MSA算法和AB模型的特点,提出了三种反向学习的策略:反向速度学习(Opposite Velocity Based Learning, OVBL)、反向角度学习(Opposite AngleBased Learning, OABL)和反向旋转学习(Opposite Rotation Based Learning,ORBL),以提高算法的全局搜索能力,避免陷入局部最优解。分别对四条长Fibonacci测试序列、四条较短和两条较长真实蛋白质序列进行结构预测。结果表明这三种反向学习的策略都能增强算法的全局寻优能力,有效改进MSA算法的性能,其中ORBL策略最好,OVBL次之,OABL最差。研究了MSA算法在多核处理器和Cluster环境下的并行,仿真结果表明在多核处理器环境下,并行MSA算法的加速比接近于核的数量,在集群环境下,问题规模越大,加速比越高,蛋白质序列长时可以接近达到线性加速比。研究了具有不同邻域拓扑结构的并行MSA算法,将环形3邻域、环形5邻域、网格5邻域和网格9邻域这四种经典的邻域结构应用于基于ORBL策略的MSA算法。仿真结果表明在较短的序列中四种经典邻域结构的并行MSA算法和全局版的MSA算法的性能相当,都能得到较优的能量值和构象;在较长的序列中采用邻域结构的并行MSA算法略优与全局版的MSA算法。