GPU加速的并行模拟退火算法及其在蛋白质结构预测中的应用

摘要

蛋白质结构预测（Protein Structure Prediction,PSP）是生物信息学中重要的研究课题。从头预测法是一种常见的用于PSP的计算方法。它主要根据蛋白质的天然构象处于自由能最低状态的理论，抽象出蛋白质结构模型，直接根据蛋白质的氨基酸序列求解出蛋白质结构。本文将依据从头预测法，采用广泛被使用的AB非格点模型来预测蛋白质的二维结构。　　基于AB非格点模型的PSP问题实际上就是求解对应能量函数极小值的过程，属于函数优化范畴。不同的是，PSP模型对应的能量函数具有大量的局部极小值和很高的计算复杂性，对寻优算法的性能要求较高。使用不同采样策略的多agent模拟退火（Multi-agent Simulated Annealing,MSA）算法克服了经典模拟退火算法收敛速度慢的缺点，能够有效地提升模拟退火算法的性能。本文借鉴了MSA的改进思路，将教与学优化算法中“Learner Phase”用到的变异方式作为MSA的采样策略，得到了基于教与学优化算法的MSA（MSATLBO）算法。本文在13个标准测试函数、4条人工系列和4条真实系列上对MSA算法的不同采样方式进行了比较，结果表明，尽管没有一种采样方式在所有问题上都优于其他方式，但对PSP问题，基于粒子群优化算法的采样方式整体性能最佳。　　考虑到MSA在求解PSP问题时需要消耗大量的计算时间，本文使用CUDA编程模型在GPU上实现了MSA（CUMSA），比较了两种并行方式对应的性能差异，同时讨论了Agent个数与迭代次数，对CUMSA的性能影响，实验证明，通过GPU加速的MSA能够大量地减少算法的执行时间。值得注意的是，应该根据GPU的硬件特征合理的分配Agent个数，以平衡CUMSA的求解精度和速度。

目录

封面

声明

目录

中文摘要

英文摘要

第一章 绪论

1.1 背景及意义

1.2 国内外研究现状

1.3 研究内容与结构安排

第二章 蛋白质结构预测

2.1 蛋白质结构

2.2 蛋白质结构预测方法

2.3 蛋白质折叠结构预测模型

2.4 本章小结

第三章 GPU计算与CUDA

3.1 并行计算

3.2 GPU计算

3.3 CUDA概述

3.4 本章小结

第四章 并行模拟退火算法的比较与分析

4.1 模拟退火算法

4.2 并行模拟退火算法

4.3 实验与结果分析

4.4 本章小结

第五章 GPU加速的并行模拟退火算法

5.1 设计思路

5.2 实现细节

5.3 实验与结果分析

5.4 本章小结

第六章 总结与展望

6.1 工作总结

6.2 展望

参考文献

附录 攻读硕士学位期间发表的论文

致谢