基于遗传算法的基因表达数据的K_均值聚类分析.pdf

《基于遗传算法的基因表达数据的K_均值聚类分析.pdf》由会员分享，可在线阅读，更多相关《基于遗传算法的基因表达数据的K_均值聚类分析.pdf（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、基于遗传算法的基因表达数据的K-均值聚类分析姜明宇马文丽郑文岭1.上海大学电子生物技术研究中心(上海 200072)2.广州南方医科大学基因工程研究所(广州 510515)【摘要】聚类算法在基因表达数据的分析处理过程中得到日益广泛的应用。本文通过把 K-均值聚类算法引入到遗传算法中,结合基因微阵列的特点,来讨论一种基于遗传算法的 K-均值聚类模型,目的是利用遗传算法的全局性来提高聚类算法找到全局最优的可能性,实验结果证明,该算法可以很好地解决某些基因表达数据的聚类分析问题。【关键词】基因表达数据 K-均值聚类遗传算法On the K-means Clustering of the Gene E

2、xpression Data Basedon Genetic AlgorithmJiang Mingyu Ma Wenli Zheng Wenling1.Bioelectronics Research Center ShangHai University (ShangHai 200072)2.Institute of Genetic Engineering,NanFang Medical University (Guangzhou 510515)【Abstract】Clustering algorithms hava become increasingly important in analy

3、zing and processing gene expressiondata.Considering the characteristics of microarray,the paper discusses a k-means cluster analysismethod based onge-netic algorithm,which takes k-means algorithm into genetic algorithm.It aims at increasing the probability to find glob-al optimum,through trail and t

4、esting,it turns out to be effective to solve some cluser analysis problems of the gene ex-pression data.【Key Words】Gene expression data K-means clustering Genetic algorithm1引言基因芯片是近 10 年来在生命科学领域迅速发展起来的一项高新技术,它将分子生物学和微电子技术相结合,在生命科学与信息科学之间架起一道桥梁,成为后基因组时代基因研究的重要技术之一。基因芯片技术使得人们可以同时监测成千上万个基因的表达水平,对不同发展阶段

5、、组织类型、临床条件及不同有机体的基因表达水平进行监测,从而有助于理解基因功能与协助疾病诊断、确定治疗效果。但是基因芯片实验所产生的大量复杂数据给研究者带来了严峻的挑战。如果没有先进的信息处理方法与工具,人们很难利用基因微阵列技术所产生的大量数据。聚类方法是在基因组学研究领域应用最广泛的技术之一,在众多的聚类算法中,K-均值聚类是一种易于实现且时空复杂度相对较小的方法,然而该算法本质上是一种局部搜索寻优法,它的迭代过程采用了一种所谓的爬山法来寻找最优解。因此该算法极易陷入局部极小值,而得不到全局最优解,特别是在聚类数目较大的情况下,这一问题尤为突出。针对这个问题,本文将 K-均值算法引入到基于

6、自然选择和群体遗传机理的遗传算法的进化中,通过遗传算法来获取全局最优解,而利用 K-均值方法来提高收敛速度。2 K-均值聚类算法及分析K-均值聚类是一种分割聚类法。该算法是一个非常简单但很常用的方法,在进行聚类分析前,首先假定 n 个聚类对象可以分为 k 类,并确定每一类的一个代表,通常成为重心和初始凝聚点,然后将每151上海生物医学工程杂志 2006 年第 27 卷第 3 期一个聚类对象与这些凝聚点进行比较,根据聚类对象与凝聚点的接近程度进行重新归类,将聚类对象归至与其最接近的聚类中心的类别当中,也就是说原先不在一类中的聚类对象也可以同过重新计算而归为一类,而对于一些不能接近所有的初始凝聚点

7、的聚类对象也可以被归为一类,然后再计算每个所得新聚类的聚类凝聚点,不断重复这一过程直到标准测度函数开始收敛为止。算法步骤如下:从 n个数据对象中任意选取 k 个对象作为初始聚类中心;循环下述流程 ,直到每个聚类不再发生变化为止;根据每个聚类对象的均值,计算每个对象与这些中心对象的距离,并根据最小距离重新对相应对象进行划分;重新计算每个聚类的均值。一般可以采用均方差作为标准测度函数,其定义如下:E=ki=1xci x-pi 2其中,x 为代表对象的空间中的一个点,Pi 为聚类 ci 的均值。K-均值算法的计算复杂度为 O(nkt),n、k、t 分别为样本数、类别数和迭代次数,通常 k n,t n

