论文部分内容阅读
生物信息学是一门运用数学和计算机科学等手段对海量的生物信息进行分析和研究的交叉学科。序列比对是当前生物信息学一个研究的热点。它对于发现生物序列中的结构、功能和进化信息具有非常重要的意义。本文首先介绍了与序列比对相关的理论知识及常用的序列比对算法,重点介绍了基于动态规划思想的N-W和S-W算法以及两种启发式算法BlAST和FASTA。动态规划算法用于序列比对能够得到精确的结果,但其算法效率不高。而启发式的算法并不能保证找到最佳比对。蚁群算法具有正反馈、通用性、鲁棒性等优点,能够在正反馈的机制下快速收敛,并具有寻找到最优解的能力,目前已成功运用于TSP问题。鉴于TSP问题与序列比对问题有相似之处,本文将蚁群算法加以修改运用到序列比对中。首先建立了基于蚁群算法的双序列比对模型,设计并实现了标准的蚁群比对算法,并通过实验验证了蚂蚁的正反馈机制发挥了作用,运用蚁群比对算法能够较快的得到最优解。但是蚁群算法有其本身的缺陷,易于陷于局部最优解,出现“早熟”现象。为了解决这一问题,我们分析了影响蚁群比对算法性能的因素,发现可以从三方面对蚁群比对算法进行改进。针对序列比对的特点,在信息素增量系数和信息素更新机制上进行改进。在基于排序的蚁群系统的基础上提出Rank-Base AS比对算法,该算法使用局部信息更新机制,在迭代初期降低了信息素的对路径选择的影响程度,使蚂蚁能够有更多的路径选择,从而扩大了搜索空间,增加了寻找到更优解的机会,避免了陷入局部最优解。同时为了加快算法收敛,对N条最优路径进行排序,增强其信息素的浓度,从而使得算法在迭代后期能够较快的收敛于最优解,一定程度上减少了算法搜索的时间,提高了算法的效率。经实验证明,这种改进的算法能够搜索到最优比对的概率更大。由于蚁群算法的通用性,它可以和其他的一些进化算法相结合从而取得更好的比对结果。另外,由于蚁群算法的并行性,和文化算法双演化双促进的并行机制有相似之处。因此,最后我们引入了文化算法,拟找出一种解决序列比对问题的新思路。首先介绍了文化算法的原理、特点,文化算法的框架及其与传统进化算法的不同之处。找到文化算法与蚁群算法的结合点,进而构造一种文化蚁群算法的序列比对模型,在蚁群优化算法ACS的基本框架中增加了并行演化的信仰空间。信仰空间对当前最优解进行优化操作,将所得的结果通过影响函数动态完成群体空间的全局信息素更新。从理论上来讲,在算法的效率上,并行化的操作要比串行操作有很大的提高。本文对文化算法的群体空间、信念空间、接受函数、影响函数进行了设计,构造了群体空间和信念空间并行演化机制,描述了算法的基本流程,最后分析了算法的可行性。