论文部分内容阅读
将不同物种、不同进化水平的生物的相关序列进行比较分析,以发现生物序列中功能、结构等信息,是生物信息学研究的主要内容。序列比较的最基本操作就是比对。目前对双序列比对算法的研究已经很成熟了,而现有的多序列比对算法多是基于一个数学模型或生物模型,不能保证所给出的比对结果是最优的,而只是一个近似值。所以目前研究既高效又准确的多序列比对算法仍是一个热点和难点。本文基于智能化算法在处理多序列比对问题上具有的高效性能,提出一种基于进化思想的粒子群优化算法与隐马尔可夫模型相结合的多序列比对算法。本文首先介绍了序列比对的基础,分析了序列比对中空位罚分、替换矩阵对比对结果的影响。说明了多序列比对的定义和序列比对结果的评价模型SP模型,引入了当前比较流行的两类算法渐进比对算法和迭代比对算法,阐述了被公认为最经典的Clustalw算法的原理。在此基础上引入了智能化算法隐马尔可夫模型,阐述了隐马尔可夫模型的三个基本问题和解决的算法。在对多序列比对的隐马尔可夫模型进行研究之后,给出了基于隐马尔可夫模型解决多序列比对问题的算法流程。然后研究了基于隐马尔可夫模型解决多序列比对问题的不足之处。鉴于隐马尔可夫模型本身需要对大量相似序列进行训练,对训练问题的Baum-Welch算法会以较大的迭代步幅收敛于不甚理想的局部极小值,本文引入了粒子群优化算法来优化隐马尔可夫模型的训练问题。粒子群优化算法是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。接着对粒子群优化算法在解决隐马尔可夫模型训练问题上的不足进行研究,阐述了粒子群优化算法中普遍存在的“早熟”现象。粒子群在搜索的过程当中,可能会陷入局部最优但却不是全局最优值的问题。为了解决这个问题,本文基于进化论的思想,改进了粒子群优化算法,如果发现某个粒子在搜索过程中陷入局部最优,则将该粒子淘汰,并填补进新的搜索能力更强的粒子,继续进行全局搜索,确保搜索的全局优化性,克服“早熟”现象。最后给出了基于进化思想的粒子群优化算法与隐马尔可夫模型解决多序列比对问题的算法流程。通过对BAliBASE2.0参考比对库中测试数据的模拟实验,验证了改进过后的算法要优于Baum-Welch算法,在解决多序列比对问题上是行之有效的。