（动物遗传育种与繁殖专业论文）基于遗传算法的基因芯片数据聚类研究.pdf

中文摘要 近年来基因芯片技术被广泛应用于生命科学及相关的各个领域，它推动了生 物学研究的发展。基因表达的模式可以提供有关细胞状态的重要信息，基因芯片 技术可以用一个样本同时测量数千个基因的表达情况。 聚类分析技术在分析基因芯片表达数据中扮演了重要的角色。在基因表达数 据聚类分析中，使用不同的参数，得到的类结构可能显著不同，k m e a n s 算法应用 较为广泛。本文首先以k - m e a n s 算法为基准，对常见的两种类型的基因芯片数据适 用的预处理方式和相似度选取进行了研究和分析，结果显示：对于时间序列数据 集，对数化转换后，相似度选择协方差所得结果最好；对于非时间序列数据集， 对数转化最好，相似度选取欧氏距离、平方欧氏距离、马氏距离都比较好。 由于k m e a n s 算法对于初始值非常敏感且易陷入局部极小值，而遗传算法是一 种通过模拟自然进化过程搜索最优解的算法，它具有隐含并行性和对全局信息的 有效利用能力，将两者结合产生了基于遗传算法的k - m e a n s 聚类算法g k a 算法， 它既能够发挥遗传算法的全局寻优能力，又能兼顾k - m e a n s 算法的局部搜索能力， 更好地解决聚类问题。本文结合参数研究结果，并将自然进化中的优选思想进一 步引入g k a 算法，提出了新的基于遗传算法的k - m e a n s 聚类算法一i l 认算法。 将该算法应用于酵母基因表达数据集研究，结果显示i k g a 算法极显著( p o 0 1 ) 的优于g k a 算法和k m e a n s 算法。 最后将该i k g a 算法应用于猪基因表达数据的聚类分析中，结果显示，该算 法能很好地避免了初始值对聚类结果的影响，使t w c v 值降低，得到了较好的聚 类结果。 关键词：基因表达数据；聚类分析；k - m e a l l s 算法；遗传算法 c l u s t e r i n gb a s e do ng e n e t i ca l g o r i t h mf o rg e n e e x p r e s s i o nd a t a l i ut i a n - f e i ( a n i m a lg e n e t i c sa n db r e e d i n g & r e p r o d u c t i o n ) d i r e c t e db yp r o f l ix u e w e i ( c o l l e g eo fa n i m a ls c i e n c ea n dt e c h n o l o g y , s i c h u a na g r i c u l t u r a lu n i v e r s i t y , y a a n ，s i c h u a n ，6 2 5 0 14 ) a b s t r a c t i l lr e c e n ty e a r s ，c l u s t e r i n ga l g o r i t h m sh a v eb e e ne f f e c t i v e l ya p p l i e di nm o l e c u l a r b i o l o g yf o rg e n ee x p r e s s i o nd a t aa n a l y s i sw i t ht h ea d v a n c e m e n ti nm i c r o a r r a y t e c h n o l o g y , i ti sn o wp o s s i b l et oo b s e r v et h ee x p r e s s i o nl e v e l so ft h o u s a n d so fg e n e s s i m u l t a n e o u s l yw h e nt h ec e l l sw e r ee x p e r i e n c i n gs p e c i f i cc o n d i t i o n so ru n d e r g o i n g s p e c i f i cp r o c e s s e s c l u s t e r i n gi sak e ys t e pi nt h ea n a l y s i so fg e n ee x p r e s s i o nd a t a k - m e a n sa l g o r i t h m i st h em o s tw i d es p r e a dm e t h o di nc l u s t e ra n a l y s i s w es t u d i e dt h ee f f e c t so fd i f f e r e n t m e a s u r i n gm e t r i c sa n dd a t ap r e p r o c e s s i n gf o rd i f f e r e n tg e n ee x p r e s s i o nd a t ao nk - m e a n s c l u s t e r i n g t h er e s u l t ss h o w e dt h a td i f f e r e n td a t ap r e p r o c e s s i n gw a y sm a d es i g n i f i c a n t d i f f e r e n c e su n d e rd i f f e r e n tm e a s u r i n gm e t r i c s t h eb e s td a t ap r e p r o c e s s i n gi nk m e a n s c l u s t e r i n gi st os e l e c tl o gt r a n s f o r m a t i o n sf o rt h et i m e c o u r s eg e n ee x p r e s s i o nd a t a s e t ， a n dm e a s u r i n gm e t r i c si st os e l e c tc o v a r i a n c em e t r i c s h o w e v e r ，t h eb e s td a t a p r e p r o c e s s i n gw a yi sl o gt r a n s f o r m a t i o n sf o ro t h e rd a t a s e t s ，t h r e em e a s u r i n gm e t r i c s l e a d st ob e r c rr e s u l t s t h ev i t a ls h o r t c o m i n go fk m e a n sa l g o r i t h mi st h es e n s i b i l i t yt ot h ei n i t i a lv a l u e ， i ti se a s yt on l l li n t oal o c a lo p t i m u m g e n e t i ca l g o r i t h mi sam e t h o do f s e a r c h i n gf o r b e s ts o l u t i o nb yi m i t a t i n gn a t u r a le v o l u t i o n ，i t sn o t a b l ef e a t u r e sa r ei m p l i c i tp a r a l l e l i s m a n dc a p a c i t yo fu s i n ge f f e c t i v eg l o b a l i n f o r m a t i o n ，s oan e wk - m e a n sc l u s t e r i n g a l g o r i t h mb a s e do ng e n e t i ca l g o r i t h m ( g k a ) w a sp r o p o s e d i th a dg o o dg l o b a la n d l o c a ls e a r c hc a p a b i l i t y i tw a st h ei n t e g r a t i o no fk - m e a n sa l g o r i t h ma n dg e n e t i c a l g o r i t h m ( i k g a ) t e s t e db yt h et h r e ey e a s td a t a s e t s ，i tp r o v e dt h a ti k g aw a sb e r e r t h a ng k a a tt h es 姗et i m e ，w eu s e di k g at or e s e a r c ht h ep i gg e n ee x p r e s s i o nd a t a t h e r e s u l t sa l s os h o w e dt h a ti k g aw a sm o r ee f f e c t i v eo na v o i d i n gt h ei n f l u e n c eo ft h e i n i t i a lv a l u et ot h ec l u s t e r i n ga n dr e d u c i n gt h ev a l u eo ft w c v k e y w o r d s ：g e n ee x p r e s s i o nd a t a ；c l u s t e r i n ga n a l y s i s ；k m e a n s ，a l g o r i t h m ； g e n e t i ca l g o r i t h m 论文独创性声明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行研究工作所取得的 成果。尽我所知，除了文中特别加以标注和致谢的地方外，学位论文中不包含其他 个人或集体已经发表或撰写过的研究成果，也不包含为获得四川农业大学或其它教 育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示了谢意。 研究生签名：捌毛u 扣孑年f 月7 日 关于论文使用授权的声明 本人完全了解四川农业大学有关保留、使用学位论文的规定，即：学校有权保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同意四川农业大学可 以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 研究生签名： 导师签名： 一2 年f 月j 7 日 一膊钿岁日 1 1 引言 基因芯片数据聚类分析 基因芯片技术是2 0 世纪9 0 年代发展起来的一项前沿生物技术。它随着人类 基因组计划的启动和实施应运而生，宅为各种生物的基因功能分析乃至生物学研 究提供了一个十分理想的技术平刽1 1 。1 9 9 8 年，( s c i e n c e 杂志把基因芯片技术 列为年度十大科技突破之一。近十多年来，以其无可比拟的高信息量、高通量、 灵敏、快速、准确等特点，它在生物学和医学基础研究及科研中表现出很强的优 势，成为各国学术界和工业界所关注并研究的热点，它被公认为将会给2 1 世纪的 生命科学研究带来一场革命。 基因芯片技术能对大量的基因表达谱进行同步、快速测量，同时提供成千上 万条基因的表达水平【2 ，3 1 ，随着小鼠、果蝇、线虫等模式生物和人类基因组测序的 完成，人类基因组计划进入后基因组时代，如何从海量的基因芯片数据中发掘成 千上万基因的功能，研究基因在生命过程中所担负的重要角色，成为基因组时代 特别是后基因组时代所面临的重要课题。 对基因芯片数据分析的目的是从表达谱矩阵中提取隐藏的信息，分析基因表 达谱可以得出基因调节和相互作用的机制，如基因功能、发育、癌症、衰老和药 理等【4 。10 1 。 聚类分析是基因芯片数据处理中最关键的分析方法之一，通过对基因表达数 据的聚类分析可以获取基因功能和基因表达调控等重要信息，对基因芯片聚类技 术的研究是生命科学和计算机科学的重要课题之一。 _ l 。2 基因表达数据分析 1 2 1 基因表达矩阵 基因表达数据分析的对象是在不同实验条件下，全部或部分基因的表达数据 所构成的矩阵。单次微阵列实验能获得细胞在某一实验条件下的全基因组表达数 据，包含成千上万条基因在细胞中的相对或绝对丰度，不同实验条件的全基因组 表达数据就构成了个，l 聊的数据矩阵m = ( 彬，j ) ，如图1 所示i i l l 。因此，基因 表达数据又常称为基因表达矩阵。在基因表达矩阵中，行表示基因，列表示实验 样品，如不同组织、实验条件或处理因素等，每个格子的数值表示特定的基因在 特定样品中的表达水平。图1 1 中，形，= 1 ，n ；j = l ，m ) 表示第f 条基因在第 - ，个样品中的表达水平( 一般是比率值，即r a t i o 值) ，行向量g f = ( 形1 ，形，。) 代表 第f 条基因在m 个样品中的表达水平，称为基因f 的表达谱，列向量 巧= ( 彤，峨，) 代表在第个样品中所有基因的表达水平，相应地称为样品的 表达谱。 12 w 历 w 2 2m w n m2 m 图1 基因表达矩阵示意图 f i g 1ag e n ee x p r e s s i o nd a t am a t r i x 1 2 2 基因表达数据预处理 对基因表达数据进行聚类、模式识别等分析之前，往往需要进行预处理，包 括对丢失数据进行填补、清除不完整的数据或合并重复数据等数据清洗过程，并 根据分析目的进行数据筛选过滤，以及针对分析方法选择合适的数据转换方法等。 数据筛选过滤是数据分析前必须进行的一个步骤，其目的是去除表达水平是 负值或很小的数据，或者含有明显噪声的数据( 单个异常大或小的峰或谷信号) ， 同时处理缺失数据。在d n a 微阵列实验中直接获得的是芯片的扫描图像，每个 点的信号强度是前景信号减去背景信号，因此有时会出现负值或很小的值，这些 负值或很小的值是没有生物学意义的。数据的缺失对于某些后续数据分析方法( 如 k m e a n s 聚类) 来说有着非常大的影响，甚至是致命性的，必须采取相应的方法来 对它们进行处理【1 2 _ 1 8 】，如a dh o c 法，多重填补法( m i ) ，期望最大化法( e m ) ，加 权回归法等【i 叽2 2 】。不管使用哪种方法，进行何类分析，选择富含信息的基因是降 2 低数据的复杂性、提高信噪比的第一步【2 3 1 。 基因表达数据经过筛选，在进行聚类分析等操作前，往往还需要进行数据转 换。数据转换是将数据变换为适合于挖掘的形式，可以根据需要构造出新的数据 属性以帮助理解、分析数据的特点，或者将数据规范化，使之落在一个特定的数 据区间中。数据转换通常包括对数转换和标准化两个过程【2 4 1 。 1 3 聚类分析 基因芯片数据上的聚类分析对于理解基因功能、基因调控、细胞的生物学过 程和细胞的子类型都很有帮助。通过聚类分析，那些具有相似表达模式的基因聚 在一起并表现出相似的细胞功能。此外，对样本的聚类可以揭示子细胞的类型， 而利用传统的基于形态学的方法是很难做到这点的【l l 】。 聚类的基本思想是在多元变量间定义距离或相似系数，并用来确定各个多元 变量的关系。在基因表达谱分析中，多元变量就是基因向量( 表达矩阵中的行) 和 样本向量( 表达矩阵中的列) 。通过聚类可以得到一组或多组共表达的基因，在每 一个组内，基因的表达谱非常类似，具有相似的表达模式。此外，通过样本聚类， 还可以发现样本间的类型关系，或者发现新的样本类型。 聚类分析涉及两个方面：相似度的定义和聚类方法。聚类分析中常用的相似 度有欧氏距离、p e a r s o n 相关系数、m i n k o w i s k i 距离、h a m m i n g 距离、马氏距离 等，目前基因芯片数据的聚类分析中用得最为普遍的是欧氏距离和p e a r s o n 相关 系数。 1 3 1 常用相似度 对微阵列数据进行聚类分析之前，必须首先确定反映不同微阵列数据相似程 度的度量函数，根据该函数可以将相似程度高的基因分为一类。计算一对个体间 的相似性或离散度的测量称为相似性度量，简称相似度。定义相似度是数据分析 的关键，它可以在很大程度上影响聚类算法的输出。在实际计算中，相似性度量 被转化为两组微阵列数据之间的距离。距离越小，表达模式越相近；反之，则表 达模式差异大。假设两个微阵列数据分别为x = ( 而，恐9o * o ，) 和y = ( y j ，咒，虼) ， 距离函数d ( x ，y ) ，它们必须满足如下条件： 4 d ( x ，y ) 0 d ( x ，】，) = d ( r ，x ) d ( x ，y ) = o ，i f x = y d ( x ，y ) d ( x ，z ) + d ( z ，n 以下介绍了常见的相似度的定义。 ( 1 )欧氏距离( e u c ii d e a nd is t a n c e ) 两个n 维向量x = “，f - 1 ，。，刀) 和】，：“，i ：1 ，刀 间的欧氏距离的定义： d ( 训) ：厄五万i 面i 而= 主( 一咒) 2 ( 1 - 2 ) yi = 1 ( 2 )平方欧氏距离( s e q u a r e de u c ii d e a nd is t a n c e ) 两个n 维向量平方欧氏距离的定义： d ( x ，y ) = ( 一乃) 2 + ( 屯一蜴) 2 + + ( 毛一虬) 2 = ( 五一只) 2 ( 1 - 3 ) i = i ( 3 )马氏距离( m a n h a t t a nd is t a n c e ) 马氏距离又称c i t y - b l o c k 距离，两个n 维向量马氏距离的定义： d ( x ，y ) = i 而一y li + lx 2 一i + + i 毛一只i - l 五一咒i ( 1 4 ) t = l ( 4 ) c h e b y c h e v 距离( c h e b y c h e v ，dis t a n c e ) 两个n 维向量c h e b y c h e v 距离的定义： d ( x ，y ) = m a x1 一虬i ( 5 )相似系数( c o s i n ec o r r e i a t i o nc o e f f i c i e n t ) 两个n 维向量c o s i n e 相似系数的定义： ( 1 - 5 ) d ( x ，y ) = ( 6 )协方差( c o v a ria n c e ) 两个n 维向量协方差的定义： 葺咒 i = 1 s = 喜学 ( 7 )相关系数( p e a r s o nc o r r e i a t i o nc o e f f i c i e n t ) 两个n 维向量p e a r s o n 相关系数的定义： 1 3 2 常用聚类方法 勺2 窆( 薯一；) ( 咒一歹) ( 1 - 6 ) ( 1 - 7 ) ( 1 - 8 ) 聚类分析( c l u s t e ra n a l y s i s ) 是指将一组个体按其相互间的相似程度归入几个子 类，根本思想是确定类群，使同一类内的各个体间差异最小，而不同类间的差距 最大。聚类是探索性数据分析和模式发现的一种基本手段，其目的是提取数据中 隐含的类结构。聚类算法及相关研究一直是国内外的热点 1 2 - 1 4 , 2 5 , 2 6 】，已经有大量 的聚类算法被应用于d n a 微阵列数据的分析【2 7 3 1 1 ，其类型涵盖了层次聚类、k - 均值聚类等，其间没有显著的共同点。 对于基因表达数据的聚类问题，由于目前对基因表达的系统行为了解得不全 面，没有聚类的先验知识，所以通常采用无监督学习方法。在基因表达数据分析 方面，层次聚类法、k 均值聚类法是常用的方法。下面主要介绍这几种常用的聚 类方法。 ( 1 ) k - m e a n s 算法 k - m e a n s 算法是一种典型的基于划分的算法，也是在基因芯片聚类分析中应 用最早的算法之一【3 2 】。给定一个数k ，通过最优化目标函数把数据集划分到k 个 5 不相交的集合。该算法在第三章有详细介绍。 ( 2 ) 层次聚类 层次聚类算法分为两种，一种是聚合式( a g g l o m e r a t i v e ) l 拘聚类方法，一种是分 裂式( d i v i s i v e ) l 拘聚类方法。 聚合式的层次聚类方法是一种自底向上的方法。开始的时候每个对象是一个 类，然后将最近的两个类合并，直到所有的对象都聚到一个类中。而分裂式的层 次聚类方法却完全相反，最开始所有的对象都在一个类中，然后将这个类分为两 个子类，使得这两个类距离尽量的远，依次分裂下去，直到每一个对象单独对应 一个类。由于层次聚类算法易于理解，便于可视化表示，因此得到较为广泛的使 用【3 3 1 。 a l o n 等【4 1 人提出的确定拟合的分裂式层次聚类算法是其中的一个典型。算法 的步骤如下： 随机初始化两个类中心点q ( _ = 1 ，2 ) 。 基因k 的表达向量是，则基因k 属于类j 的概率为： p j ( 一g k ) = e x p ( 一i 五一e1 2 ) e x p ( 一l 瓦一q1 2 ) ( 1 - 9 ) ， 更新类中心点的公式为： q = 弱( 瓦) e ( 瓦) 七七 ( 1 1 0 ) 弓和q 利用期望最大化算法进行迭代直至收敛。随着算法的不断迭代， 类的数目不断增长直到每一个类只包含一个对象。 ( 3 ) 自组织映射图 自组织映射( s o m ) 的数学模型是由t u e v ok o h o n e n 在1 9 7 9 年和1 9 8 2 年提 出和发展的【3 4 1 。该模型是基于实际神经细胞中的一种特征敏感细胞，这些细胞在 外界信号刺激下对某一种特征特别敏感，这种特征的形成过程是自学习的。神经 细胞模型中还存在一种细胞聚类的功能柱，它是由多个细胞聚合成的。当受到外 界刺激时，有的细胞聚合起来形成功能柱来完成同一种功能。 6 当外界输入不同的样本到人工的自组织映射网络中，开始时输入样本引起输 出兴奋细胞的位置各不相同，但通过自组织会形成细胞群，它们分别代表了输入 样本，反映了输入样本的特征。样本自学习后，在输出神经元层排列成一张二维 映射图，功能相同的神经元靠得比较近，功能不同的神经元分得比较开。该映射 过程是通过简单的竞争算法来完成的，其结果是一些无规则的输入自动排序，那 些有相似特征的输入对应的输出神经元靠得比较近，而特征相差比较多的神经元 离得比较远。 和k - m e a n s 方法相比，自组织映射方法对噪声有更好的鲁棒性。但是它也需 要事先给出类的数目，而且还要给出最初的二维映射图的结构。此外，如果数据 中存在表达量变化很小的基因，s o m 的聚类效果则非常糟糕【3 2 】。 ( 4 ) 模糊聚类 模糊聚类的概念最早是1 9 6 9 年由r u s p i n i 提出【3 5 j ，利用这一概念人们提出了 多种聚类方法，比较典型的有：基于相似性和模糊关系的方法、基于模糊图论最 大树方法和基于数据集的凸方法等。由于这些方法不适合处理大数据量的情况， 因此基于目标函数的划分方法受到欢迎并且得到了较为广泛的应用。和其它的聚 类分析相比，模糊聚类中的每一个对象不再仅仅属于某一类，而是以一定的隶属 度分别属于每一类。在动态的生命系统中，有的基因具有多个功能，参与不同的 生物过程，和多个不同的分子发生相互作用，这些情况可以采用模糊聚类的方法 进行分析f 3 6 1 。 1 3 3 聚类结果评价 聚类结果评价是指以客观定量的方式对不同聚类过程所得的结果进行质量和 可靠性评价。对聚类结果进行评价，黄金标准是能否发现生物学知识，即从数据 出发，能够找到新的生物学知识或得到明确的对某些生物学问题的答案。但是， 聚类方法作为一种探索性的知识发现方法，它的结果是预测性的，而生物学知识 还是非常不完备的，对方法进行生物学评价是非常困难的。目前，对聚类结果的 评价主要从内部标准和外部标准两个方面进行。内部标准分析应用给定数据内部 的信息来描述输入数据和聚类结果之间的一致性。外部标准是指有一个参考标准， 分析新的聚类结果与参考标准的匹配性，来判断聚类方法的好坏，外部标准分析 更有利于对聚类质量进行独立的、无偏的评价。以下介绍常用的几种聚类算法的 定量评价指标。 ( 1 ) ? r a n d 指数 在基因表达聚类分析中，r a n d 指数被广泛用来评价聚类结果与外部标准的一 致性3 7 , 3 s l 。本文通过将聚类结果与相应的外部标准进行比较来评价分析方法。聚 类结果和外部标准的类都可看作是将个体划分为组，将聚类结果与外部标准进行 比较等同于评价两种划分的一致性。r a n d 指数在下一章中将有详细介绍。 ( 2 ) 误差平方和准则 假定有一组样本( ，屯，) r ，要求将这些样本分成c 个类，由于存在多种 可能的分类方案，到底哪种分法最好? 这就必须定义一个准则函数，聚类问题就 变成对这个准则函数求极值的问题。最简单的准则是误差平方和准则，其准则函 数定义如下： 了= 卜i i 扛lj e 石 其中c 为聚类数，z 表示第i 个聚类的样本集合，历，是集合z 中所有样本的 中心。显然，使j 最小化的聚类就是最好的聚类。当每类的样本都很密集，而各 类之间又有明显的分离，使用这种准则进行聚类可得到最好的结果。而当各类界 限不清楚时，利用这种准则得到的聚类结果往往不能令人满意。 ( 3 ) s i l h o u e t t e 指数 s i l h o u e t t e 指数是采用类间分离和类内紧致性来评价聚类结果的好坏。如果在 样本空间中，各个聚类彼此分隔得比较远，而每类的样本又彼此靠近，则可以认 为聚类质量好。s i l h o u e t t e s 指数是基于每一样本到其所属类距离与到邻近类距离 的比值来定义的。对一给定划分uh x = 置u u 以，若样本g 被分配到置类， d i s t ( u ， ，) 为样本掰和y 间的分离( 相似度) ，口俐代表g 与墨中所有样本的平均分 离，即：口( g ) = d i s t ( g ，h ) ( ix , 1 - 1 ) ，设为另一类，d ( g ，一) 为g 与一中 h e x i ， g 所有样本的平均离散度，即：b ( g ) = m i n d ( g ，x m 。计算g 与所有其他类的平均 离散度，取则个体g 的s i l h o u e t t e 宽度删定义为： 8 = 磊b ( 丽g ) - a ( g ) m a x i 以1 2 i d 1 2 l ( 1 1 2 ) 显然，删的值间于1 与l 之间。若删接近l ，说明g 的确属于此类；若 涮接近1 ，说明g 被误分，应归入另一类；若删接近0 ，则口倒与6 例相当， 样本g 也可以归入最近邻类。类置的s i l h o u e t t e 宽度s ，可用其中所有样本的平 均s i l h o u e t t e 宽度来表示： 墨2 高互抛) ( 1 - 1 3 ) 划分u 的全局s i l h o u e t t e 宽度g s v ，定义为该划分中所有类的s i l h o u e t t e 宽度 的均值： 1 量 g s u = f x s , j 1 i = 1 ( 1 1 4 ) g s v 是u 的有效性确认指标，称为s i l h o u e t t e 撇( s i l h o u e t t ei n d e x ) 。s i l h o u e t t e 指数定义至少需要两类，且若一类只有一个个体，则该类的s i l h o u e t t e 宽度定义 为0 。 ( 4 ) f o m 值 f o m 法，是一种数据驱动的方法，用于比较来自基于启发式聚类算法的分类 质量。本质上属于留一交叉验证方法，即在g 个基因、f 个条件中保留 l ，2 ，e 一1 ，e + l ，刀) 进行聚类分析，留出条件e 用于验证，聚类后有k 个类，用 石，以表示每一类的基因集合。k 表示基因g 在条件口下的表达水平，u s , ( d 是 类，中的基因在e 条件下的平均表达水平，则 f o m ( k ) = ( 1 1 5 ) 对每个条件分别计算f o m ( e , k ) 值，并求和作为聚类方法的评价指标， f o m ( k ) = f o m ( e , 七) ( 1 - 1 6 ) e = l ，i l f o m 法存在一些应用上的限制，首先是该方法并非对所有的情况都适用，如 9 果所有的实验条件之间是相互独立的，那么取出条件p 后的万j 个条件下的聚类 结果就不能对e 条件有预测效果。但是，在实际情况下，f o m 法对于许多基因表 达数据集是可用的，可以应用于时间系列数据、来自不同组织样本的数据集。其 次，对于比较具有不同类数目的聚类结果是不合适的。因为f o m ( e , k ) ，定义为类内 方差在所有k 类上的和，随着类数目的增加，f o m 会下降。因此，可以定义调整 的f o m ，将f o m 除以一个因子，来弥补由于类数目不同而造成的统计偏差，计 算公式如下： 删化炉f o m ( 咖) 疗 ( 1 - 1 7 ) 1 4 课题研究的主要内容和文章的组织 本课题主要是对基于遗传算法基因芯片数据聚类分析算法进行研究。通过将 遗传算法引入k - m e a n s 算法，很好地弥补了k m e a n s 算法的一些缺点，使该聚类 算法能收敛到全局最优解，改善了聚类效果。本研究的主要目的是进一步提高针 对基因芯片数据聚类分析的算法性能，提出一种改进的遗传k m e a n s 算法，其主 要创新点有以下两个：一是基于k m e a n s 算法的不同实验类型的基因表达数据聚 类分析方法研究，得出针对基因芯片聚类分析的适宜参数；二是将第一步研究结 果融入g k a 算法，再进一步引入遗传育种理论中的优选理论，改进了g k a 算法， 提出一种新的算法i k g a 算法。 本研究采用r 语言来实现该算法，并采用酵母基因表达数据验证了该算法的 性能。同时本文还将i k g a 算法应用于猪基因芯片数据聚类分析，结果显示该算 法优于其它算法。全文共分五章： 第一章本章详细介绍了基因芯片数据聚类分析的有关知识，以及主要的聚类 算法，如k - m e a n s 算法、层次聚类、自组织映射图、模糊聚类等。还介绍了聚类 结果的评价标准。 第二章主要是对k - m e a n s 算法进行了详细的阐述，并对该算法的处理流程和 伪代码进行描述。重点研究了广泛用于基因表达数据聚类分析的k - m e a n s 算法的 相似度和数据转换方式的选择。 第三章讨论了用于聚类分析的遗传算法，介绍了用遗传算法进行聚类时的具 体步骤，重点研究了基于遗传算法的k - m e a n s 聚类算法，结合上一章的研究结果， 提出了新的i k g a 算法，并对该算法的处理流程和r 语言伪代码进行描述。通过 1 0 三组具体的实验进行分析和比较，并将该算法应用于猪基因芯片数据聚类分析。 首先用r 语言实现三种算法，用来对k - m e a n s 算法，g k a 算法和i k g a 算法的算 法性能进行比较。通过三个酵母基因表达数据集的实验，验证了本研究提出的 i k g a 算法优于其它两种算法。将i k g a 算法应用于猪基因芯片数据聚类分析， 进一步验证了该算法的优异性能。 第四章总结全文和对未来聚类分析研究的展望。 2 k m e a n s 算法聚类技术分析实验 基因表达的模式可以提供有关细胞状态的重要信息，基因芯片技术可以用一 个样本同时测量数千个基因的表达情况。近年来基因芯片技术被广泛应用于生命 科学及相关的各个领域，它推动了生物学研究的发展。聚类分析技术在分析基因 芯片表达数据中扮演了重要的角色，其中使用最广泛的是分层聚类( h i e r a r c h i c a l c l u s t e r i n g ) 3 9 1 ，k 均值聚类( k - m e a n sc l u s t e r i n g ) 删及自组织映射( s e l f - o r g a n i z i n g m a p s ，s o m s ) t 4 l 】等，这些聚类算法帮助我们了解潜在的生物学现象。但是，不同 的聚类算法，甚至于同一算法使用不同的参数，得到的类结构可能显著不刚3 7 ，对 于不同类型的基因芯片表达数据是否适用于相同的参数，还鲜有文献对此进行研 究分析。 对基因表达聚类分析的首先要对芯片实验所产生的基因表达矩阵进行预处 理，以确保基因表达水平的可比性【2 3 1 。数据预处理方法可分为对原始数据作标准 化处理和取表达比率的对数值两大类。常规的基因表达聚类分析算法基于个体间 的相似性度量( 简称相似度) 来衡量两个表达谱的相似程度，如p e a r s o n 相关系数、 e u c l i d e a n 距离、协方差、c o s i n e 相关系数等。其中被广泛采用的是p e a r s o n 相关 系数和e u c l i d e a n 距离。由于不同的聚类算法可能偏爱不同的数据转换方式和相似 度，因此，在基因表达聚类分析时，选择合适的数据预处理方法和相似度至关重 要，它是获得更加准确聚类结果的前捌3 7 j 。 本章以k m e a n s 算法为基准，对常见的两种类型的基因芯片数据适用的预处 理方法和相似度选取进行了研究分析，为其在基因芯片数据聚类分析上的应用提 供重要的参考依据。 2 1k m e a n s 算法概述 2 1 1k m e a n s 算法描述 k m e a n s 算法属于划分的聚类方法，即给定类的个数k ，利用距离最近的原 则，将行个对象分到k 个类中去，聚类的结果由k 个聚类中心来表达，基于给定 的聚类目标函数，算法采用迭代更新的方法，每一次迭代过程都是向目标函数值 减少的方向进行。在每一轮中，依据k 个参照点将其周围的点分别组成尺个类， 而每个类的几何中心将被作为下一轮迭代的参照点，迭代使得选取的参照点越来 越接近真实的类的几何中心，使得类内对象的相似性最大，类间对象的相似性最 1 2 疗个对象组成的集合 薯，i = l ，2 ，力 ，劫表示对象而的第j 个属性。对于 i = 1 ，2 ，n ，k = l ，2 ，k ， 对于矩阵 ：n萼薏，对象属于第七类(2-1)i 2 0 其他 膏 w = 】， o ，1 h e = 1 ( 2 2 ) ，之l 该式保证一个类中至少有一个对象且有一个对象仅属于一个类。 令第后个类的质心g = g 。，g ：，c 乙 ，则 一 嘞 = 号- 一 。_一 i = 1 第k 个类的类内差异( w c v ) 定义为： nd s ( 形) = ( 而一) 2 i = 1 一l 总类内差异( t w c v ) 定义为： ( 2 3 ) ( 2 4 ) ( 2 - 5 ) 此目标函数的目的是要找到即叨的最小值w = 【w 雎】，目标函数s ( w ) f f i 依g l 于数据集的几何形状和类中心的位置，吖叨的值越小，表明聚类效果就越好。因 此，算法通过不断优化吖叨的取值来寻求好的聚类方案，当研聊取极小值时，对 应的聚类方案即是最优方案。 1 3 铲 一 而 ，- 、 d肖 。问捌 = ” 祭 f 柚 = 、j 矿 双 k m e a n s 算法步骤描述如下： 已知样本数据集 而，屯，) ( 1 ) 给定类别数k 和允许误差f ； ( 2 ) 初始化聚类中心q ，其中k = 1 ，2 ，k ； ( 3 ) 按下式修正w & ，其中i = l ，2 ，刀，k = 1 ，2 ，k ； 乃么：j - 若。而一簟0 22 哑n l l 五一簟0 2 ) ( 2 6 ) 10 其它 ( 4 ) 按下式修正聚类中心c k ，其中k = 1 ，2 ，k 。 ( 5 ) 计算误差： w , k x f c = i = 1 e ：k 粉圳一创 ( 2 - 7 ) ( 2 - 8 ) ( 2 9 ) ( 6 ) 如果吖叨的值低于一个给定的最小阈值或者连续两次类中心值之差的和 小于一个参数阈值，即e f ，则算法结束；否则n = n + l ，转( 3 ) 步继续计算。 对k - m e a n s 的算法步骤作以下解释：既是将第i 个样本归入第k 个类的标志。 r g i k = l 表示第i 个样本归入第k 类，彤产0 表示第i 个样本不归入第k 类。在算法 第( 3 ) 步中修改暇七，实际上就是调整第i 个样本所属的类别。如果 忙一4 。0 2 = 唧n l l x , 一4 峨，即如果x r 离第七类的类中心最近，则暇尸1 ，即将而 4 p 一 吻 ，l d 同 闻f 心 = ” 科 心 i i 、， 形 文 归入第k 类；否则不归入第k 类，即卿，因此第( 3 ) 步是用来修改分类的。第( 3 ) 步修改分类后，聚类中心发生了改变，需要作出修正，第( 4 ) 步来完成修正聚类中 心的工作。从这个算法的第( 3 ) ( 4 ) n - - f 以看出，这个算法是在每次把全部样本都调整 完毕后才重新计算一次各类的聚类中心，因此是成批样本修正法。也可每调整一 个样本的类别就重新计算一次各类的聚类中心，即采用逐个样本修正法。 2 1 2k m e a n s 算法伪代码 k m e a n s 算法的伪代码描述如下： 袢输入：聚类数目k 迭代次数t ，允许误差； 为每个个体随机确定分类； 计算初始各个聚类中心； 设置迭代计数t = l ； w h ii e ( e ( t ) - e ( t - 1 ) t ) ) 根据样本点与各聚类中心的距离分配聚类； 计算类内误差平方和e ( t ) ； 计算各个聚类中心： 输出聚类结果 初始聚类中心的选择可以有多种方法，例如，根据已确定的聚类数k 直接选 取数据集合中的前k 个数据作为初始聚类中心，或者在数据集中随机抽取k 个数 据作为聚类中心，或者采用等分的方法在数据空间中确定k 个点作为初始聚类中 心等。初始聚类中心的确定对聚类质量的影响很大。 k - m e a n s 算法是应用最广泛的聚类算法之一，- k m e a n s 算法的优点在于计算速 度快，资源消耗小，对于处理大数据集，这个算法是相对可伸缩和高效的，计算 的复杂度为d 彻砂，其中刀是对象的个数，k 是类的数目，t 是迭代的次数。一般 来说，艇 雄，f 。匣群卜。一h。0vd)摊嘲肇呔州幅样站仆时k燃竖遥匿恃长赢榭一ho0vd)摊嘣鼙呔榭惜群对仆盯燃肇遥q匣长墨晕蚶一爆 oo州田hho 9o0州ooo ooo刊田0 s叶o0州西掣0 oo刊hl-o 露牛 。品oo制o-8no0刊no【o，；oo刊h竹hob寸o0甜n口-o。doo州寸no d6口010制寸n-0d6oo剞寸nho ，10o制n-0no0刊”ooo葛o0剞n协oon8o制oo ，：oo制西dokgo剞o0oo刊no口oooo州no oonoo刊oo oooo刊西o0 矗6noo刊o0no-o刊苫0 劬900o卅0 ，oo刊西ooq。n竹o0刊16o onno0槲时oh08o刊口no-0o“竹o0荆nookoo刊noo ；00o州口oo 钆竹oo刊ioo kio0州o曩五罚oo刊“oo；oloo槲西oo b00o刊ob10o剞葛9o。b10o卅摹o00lo0刊葛o ，ni_o-o刊卜no m clono0州oh-o kno0州竹oop00o*器9oog-0刊ooob8o刊ooo8o刊。口9o 犍斟删钕盎超醋籁垛水罂coj1e。口 砸哥糕帐枨罂o u i n o u髓吼h，ooxo廿上q 艇酲皿即 铤斟呶督蹿斟蚁备恹 嚣 凸o 口j o 芷o j d 芷 越警罂 pop口uu，hd】(o口c叫口c篮。卫一_【h c l b 耘霉p u 盘g 8，球鞲籁【僻 o n 口61o刊曲一o b1o刊o 钿田_o刊10o 。；io剞ho o=0刊nho 霸 ooio州鐾00o0州nnon9o0刊10obdo0刊寸oo0 koo刊oo西0koo刊o西ok口oo刊016-o ，boo刊noo。ie西oo刊n卜-o01900州寸o帕010o州nn丫o0o_0槲180。寸口o-0刊西h0，no0刊18o o西noo刊lo卜ooooo剞ohoopoo制ooo0州d富o：西o0州016o000制口06og0刊：西0 ，口noo刊n西0 onnoo刊西口o o竹oo制寸口o。n竹o0州n寸oo口80州西noo竹o0制oo竹oo刊西曲-0o竹oo刊卜o o寸oo州leo，：o0刊=oo口寸o0制n寸d0o口noo刊nn口oohnoo刊口o。no0制nnoo ondoo刊价oo