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

《上海生物医学工程》杂志2006年第27卷第3期·151·

基于遗传算法的基因表达数据的K-均值聚类分析

姜明宇马文丽郑文岭
1.上海大学电子生物技术研究中心(上海200072)
2.广州南方医科大学基因工程研究所(广州510515)

【摘要】聚类算法在基因表达数据的分析处理过程中得到日益广泛的应用。本文通过把K-均值聚类
算法引入到遗传算法中,结合基因微阵列的特点,来讨论一种基于遗传算法的K-均值聚类模型,目的是利
用遗传算法的全局性来提高聚类算法找到全局最优的可能性,实验结果证明,该算法可以很好地解决某些基
因表达数据的聚类分析问题。
【关键词】基因表达数据K-均值聚类遗传算法

OntheK-meansClusteringoftheGeneExpressionDataBased
onGeneticAlgorithm
JiangMingyuMaWenliZhengWenling
1.BioelectronicsResearchCenterShangHaiUniversity(ShangHai200072)
2.InstituteofGeneticEngineering,NanFangMedicalUniversity(Guangzhou510515)

【Abstract】Clusteringalgorithmshavabecomeincreasinglyimportantinanalyzingandprocessinggeneexpression
data.Consideringthecharacteristicsofmicroarray,thepaperdiscussesak-meansclusteranalysismethodbasedonge-
neticalgorithm,whichtakesk-meansalgorithmintogeneticalgorithm.Itaimsatincreasingtheprobabilitytofindglob-
aloptimum,throughtrailandtesting,itturnsouttobeeffectivetosolvesomecluseranalysisproblemsofthegeneex-
pressiondata.
【KeyWords】GeneexpressiondataK-meansclusteringGeneticalgorithm

1引言是一种易于实现且时空复杂度相对较小的方法,然
基因芯片是近10年来在生命科学领域迅速发而该算法本质上是一种局部搜索寻优法,它的迭代
展起来的一项高新技术,它将分子生物学和微电子过程采用了一种所谓的爬山法来寻找最优解。因此
技术相结合,在生命科学与信息科学之间架起一道该算法极易陷入局部极小值,而得不到全局最优解,
桥梁,成为后基因组时代基因研究的重要技术之一。特别是在聚类数目较大的情况下,这一问题尤为突
基因芯片技术使得人们可以同时监测成千上万个基出。针对这个问题,本文将K-均值算法引入到基
因的表达水平,对不同发展阶段、组织类型、临床条于自然选择和群体遗传机理的遗传算法的进化中,
件及不同有机体的基因表达水平进行监测,从而有通过遗传算法来获取全局最优解,而利用K-均值
助于理解基因功能与协助疾病诊断、确定治疗效果。方法来提高收敛速度。
但是基因芯片实验所产生的大量复杂数据给研究者2K-均值聚类算法及分析
带来了严峻的挑战。如果没有先进的信息处理方法K-均值聚类是一种分割聚类法。该算法是一
与工具,人们很难利用基因微阵列技术所产生的大个非常简单但很常用的方法,在进行聚类分析前,首
量数据。聚类方法是在基因组学研究领域应用最广先假定n个聚类对象可以分为k类,并确定每一类
泛的技术之一,在众多的聚类算法中,K-均值聚类的一个代表,通常成为重心和初始凝聚点,然后将每
·152·《上海生物医学工程》杂志2006年第27卷第3期

一个聚类对象与这些凝聚点进行比较,根据聚类对数据进行聚类分析的步骤如下:
象与凝聚点的接近程度进行重新归类,将聚类对象(1)编码方案
归至与其最接近的聚类中心的类别当中,也就是说编码操作和具体要解决的问题紧密相关,因此
原先不在一类中的聚类对象也可以同过重新计算而是极为重要的一个步骤。在基于遗传算法的聚类问
归为一类,而对于一些不能接近所有的初始凝聚点题中,通常有两种编码方案。设n个p维样本要分
的聚类对象也可以被归为一类,然后再计算每个所为k类,第一种方法是用S=(s1,s2,…,sn)表示解
得新聚类的聚类凝聚点,不断重复这一过程直到标(染色体)的结构,S为1＊n维的行向量,这里Si
准测度函数开始收敛为止。算法步骤如下:①从n{1,2,…,k}为第i位的等位基因,当si=k时表示