8、,因此 K-均值聚类可应用于数据量较大的情况,这是其优点之一。该算法的关键问题是如何选取初始聚类中心,如果初始分类严重地偏离全局最优分类时,用该算法则可能陷入局部极小值,得到一个局部最优解。另一方面,当聚类数较大时,这种缺点尤为明显,往往要经过多次聚类才能得到一个较满意的结果,甚至得不到满意的结果。3基于遗传算法的K-均值聚类遗传算法模拟自然界的演化进程,采用优胜劣汰的原则,是一种基于自然选择和自然遗传的全局优化算法,用遗传算法对多个个体组成的群体进行操作,通过遗传算子可以使个体间的信息得以交换,这样的群体中的个体一代一代地得以优化,并逐步逼近最优解,这既可以避免用 K-均值聚类算法陷入局部最

9、优解的缺点,又比多次执行 K-均值聚类算法速度快,在遗传 K-均值(Genetic K-Means Al-gorithm)算法中,用 K-means 操作取代了标准遗传算法中的交换操作。采用GKA 对微阵列基因表达数据进行聚类分析的步骤如下:(1)编码方案编码操作和具体要解决的问题紧密相关,因此是极为重要的一个步骤。在基于遗传算法的聚类问题中,通常有两种编码方案。设 n 个 p 维样本要分为 k 类,第一种方法是用 S=(s1,s2,sn)表示解(染色体)的结构,S 为 1n 维的行向量,这里 Si 1,2,k 为第 i 位的等位基因,当 si=k 时表示第i 个样本属于第 k 类,例如,S=

10、(1,2,1,2,2)表明将 5个基因分为 2 类情况,其中第 1、3 个基因属于第 1类,第 2、4、5 个基因属于第 2 类;第二类方法是对聚类中心进行编码,将 k 个表示聚类中心的 p 维向量连接起来。考虑到微阵列数据的高维特性,本文采用第一种方案。(2)初始化群体随机选择出初始群体 p(0),在初始化的过程中,可能会出现某个体中包含空类的情况,例如个体S=(2,2,2,3,3),其中聚类 1 为空类,由于这样的个体并非合法的解,可以采用如下方法进行处理:若某个聚类 Ci 为空,则从离聚类 Ci 最近的非空聚类中取出一个对象,该对象处于距离原聚类中心最远的位置。将该对象放入 Ci 中,重

11、复该过程,直至划分中不再有空的聚类为止。(3)确定适应度函数个体的适应度反映了其存活到下一代所能带来的利益。在遗传 K-均值算法中,目标是最小化误差平方的值,因此,具有较小误差平方值的个体有更高的存活率,并赋以较大的适应度值。个体 S 的适应度函数f(S)定义为:f(S)=11+J其中 J=ni=1kj=1d2为(xi,ci)类内平方误差和,cj为第 j 类的聚类中心。为了避免适应度大的个体过度繁殖,还可以采用遗传算法生态算子中的资源共享策略来对个体的适应度进行调整。主要思想是:在生物界中,由于实行资源共享,才能限制单一物种的无限度增长,从而保持自然界物种的多样性。因此,可将适应度值和个体的数

12、量联系起来,若某个体数量过大,则适当减小其适应度值,使得f(Si)=Cf(Si),0 C 1。(4)选择操作152上海生物医学工程杂志 2006 年第 27 卷第 3 期个体是否被选择依据其适应度的大小,适应度小者的选择概率也较小并可能被淘汰,而适应度大的个体具有较大的选择概率。随机选择的过程采用了旋转轮盘方式进行选择,基本步骤如下:依次累计群体内各个体的适应度,得到相应的累计值 Fi,最后一个为Fn;在0,Fn区间内产生均匀分布的随机数 R;依次用 Fi 与 R进行比较,第一个出现 Fi 大于或等于 R的个体 i 被选出;重复步骤、直至满足所需的个体数目。(5)变异操作GKA中的变异操作与标

13、准遗传算法中变异操作的不同之处在于它是基于距离的,即根据每个样本与各聚类中心的距离对个体中相应位置的值进行改变,使得群体朝着更优的方向进化。对于解空间中的某个体,其每一位都对应一个样本,其值等于样本所属聚类的编号。如果一个样本离某个聚类中心的距离更近,那么个体中对应此样本的位变异为这个聚类编号的概率就大一些。设 d(xi,cj)为样本 xi和聚类中心 cj 之间的欧几里德距离,根据下式所得的概率使等位基因的值发生变异:Pj=Cdmax(xi)-d(xi,cj)+1kj=1Cdmax(xi)-d(xi,cj)+1其中 dmax(xi)为 d(xi,cj)中的最大值,C 是一个常量,可取 1 到

