论文部分内容阅读
随着生物信息学的发展,特别是进入后基因时代,基因芯片技术得到了越来越广泛的应用,这直接导致了基因表达数据的大量积累,而如何从海量的基因表达数据中提取出有意义的生物学信息己成为当前生物信息学研究的热点。聚类分析是生物信息学的主要分析工具之一,能将表达模式相似的基因聚集在一起,根据已知基因的功能可以推断出未知基因的功能。本文对基因表达数据的聚类分析进行研究,介绍生物信息学中常用的聚类算法,分析其各自的特点,根据已有的算法提出本文的改进算法。粒子群优化算法(Particle Swarm Optimization,PSO)源于对鸟类群体行为的研究,是一种全局优化算法,算法简单,搜索速度快。本文在深入研究PSO算法的基础上,将其应用在基因表达数据的聚类分析中。在PSO与K-means混合算法的基础上,对算法进行改进,虽然混合后的算法PSOK-means增强了算法的收敛速度,但依然存在两个问题:PSO算法的早熟问题和聚类的K值问题。针对这两个问题,本文提出了如下改进算法:(1)算法早熟问题。对于早熟问题,本文提出了一种双扰动的粒子群聚类算法——DDPSOK-means,改进思想是检测算法的收敛时机,若算法收敛,则进行惯性权重和极值的双扰动,使粒子能跳出局部最优的状态,从而再次进行全局搜索,直到多次扰动算法不再进化为止。惯性权重采用非线性的惯性权重策略,而扰动时采用随机的惯性权重策略。搜索时采用非线性的惯性权重策略能增强算法的搜索能力,因为非线性权重策略能平衡算法的搜索过程;扰动时采用随机的惯性权重策略,能增强粒子的多样性,使粒子能进行全局搜索。同时采用极值扰动的方式,对粒子的个体极值进行扰动,进一步改变粒子的速度和方向,增强了粒子跳出局部最优解的能力。(2)聚类K值问题,即算法聚类数目需要预先给出,不能在聚类过程中自适应调整。K值问题在聚类研究中一直是一个重要的研究方向,因为K值选取的好坏严重影响到聚类结果的好坏,不同的K值将导致结果差别非常大。本文对适应度函数与K值的关系进行研究,发现适应度函数值随K值的增大而减小,并且减小的速率在标准K值处突然减小,利用这个规律,提出变化率公式对拐点进行捕捉,最后在DDPSOK-means的基础上提出了自适应K值的粒子群聚类算法。针对粒子群易陷入局部最优解问题和聚类的K值问题,本文提出了上面的两种改进方法,最后采用四组基因表达数据对改进的算法分别进行了验证,实验结果验证了改进算法的有效性。