论文部分内容阅读
序列比对是生物信息学中一项重要的基础性研究课题,它的最基本任务之一是进行多序列比对,多序列比对可用于蛋白质的功能域识别、二级结构预测、基因识别以及分子系统发育分析等方面的研究。由于多序列比对问题是一个NP完全问题,它的求解至今仍是生物信息学中的一个难题。本文提出使用量子粒子群优化算法以及隐马尔可夫模型来解决多序列比对问题。首先分析了空位罚分、替换矩阵和目标函数对序列比对的影响,具体介绍了SP和COFFEE目标函数。对经典的多重序列比对算法:SAGA算法和Clustal算法及隐马尔可夫模型多重序列比对算法进行了研究,对几种算法的性能进行了比较和评估。接着通过对粒子群优化算法的特点进行分析提出了基于二进制粒子群优化算法的多序列比对算法MSA_BPSO(Multiple Sequence Alignment based on Binary Particle Swarm Optimization Algorithm)。然后通过对量子粒子群优化算法与隐马尔可夫模型的分析研究提出了基于隐马尔可夫模型和量子粒子群优化算法的多重序列比对算法MSA_HMM_QPSO(Multiple Sequence Alignment based on Hidden Markov Model and Quantum-behaved Particle Swarm Optimization Algorithm)。以本文提出的算法为基础,利用Microsoft Visual Studio.Net C#2005为开发工具设计并实现了一个基于Windows操作系统的多重序列比对的软件。用基准多序列比对库BAliBASE中的用例对算法进行测试,并与经典多重序列比对方法进行对比分析,结果表明MSA_HMM_QPSO算法在解决蛋白质序列比对问题上是有效的。最后论述了MSA_HMM_QPSO算法在序列分析方面的发展前景。