14、2 之间的整数。(6)K-means操作由于任意置定初始条件,并且选择和变异操作都是基于概率的,因此标准遗传算法需要较长时间才能收敛。为了提高收敛速度,我们引入 K-means操作,并最终得到具有最小类内平方误差的最优解S。K-means 操作包括以下两个步骤:计算个体 Si 中每个类的质心;计算每个样本与各质心的距离并将其分配给最近的类,得到 S;(7)保留最优个体将每一代群体中适应度最高的个体存放在一个数组中,当遗传过程结束之后,对这些个体进行比较,将最优个体作为结果输出。4实验结果与分析分析该聚类算法的实际效果需要已知类别的基因表达数据,本文共选取了 130 个已知类别的 YeastCe

15、ll Cycle 基因数据,每个基因表达数据是 76 维的,分别是不同实验条件和时间点的组合。基因根据其RNA 表达水平在细胞周期中达到高峰点的时间可分为5 类,其中包括了 44 个G1 类型,20 个 S 类型,22个 G2 类型,24 个 M 类型和 20 个M/G1 类型,G、S、M 分别代表细胞的生长期(Growth)、合成期(Syn-thesis)和分裂期(Mitosis)。在各阶段的交界处有部分重叠,例如 G1 和S、G2和M。分别用 K-均值算法和 GKA 算法对该数据进行聚类,设定类别数 c=5=0.0001,两种算法的聚类效果比较如下表。从表 1 中可见,GKA 的正确率高于

16、 K-均值算法,说明基于全局搜索的遗传算法在得到全局最优解方面优于基于爬山策略的算法。对于本文中所采用的数据,K-means 的目标函数值为 1805,GKA 的目标函数值为 1770,相差不是很大,但是GKA 的运行时间是 K-means的 225 倍。表 1K-均值与 GKA性能比较表聚类算法K-均值GKA分类准确率65%75%终止时的迭代次数1143运行时间(ms)4710610图 1群体规模对 GKA 性能的影响在实验中,我们对GKA 中两个比较重要的参数群体规模M 和变异概率Pm 在基因表达数据聚类中的影响进行了测试,因为控制参数的选取是否合理,对该算法的收敛速度及结果有很大的影响。

17、153上海生物医学工程杂志 2006 年第 27 卷第 3 期图 2变异概率 Pm 对 GKA 性能的影响将群体进化的总数和变异概率设为 100 和0.05,群体规模M 的影响如图 1 所示。从图中可看出,群体规模直接影响着GKA 的计算效率和进化过程所获得的解得质量。大的群体规模能提供足够的个体数目,使遗传算法进行启发性的搜索,防止其早熟性收敛,但是当群体规模达到150 时,目标函数值得变化已经比较小,而运行时间一直以比较快的速度上升。变异概率是增加群体变化的方法之一,各代中大约发生Pm ML 次(L 为染色体长度)突变操作。我们将群体规模和进化总代数均设为 100,观察变异概率的影响。如图

18、 2 所示,当 Pm=0.05 时,目标函数达到最小值,Pm 继续变大时,算法的随机性增强,又偏离了最优解。4 结束语本文结合基因芯片数据的特点,设计并实现了一种基于遗传算法的 K-均值模型 GKA,在一个大的范围内找到 K 值,加快收敛并避免陷入局部最优,使聚类的结果达到类内距最小、类间距最大,通过对一些有代表性的数据的实验表明这种方法是有效的,为基因微阵列的知识发现提供了有效的手段。参考文献1 马文丽,郑文岭.DNA 芯片的方法与应用M.广州:广东科技出版社,20022玄光男,程润伟.遗传算法与工程优化 M.北京:清华大学出版社.20043 王富刚,陈先农.基因芯片数据的聚类分析 J.国外

19、医学生物医学工程分册,2004.4,27(2):98-1014 AZUAJE F.Clustering-based approaches to discov-ering and visualizing microarray data patterns.Briefin-gs in Bioinformatics,2003,.4(1):31-425 S.T.SPELLMAN.Comprehensive Identification ofCell Cycle-regulated Genes of the Yeast Saccha-romyces cerevisiae by Microarray Hyb

20、ridization J.Molecular Biology of the Cell.1998,9:3273-32976 K.KRISHNA,M.NARASIMHA MUTY.Genetic-Means Algorithm J.IEEE TRANSACCTIONS ON-SYSTEMS,MAN,AND CYBERNETICS-PATR.B:CYBERNERICS,1999.6,29(3)(收稿日期:2006-05-17)手表式药物释放装置美国Chrono 治疗仪器公司新近推出一种唤做 ChronoDose 的手表式新颖药物释放装置,它可程控,无论在病人睡着或醒着时,均可在一日的不同时间以不同剂量自动地将药物施入人体。当统计出疾病症状极差时,即可程控此装置释放药物,以提高治疗效果。该装置用于治疗心脏疾病、忧郁症、哮喘、关节炎和高血压时,尤为有效。154上海生物医学工程杂志 2006 年第 27 卷第 3 期