（计算机应用技术专业论文）基于关系的dna微阵列数据聚类分析.pdf

摘要摘要d n a 微阵列产生巨量的表达谱数据，用以挖掘特定的生物信息，而对表达谱数据的分析离不开有效而可靠的聚类算法。现有的聚类方法都是把具有相似表达模式的基因或样本归为一类，而微阵列数据的高维小样本特点，致使基于d n a 微阵列的聚类算法是在超高维的空间中进行的，从而产生了维数灾难问题。本文从另一个侧面入手，注重基因之间或样本之间的关系，提出了一种新颖的聚类方法。该方法把经典的基于相关的d n a 微阵列数据聚类分析方法和图论知识相结合，能更好地揭示基因或样本之间的相似性，且避免了维数灾难问题。把本文方法运用到真实的d n a 微阵列数据( y e a s t 数据和n c i 数据) ，并与其他的聚类方法进行了实验比较，实验结果显示，本文方法获得了较好的聚类效果。关键词：d n a 微阵列聚类关系网络局部结构特征关系特征一一垒! 壁竺!一a b s t r a c td n am i c r o 蝴y sa r eu s e dt op r o d u c e1 a r g es e t so fe x p r e s s i o nm e a s l l r e m e “t s 仃o mw l l i c hs p e c i 丘cb i o l o g i c a li n f o m l a t i o ni ss o u g h t a n de m c i e n t 趾dr e l i a b l ea l g o r i 岫sf o rc l u s l e r i n g a r cr e 删r e dw h e na n a l y z i n gr n i c r o a 玎a yd a 协m o s to fm ec o n v e f l t i o n a lm 劬o d s 伊o i l pg e n e so rs 砌p l e s 、v i t l ls i m i l a re x p r e s s i o np r 0 6 l e si n t o 山es 锄ec l u 8 t e ld u et 0m ec h a r a c t e r i s t i c so fm i c m a r r a yd a t at h 砒i th a saf b wt i s s u es 锄p l e sb u te a c hc 0 心却n 凼t oe x p r c s s i o nl e v e l so f ah u g en 咖b c ro f g e n e s ，c l u s t e 血ga l g o r j 岫sb a s e do n q ai n i c m a r r a yi sp e 面彻e di nas p a c eo fs u p e d l i 曲d i i n e n s i o n s ，r c s u i t i n gi nt 1 1 ed r c l b l e mo fc 1 】r s eo fd 曲c n s i o n a l 吼f o 咄i n go nr c l a t i o i l s h i pb e t w e e nn s s u e so rg c n e 5 ，an o v e lc l u s 矧n gm e m o di sp r o p o s e di nt h i sp m 埘c hc o m b i n e s 岫c l a s s i c a lc o 啪l a t i o n b a s c dc l u s t e r i n gf o rs t l l d y i n gd n am i c r o a 仃a yd a 协a i l d 聊h i c a lm c o r y nc 眦d e n 曲a t ei i 仰吐他s i i n i l 撕t yb e t 、v e e nt i s s u c so rg e n e s ，帕1 ea v o i d i n gt l i ep m b l e mo fc u r o fd i m e n s i o n a l i t y a p p 】i c 鲥o no ft h ep r o p o s c dm c l o dt dp u b l i c l ya v a j l a b l ey e a s t蛐dn c id 枫c o m p a r e d 、i t l ls o m eo 也e rm e m o d s ，d c m o n s 仃a t e s 恤tm ep m p 0 3 e dm e t l l o di sm o e 位c l i v c 鲫de 伍c i e n ti i lc l l l s t 嘶n gg e e so r t i s s u e s k 胛砌：d n am i c r o a r r a y ，c l u s t e r i n g ，r e i 窘t i o nn 咖。咄1 0 c 曩is t r u c t 叭f e a t l l r e ，r e i a t i o nl 奄a h i r e y 8 5 9 0 6 9独创性( 或创新性) 声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：曼墨j 芷日期垭厶至! 旦! 目关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解密后遵守此规定)本学位论文属于保密在一年解密后适用本授权书。本人签名：导师签名：曼盍j 公1 参日期圣翌竺! 基羔投日期2 壁至】丘旦第一章绪论第一章绪论随着科学技术的快速发展，人们对于自身的认识在不断提高。然而人类本身的诞生、成长、疾病等生命现象还存在着大量的谜团。至今，一些重要的生命现象依然无法得到科学的解释。特别是在医学方面，一些重要的疾病还很难进行诊断与治疗。近年来，快速发展的信息技术与现代医学越来越紧密地结合在一起，并产生了生物医学信息处理技术。目前，生物医学信息处理主要包括医学图像处理与分析、计算机辅助诊断与治疗系统、医学信号的检测与处理和基于基因技术的生物信息学。而生物信息学是一门崭新的综合性学科，并在医学应用上有着广阔的空间和前景。实际上，最近生物基因技术的快速发展，使得人们能够在分子水平上认识生命现象并在一些方面得到了突破。由于人类或者生物所提供的基因数据是巨大的，并且按一定的方式进行着复杂的编码，破解这些生命的密码则需要数理科学和计算机科学的共同努力。这样便产生了生物信息学和相应的生物信息技术【3 矾。这门新的学科不仅为最终揭开生命之迷奠定了科学基础，并且为现代医学的发展提供了一些崭新的工具。实际上，基因技术很早就被应用到医学诊断中。一些遗传性疾病的根源大致可归结为一个或几个基因出了问题。也就是说，遗传疾病是由一个或几个基因所控制的。这些基因的缺失或没有得到充分的表达，则会导致了这种疾病的产生。然而，这种分析方法很难推广到一般性疾病，如心脏病、癌症等。实验表明，一般疾病不是由单个或几个基因的表现所控制，而是由许多基因的共同表现所确定的。因此对于一般疾病的研究则需要观察众多基因的表达水平。根据这种实际需要，d n a 微阵列芯片技术应运而生并得到快速发展。这种生物芯片可以同时检测到几千甚至上万个基因的表达水平值。这些生物数据不仅能够为生物特性、疾病的分析和发现提供依据，并且能够发现与疾病相关的基因，并应用于疾病的分类、诊断和治疗。进一步，我们还可以通过这些数据分析发现基因之间的调控关系为疾病的治疗提供依据。基于关系的d n a 微阵列数据聚类分析1 1 研究背景d n a 微阵列数据的聚类分析对于研究基因功能和基因调控机制有重要意义如有效鉴别癌症的基因表达模式从而获得癌症模式在分子级别的有效分类，作为一个无监督数据聚类问题，是在分子级别上有效实现癌症诊断和治疗的基础和前提。在d n a 微阵列数据上的聚类分析方法可以分别用于对基因或者样本聚类，对基因聚类可以发现一些功能相关的基因集团，进而预测基因的功能”：对样本的聚类( 实验中组织样本被标明为特定的种类，如癌变组织或正常细胞，癌症的各个类别、不同阶段等，微阵列数据的基因可看作样本的特征或属性) 可以发现不同的疾病亚型1 等等。目前，用于d n a 微阵列数据聚类的方法主要有k 一均值法、模糊k 一均值法、自组织映射神经网络法、分级聚类法等。不论是基因聚类还是样本聚类，这些方法都是以聚类个体( 基因或样本) 的自身特征参与聚类。把具有相似表达谱的基因( 样本) 聚为一类而没有考虑聚类个体间的相互关系。而d n a 微阵列数据具有这样的特点：基因芯片制作技术的发展使得在一个d n a 微阵列数据上可能含有超大规模的基因表达水平信息( 如成千上万个基因的表达水平) ，而由于有限的病人数和昂贵的测试费用等使得能够获得的癌症组织样本的数目又极其有限( 如几十或几百个) ，使得在对d n a 微阵列数据进行样本聚类时，存在大量无关基因的干扰而不能正确分类，而且正是这个原因，使得基于d n a 微阵列数据的癌症组织样本的分子分类( 聚类) 问题是在一个超高维空间中的超小样本上进行的，从而无可避免地遇到了维数灾难现象；且微阵列数据通常不满足正态分布假设且存在噪声干扰使用传统的聚类方法进行d 咐a 微阵列的数据分析的效果并不是最佳。因此，急需在数据分析方面改进现有的方法或发展新的方法。正是出于这样的现状：现有的d n a 微阵列数据聚类方法都是基于基因( 样本)个体特征，直接在表达水平数据上进行聚类而存在这样那样的问题，很难得到令人满意的效果。本文尝试从另一个侧面入手，关注基因之恻( 样本) 之间的关系，把传统的基于相关的d n a 微阵列数据分析方法和图论知识相结合，提出了一种新第一章绪论3颖的d n a 微阵列数据聚类方法，通过挖掘基因( 样本) 之间的关系特征来聚类基因( 样本) ，能更好地揭示基因( 样本) 之间的相似性，获得了较好的聚类性能，而且在一定程度上避免了维数灾难问题。1 2 本文结构安排本论文在分析传统聚类方法的基础上，结合d n a 微阵列数据的特点和分析现状，提出了一种较为新颖的用于d n a 微阵列数据聚类的方法，在算法思想上作了详细阐述，并应用到了真实的d n a 微阵列数据上，收到了良好的聚类效果。具体章节的内容安排如下：第一章：简单介绍d n a 微阵列数据聚类分析的意义、研究现状及其应用：第二章：简要介绍d n a 微阵列的相关知识；第三章：系统介绍目前国内外用于d n a 微阵列数据聚类的传统方法：第四章：从算法理论上详细阐述了基于聚类个体间关系的d n a 微阵列数据聚类方法：第五章：将本文提出的方法应用到实际的d n a 微阵列数据中的实验结果、结果分析及与其他方法的实验结果比较：结束语总结本论文的主要研究成果及意义，同时也指出了研究工作中存在的不足和迸一步的解决思路。本论文的研究工作在国家自然科学基金( n o 6 0 3 7 1 0 4 4 ) 和国家留学回国人员科研基金的支持下完成。基于关系的d n a 微阵列数据聚类分析第二章d n a 微阵列数据背景知识介绍d n a 微阵列( d n am i c r o a r r a y ) 又称d n a 芯片，基因芯片( g e n ec i l i p ) 。2 0 世纪9 0 年代初兴起的人类基因组计划( h g p ) ，其研究重点现己从结构基因组迈向了功能基因组的研究。揭示生命的本质，阐明基因的功能是后基因时代的重要任务，随之而产生的基因芯片( g e n ec h j p ) 技术，为功能基因组学研究提供了强有力的手段。由于基因芯片具有高通量和平行检测等特点。所以该技术自1 9 8 9年提出并取得国际专利以来【2 3 ，2 ”，已经在基因组测序、基因表达及功能分析、基因文库筛选、基因突变检测及基因多态分析、新药物的筛选开发、病原体检测及致病机制研究等方面得到了广泛的应用。2 1d n a 微阵列技术我们首先介绍一下基因的生物学定义和作用。在我们的每个细胞中，都包含着完全相同的遗传物质，即2 3 对染色体。而每条染色体是由4 种碱基通过双螺旋结构对偶连接而成的d n a 。d n a 是遗传的物质基础，它决定了蛋白质的合成。基因被定义为能产生一个特定蛋白质的d n a 序列片断。它是人类遗传的基本单元。科学家估计，人类共有3 4 万条基因并且很稳定。然而，这些基因在每个人中的表现不同，这就造了人类之间的千差万别。这里包括了不同人之间的差别和每个人不同时期之间的差别。为了检测基因的表达水平，人们于2 0 世纪9 0 年代开发了d n a微阵列基因芯片，即基因芯片。它能够同时测量出成千上万个基因表达水平值。这些数据被称为d n a 微阵列数据或大规模基因表达谱。我们知道蛋白质的合成是由d n a 决定的，但是基因不能直接翻译成蛋白质，而是通过产生一个m r n a 中间体来进行蛋白质的合成。从基因到m r n a 的过程称为转录( t 肼l s c f i 口t i o n ) ，而从m r n a 到蛋白质的过程称为翻译( 锄s l a t i o n ) 。在转录阶段，细胞核中d n a 带有的遗传信息通过碱基配对原则转录到m r n a ( 信使r n a )上这些m r n a 再通过t r n a 进行蛋白质合成。微阵列实验就是将一些荧光标记第二章d n a 微阵列数据背景知识介绍的m r n a ( 即d n a 单链) 通过配对杂交对应到微阵列芯片上的d n a 探针上，从而测量细胞当中不同基因对应的f t l r n a 丰度( r e d u l l d a n c y ) ，即基因的表达水平值( 也称为基因表达谱数据) 。根据这些数据，我们便可以分析不同的人或人在不同条件下的身体特征或健康的状况。2 1 1d n a 微阵列的提取微阵列的产生过程是将许多特定的寡核苷酸片段或基因片段作为探针，有规律地固定于支持物上，然后与待测的荧光素或放射性同位素标记的核酸样品按碱基配对原理进行杂交，再通过激光共聚焦荧光检测系统等对芯片进行扫描，对每一探针上的荧光信号做出比较和检测，并用计算机系统分析从而迅速得出所要的信息。其过程由图2 1 示出。主要包括下列基本步骤：芯片和样品制备、杂交反应、芯片信号检测和数据的生成。( 1 ) 基因芯片的制备。基因芯片的实质是高度集成的寡核苷酸阵列，制造基因芯片首先要解决的技术是如何在芯片片基上定位合成高密度的核酸探针。目前基因芯片的制备主要采用三种方法：即光蚀刻合成法、压电印刷法、点样法。( 2 ) 样品的制备。生基于关系的d n a 微阵列数据聚类分析生物样品成分往往比较复杂，所以在与芯片接触前，必须对样品先进行处理。为了提高结果的准确性，来自血液或组织中的d n m r n a 样本须先行扩增，然后再被荧光素或同位素标记成为探针。( 3 ) 杂交。影响杂交的因素很多，但主要是时问，温度及缓冲液的盐浓度。如果是表达检测，需要长历时，低温和高盐条件的较严谨性杂交。而如果是突变检测，需要短历时，高温和低盐条件高严谨性杂交。总之，杂交条件的选择要根据芯片上核酸片段的长短及其本身的用途来定。( 4 ) 杂交图谱的检测和读出目前最为常用的是激光共聚焦荧光检测系统，其主要原理是：与芯片发生杂交的探针上的荧光被激发后经过棱镜恰好能通过共聚集小孔被探测器检测到，而芯片之外的其它荧光信号则不能被探测器检测到，检测到的荧光信号通过计算机处理后就可直接读出杂交图谱，此法灵敏度和精确度较高，但是扫描所需时问较长。此外，近年来还发展了多种检测方法。如质谱法，化学发光法，光导纤维法等多种方法。2 1 2d n a 微阵列技术的应用基因测序和突变检测。d n a 芯片用于测试基于杂交测序法( s b h ) 发展而来的，该技术增加了微阵列中寡核苷酸的有效长度，从而增加了测序的准确性，可对较长的d n a 片段进行测序，另外也适用于对不同基因组同源区序列的比较及含有内部重复序列d n a 片段的序列分析。致病微生物的快速诊断。a n t h o n y 等人建立了一个在4 小时以内便可检测和识别出致病微生物的方法，该方法的具体过程是使用随机引物通过p c r 法扩增细菌核糖体2 3 sd n a ，后通过检测系统来识别。癌症的诊断及治疗。目前基因芯片技术己应用于癌相关基因突变的快速检测。由于可以利用基因芯片对某一细胞的基因表达情况进行一个全面的了解，所以基因芯片技术还可进一步应用于癌症的精确诊断及治疗，利用该技术可对包括白血第二章d n a 微阵列数据背景知识介绍!病、淋巴瘤、皮肤黑色素瘤及乳腺癌等多种癌症的癌细胞亚群进行区分，还可利用它对治疗方案进行评估和新药药效评价，此外还能对癌症的发生、发展和转归进行预测。此外，可利用基因芯片技术观察药物对肿瘤细胞基因表达谱的影响，评估药物对肿瘤治疗的可行性，从中筛选出抗肿瘤候选药物，对肿瘤药物的研究和开发提供了极具价值的参考资料。基因芯片技术在癌症基因研究及临床治疗领域的应用将不但使我们能更快速可靠地对癌症进行诊断，对其发生的内在分子机理也将有更深入的了解，同时也将为癌症治疗药物的开发提供极大帮助。寻找新基因。定量检测大量基因表达水平在阐述基因功能、探索疾病原因及机理、发现可能的诊断及治疗等方面是很有价值的。基因芯片技术在发现新基因及分析各个基因在不同时空表达方面是一项十分有用的技术，它具有样品用量极少，自动化程度高等优点，便于大量筛选新基因。目前，大量人类e s t s 给c d n a微阵列提供了丰富的资源，数据库中4 0 0 0 0 0 个e s t s 代表了所有人类基因成千上万的e s t s 微阵列将为人类基因表达研究提供强有力的分析工具。这将大大地加速人类基因组的功能分析。后基因组研究。基因组测序完成后，未知基因的功能研究是一个十分诱人的后基因组研究课题。斯坦福大学的d a v i s 研究小组的研究提示d n a 芯片技术将来可能应用于人类基因组测序完成后阐明开放读码框架0 r f 生物学功能的研究，可能会对深刻认识生命现象及药物设计带来重大影响。此外，基因芯片还广泛地应用于药物筛选、药物作用机制研究、毒理学研究、基因扫描、环境化学毒物的筛选、耐药菌株和药敏检测等多个应用领域。人们相信，在新的世纪中，基因芯片将会在人类疾病的基因诊断中发挥巨大的作用，为整个世界带来巨大的社会效益。基于关系的d n a 微阵列数据聚类分析2 2d n a 微阵列数据分析现状由于基因芯片通常产生巨量的表达谱数据，数据挖掘技术已经被广泛的应用到基因表达谱的许多方面，并取得相当的成功。基因芯片的基因表达谱的生物信息学分析流程一般包括前期的数据预处理、标准化、差异表达基因选择，以及后期的无监督与有监督分析、基因功能的预测与注释、基因调控网络构建、代谢通路和信号传导分析等。对相应的基因表达数据谱的分析取决于我们研究的具体目的。其中监督与非监督数据分析方法现常用于基因表达分析，如预测基因功能分类及恶性肿瘤分级【5 j 。往往是比较矩阵行和列的相似性或差别：如果发现两个行相似，我们可以推测它们对应的基因具有协同调节和功能相关性：如果两个列相似，则它们对应的组织是属于同一种病类。分类研究主要用于癌症分类，g o l u b 等旧利用基因表达谱对人白血病进行了分类：x i o n g 等【7 】采用了主成分分析与f i s h e r 判别分析方法相结合的办法，对结肠癌数据进行了分类研究，结果显示：采用7 个主成分可以获得精度为8 7 的判别结果。2 0 0 2 年l i w j 【e 1 采用f i s h e r 方法与逐步优化过程相结合的办法，只用5 6 个基因，预测精度就可达到大约9 5 。监督方式是假定已知一些或全部表达谱的额外信息，可以把这些额外信息看成是矩阵的行或列的标签，有了这个信息，再建立一个分类器，该分类器可以通过表达谱预测标签；非监督数据分析是通过聚类来发现具有协同调节性的基因或属于同种疾病的组织样本，也即聚类分析。聚类分析方法可以分别用于对基因或者样本聚类，对基因聚类可以发现一些功能相关的基因集团，进而预测基因的功能”】；对样本的聚类( 实验中组织样本被标明为特定的种类，如癌变组织或正常细胞，癌症的各个类别、不同阶段等，微阵列数据的基因可看作样本的特征或属性) 可以发现不同的疾病亚型3 钔，用来帮助疾病诊断、观测药物疗效等。监督或非监督数据分析只是表达数据分析的第一步，表达谱聚类后的下一个重要步骤是利用具有相似表达基因假想启动子序列，来发现基因组里的调控序列因子。长远来看，生物学越来越成为可以量化的学科，基因芯片信息挖掘方面的研究不断取得新的进展，今后基因第二章d n a 微阵列数据背景知识介绍!表达数据分析方法将会有很好的发展。既然聚类分析是进行表达数据的数据挖掘的第一步，其效果直接影响后续的表达谱数据分析性能，故发现和发掘好的聚类算法至关重要。本文着重讨论聚类分析方法，现有的可用于微阵列数据聚类的方法主要是k 一均值法、模糊k 一均值法、自组织映射神经网络法和分级聚类法等，但是这些方法运用在d n a 微阵列数据上的研究成果却很少见。这其中一个很重要的原因，我认为是这些传统方法直接运用在d n a 微阵列数据上进行聚类分析，并不能很好地揭示基因或样本之间的相似性。基于关系的d n a 微阵列数据聚类分析第三章传统的d n a 微阵列数据聚类方法3 1 。1 模式识别概述3 1 模式聚类概述模式识别川诞生于2 0 世纪2 0 年代，随着4 0 年代计算机的出现，5 0 年代人工智能的兴起，模式识别在6 0 年代初迅速发展成为一门学科。它所研究的理论和方法在很多科学和技术领域中得到了广泛的重视，推动了人工智能系统的发展扩大了计算机应用的可能性。几十年来，模式识别研究取得了大量的成果，在很多地方得到了成功的应用。但是，由于模式识别涉及到很多更复杂的问题，现有的理论和方法对于解决这些问题还有很多不足之处。关于模式识别，第六届国际模式识别会议主席，德国爱尔朗根大学h n i 锄啪教授在模式分类专著中指出：“模式识别是研究模式的自动处理和判读的数学技术问题，它既包含简单模式的分类，也包含复杂模式的分析。”针对本文要讨论的内容，我们对模式、模式识别作如下狭义的定义：模式是对某些感兴趣的客体的定量的或结构的描述，模式类是具有某些共同特性的模式的集合。模式识别是研究一种自动技术依靠这种技术，机器将自动地( 或人尽量少地干涉) 把待识别模式分配到各自的模式类中去。3 1 2 模式聚类聚类是探索性数据分析和模式发现的一种基本手段，其目的是提取数据中隐含的类别结构。聚类分析的基本思想非常朴素、直观和简单它是根据各个待分类的模式特征相似程度进行分类的，相似的归为一类，不相似的作为另外一类-简单地说相似就是两个特征矢量之间各分量分别较接近。由于在分类中不需要用训练样本进行学习和训练故此类方法称为无监督分类。首先在聚类算法中，距离的定义非常关键，可以在很大程度上影响聚类算蔓三童传统的d n a 微阵列数据聚类方法旦法的结果。根据适用情况的不同，每种距离都有自己的优缺点。p e a r s o n 相关系数能够反映表达模式形状的相似性但不强调两组测量的数值关系，对偏差比较敏感。而欧式距离可以反映两者在数量关系上的差异，不强调形状的相似性。另外，基于模式相似准则而建立的分类方法的有效性，从根本上讲，首先取决于模式特征点在特征空间的分布情况。如果同类的模式特征点密集，不同类的模式特征点相距较远，即特征点按类群聚，一般的分类方法通常是有效的：反之，如果不同类的模式特征点混杂散步，许多分类方法往往无效或效果不佳。既然某些对象属于不同的类别，它们之间必然有一些重要特征显著不同，之所以出现上述特点混杂情况，原因是特征选得不当，可能是对于所选取的特征，不同类的模式的特征值差别不大，换句话说，有显著差别的特征没有选取。这时应该重新提取特征，选取它们之间显著不同的特征而产生新的特点。另一个可能的原因是，虽然各分量满足上述要求，但它们组合起来未必能使这些特征点按群聚类。从技术上讲，方法的有效性取决于分类算法和特征点的分布情况的匹配。故在聚类分析中，针对数据的特性进行有效的特征提取至关重要。3 。2 传统的d n a 微阵列数据聚类方法目前用于d n a 微阵列数据分析的聚类方法主要有k 均值法、模糊k 一均值法、自组织映射法、分级聚类法等。这些方法都是把基因表达谱向量作为特征模式，将一组个体按其相互间的相似程度归入几个子类，根本思想是确定类群，使同一类内的各个体间差异最小，而不同类间的差距最大。3 2 1 学习准则聚类需要一个准则来衡量两个表达谱的相似程度，选择一种合适的比较准则是至关重要的。基因表达数据分析中普遍使用的准则为欧氏距离和p e a r s o n 相关系数。欧氏距离测量空间中两个点的绝对距离，故同时考虑了矢量的方向和幅度。1 2基于关系的d n a 徽阵列数据聚类分析若直接使用原始数据进行计算，则表达谱幅度相似的基因将被认为是相似的。但生物学上更倾向于寻找表达水平不同而表达谱形状相似的基因，故使用欧氏距离前需对数据作适当的转换，如重新进行标度或作归一化处理。p e a r s o n 相关系数从本质上说是测量两个表达矢量所指方向的相似性，处理时将其视为单位矢量，因而对幅度的变化不敏感。但若两个不很相似的基因表达谱在某一个突出的峰或谷特别相关的话，p e a r s o n 相关准则可能给出假阳性。相关系数的一个有趣的性质是它可用来检测负相关的基因。3 2 2 传统聚类方法k 一均值法( k - 嘴a n s )k m e a n s 聚类f 17 】是一种传统的统计聚类方法。在类别数k 给定的情况下，该方法能够按某种距离将所有基因( 样本) 点自动地划分到k 个类中。该算法的基本思想是首先任意设定k 个类中心的初始值，然后根据一定的距离准则( 如欧氏距离) ，分别计算每个表达谱与各个类中心的距离，并将它归到距离最近或“相似”的类中心代表的那一个类。再计算每个类中样本点的平均点，并以此取代原来的类中心。依次下去。直到类中心都不再变化，算法终止，并得到了分类结果。下面给出基于欧氏距离的k 一均值算法。1 条件及约定设待分类的模式特征矢量集为“，x ：，一，x 。 类的数目k 是事先取定的。2 基本思想该方法取定k 类和选取k 个初始聚类中心，按最小距离原则将各模式分配到k类中的某一类，之后不断地计算类中心和调整各模式的类别，最终使各模式到其判属类别中心的距离平方和最小。3 算法步骤( 1 ) 任选k 个模式特征矢量作为初始聚类中心：z f 0 ，z ”，z p ，令t = o 。( 2 ) 将待分类的模式特征矢量集) 中的模式逐个按最小距离原则分划给k 类第三章传统的d n a 微阵列数据聚类方法堡中的某一类，即如果d i ) _ m i n k 】，j _ l ，2 ，( 3 一1 )贝0 判x ，d ，r “。式中d 扩表示t 和甜，的中心z ，的距离，上角标表示迭代次数。于是产生新的聚类甜“( ，= 1 ，2 ，k ) 。( 3 ) 计算重新分类后的各类心雩+ ”2 南。岔r ，川2 ，kb 2 ，式中疗y “为珊y 类中所含模式的个数。因为这一步采取平均的方法计算调整后各类的中心，且定为k 类，故称k 一均值法。( 4 ) 如果z 罗“= z 罗 l 是一个可以控制聚类结果的模糊程度常数。( 3 - 3 )在不同的隶属度定义方法下最小化( 3 3 ) 的损失函数，就得到不同的模糊聚类方法。其中最有代表性的是模糊k 一均值法，它要求一个样本对于各个聚类的隶属度为l ，即k，( t ) = l ，f _ l 疋，n，；1( 3 - 4 )在条件式( 3 4 ) 下求式( 3 3 ) 的极小值，令j ，对研，和，( 工) 的偏导数为o ，可得必要条件：主k 肛) r z ，蒜驴1 2 k。巧2，mxk r)fk。h。问一一，j第三章传统的d n a 微阵列数据聚类方法1 5，cx，=瓣，=，z，n；，=t，z，kc ，s ，l 】| i x ，一m 。阱一用当前的聚类中心根据式( 3 6 ) 计算隶属度函数；用当前的隶属度函数按式( 3 5 ) 更新计算各类聚类中心。当算法收敛时，就得到了各类的聚类中心和各个样本对于各类的隶属度值，从而完成了模糊聚类划分。k 一均值和k 一均值一样，对聚类中心的初值非常敏感。人脑是由大量的神经元组成的，它们并非都起着同样的作用，处于空间不同部位的区域分工不同，各自对输入模式的不同特征敏感。t k o h o n e n 认为：神经网大脑神经系统自组织特征映射的人工自组织映射网络，人工自组织映射与大脑映射有许多共同特征，通常又称作自组织映射神经网络( s e l r g a n i z i n gm a p ) 或简称s o m 网络。s o m 网络可以作为一种神经网络聚类方法它以无监督的方式进行网络训练，能自动对输入模式进行聚类。它是将高维空间的点映射到具有拓扑结构的二维网格上。输入的每一个分量到每个结点都具有连接权。在学习过程中，获得最大响应的结点以及附近的结点的权值得到不同程度的修正，使得对输入的响应增加。对不同样本反复学习以后，网格能够反映出输入模式的结构特征，并自动完成样本分类。训练好的s o m 网格节点上已分配好相应的基因表达谱，节点的权基于关系的d n a 微阵列数据聚类分析重矢量代表相应类内表达谱的平均，节点相距越远。1 自组织映射神经网络结构自组织映射网络是一种竞争式学习网络，在学习中能无监督地进行自组织学习。输一- ，c o出层的类神经元们彼此竞争，以争取学习的机会。基于竞争方式的s o m 网络基本结构如燮图3 1 所示。x且相邻节点表示相似的类，类差别越大，其图3 1 中，输出层有n 个图3 l 自组织网的基本结构输出神经元；输入层是任意一个l x m 维的输入x ；晰是一个lx m 维的向量，表示第i 个输出神经元与输入之间的链接权值。对于每一个输入x ，都只有一个输出神经元竞争胜利，这个胜利神经元即图3 1 中的m n n e ro u t p u t ，胜者获得了学习的机会可以修改对应的链接权值嘶。2 s o m 网络的工作原理s o m 网络的工作原理是将任意维输入模式在输出层映射成一维或二维离散图形，并保持其拓扑结构不变。此外，网络通过对输入模式的反复学习，可以使权重向量空间与输入模式的概率分布趋于一致，即权重向量空间能反映输入模式的统计特征。这种自组织聚类过程是系统自主、无监督的条件下完成的。s 0 m 网络的竞争层各神经元竞争对输入模式的响应机会，最后仅一个神经元成为竞争的胜者，并对那些获胜神经元有关的各权重朝着更有利于它竞争的方向调整，即以获胜神经元为中心，对近邻的神经元表现出正向刺激侧反馈。这样，应用侧反馈原理，在每个获胜神经元附近形成一个“聚类区”，学习的结果总是使聚类区内各神经元的权重向量保持与输入向量逼近的趋势，从丽使具有相近特性的输入向量聚集在一起。嚣ia第三章传统的d n a 微阵列数据聚类方法3 自组织神经网络的聚类算法自组织网( s 0 m ) 学习算法具体步骤如下：( 1 ) 初始化s o m 网络。随机初始化网络的链接权向量晰，注意所有的n 个链接值初始向量应各不相同，n 是神经元的个数：确定学习率参数，7 的初始值；确定领域m 的初始值。领域m 是指以步骤( 3 ) 确定的获胜神经元七为中心，包含若干神经元的区域范围。( 2 ) 任选一个输入模式，提供给输入层。( 3 ) 以最小欧氏距离( 输入样本归一化后) 或最大相关的方式找出输入爿，后的得胜神经元，如式( 3 7 ) 。七= m i n a 咯 d ( 彤，x ) ( 3 7 )其中，嘶为输入与第i 个神经元的链接权值，j ，为输入样本，t 为胜利者。( 4 ) 以式( 3 8 ) 词整所有神经元的链接值向量咐d = 髋叼峭堋 善篙仔s ，其中，t 为学习迭代次数，叩为学习率参数，以是得胜者神经元的邻域，后两者都是学习迭代次数t 的函数。( 5 ) 重复步骤2 至步骤4 ，直到学习次数达到预先指定数目为止。分级聚类法【1 5 1 6 】1 条件及约定设待分类的模式特征矢量集为缸。，x ：，h ，g j ”表示第 次合并时的第f 类。2 基本思想首先视个模式各自成为一类，然后计算类与类之问的距离，选择距离最小的一对合并成一个新类，计算在新的类别分划下各类之间的距离再将距离最近的两类合并，直至所有模式聚成两类为止。3 算法步骤堡基于关系的d n a 微阵列数据聚类分析( 1 ) 初始分类。令女= o ，每个模式自成一类，即g ，( o = “) ( f = 1 ，2 ，) 。( 2 ) 计算各类间的距离嘎，由此生成一个对称的距离矩阵d = ( d f ，) ，m 类的个数，女表示合并的次数。( 初始时，”= | v ) 。( 3 ) 找出前一步求得的矩阵d n 中的最小元素，设它是g r 和g ，问的距离，将嘭”和g ( 两类合并成一类，于是产生新的聚类g p “，g r ”，令女= t + 1 ，m = 一1 ，m 为矩阵的行列数。( 4 ) 检查类的个数。如果类数m 大于2 ，转至( 2 ) ：否则，停止。如果某一循环中具有最小类间距离不止一个类对，则对应这些最小距离的类对可以同时合并。上述算法步骤给出了从j v 类至2 类的聚类过程，在实际应用中该算法也可将类间距离门限丁作为停止条件，当d ( 中最小阵元大于r ( 即d ( 中的任一元大于r ) 时，聚类过程停止：该算法也可将预定的类别数目作为停止条件，在类别合并过程中，类数等于预定值时，聚类过程停止。上述算法在归并的每次迭代过程中，距离矩阵的最小元素值不断地改变，如果有单调不减关系则称类间距离对并类具有单调性。展近距离法、最远距离法、平均法及离差平方和法等定义的类间距离都具有这个性质，而重心法没有这个性质。该算法的特点是在聚类过程中类心不断地调整，但一些模式一旦分划到某一聚类中就不再分划开。这类技术的另一个算法和上述算法过程相反，依据类的离差平方和递推公式按1 类至类进行分解，这里不作介绍了。聚类过程可以表示成一个树图。运用以上方法进行d n a 微阵列数据的聚类分析时，都是把表达谱向量作为聚类的特征矢量，把具有相似表达谱的基因( 样本) 聚为了一类。其特征模式是基因( 样本) 的个体特征，故可以认为是基于个体特征的聚类。第四章基于关系的d n a 微阵列数据聚类方法旦第四章基于关系的d n a 微阵列数据聚类方法4 1d n a 微阵列的数据形式及其前期处理d n a 微阵列的数据形式计算机读出的微阵列数据矩阵z ( | m ) 表示个基因在肘个样本( 或m 个不同的实验条件) 上的表达矩阵，形式为：x =而l 工1 2 。x l 吖工2 l 工2 2 。x k ，x k l x 荆( 4 - 1 )矩阵x 中每一行代表一个基因每列代表一张芯片( 样本) 上基因的数据。屯为基因f 在实验( 条件) - ，中的表达值。由基因芯片的实验原理，取为相对的荧光强度的比值：x ：l 。g ：鲁( 4 - 2 )jg，。为芯片上样本组基因( 红色荧光剂) 的强度，名为芯片上对照组基因( 绿色荧光剂) 的强度，取对数的目的在于克服以下差异：当基因高表达时，表达比在( j ，+o 。) ，而当基因低表达时，表达比在( 0 ，1 ) ，两者存在不对称性。基因可以看作是含有m 维实数的向量，而样本可以看作是维实数的向量。这意味着无论对基因聚类，还是样本聚类，都可以使用同样的聚类方法。数据前期处理在芯片数据的后期处理过程中可以对每张芯片内的全部基因的表达值做归一化处理，去除芯片的背景噪声。基因芯片实验中的变异来源很多，如荧光标记效率、基于关系的d n a 微阵列数据聚类分析扫描参数的设置、空间位置的差异等，都可能对基因表达水平的测量产生影响。因此，原始数据需经过标准化，以消除由于系统变异引起的误差，使得基因表达数据真实地反映测量样品的生物学差异。常规标准化包括：( 1 ) 均数或中位数中心化包括基因中心化和序列中心化。通常在实验中使用的共同参照样本与实验本身是独立的，而分析时也应该把参照样本表达水平的影响去除，基因中心化就可以实现这一目的。基因中心化是把每个基因在各实验中的表达值减去该基因在各实验中表达值的均数或中位数。基因中心化后的值就反映了该基因在不同序列下的变异。而当参照基因是实验的一部分，或要了解基因差异表达的程度时，不适宜进行中心化。序列中心化也很重要，可以消除某些类型的偏倚，如基因在芯片的不同空间位置造成的影响背景的差异造成的影响。( 2 ) 除以标准差其作用在于把数据的变异设定在与感兴趣的基因变异相同的范围内，放大弱信号而抑制强信号，但同时存在把噪声纳入真实信号中的危险。在进行基因聚类时。对于个基因在m 个时间点上的表达量矗，1 ，j ，1 ，m ，使用下式迸行归一化处理：毛：互丛( 4 3 )毛2 一竹。纠o 式中：h 和q 分别是托的均值和方差。把一个基因在各个时间点的表达量记作该基因的表达谱向量：t = lt 2 ，】l f ( 4 - 4 )在进行样本聚类时，可采用同样的方法进行数据的前期处理。总的来说，微阵列数据有下述三个特点：首先，由于检铡的仪器尺度的不同，我们一般需要对这些数据进行归一化处理。目前己经有几种较成熟的方法，见文献【9 】。其次，由于实验条件不可能完全一样，数据中不可避免地存在着一定的噪声。因此，在进行数据处理时，我们必须要考虑消除这些噪声。第三，由于实验第四章基于关系的d n a 微阵列数据聚类方法!成本的原因，并且每个芯片只能使用一次，样本个数比较少，特别是相对于成千上万的基因个数。在数据分析中，我们所面l 临的是个非常典型的高维小样本问题。4 2 基于关系的d n a 微阵列数据聚类方法从参考文献【l 】中，我们知道基因之间或样本之间的关系可以通过表达图谱的相关性来表示，通过构造关系网络来获得基因之间或样本之间的关系。受这种思想的启发，我们把经典的基于相关的d 咐a 微阵列数据聚类分析方法和图论理论相结合，提出了一种新颖的基因或样本聚类方法。同一功能组的基因或同一种疾病亚型的样本在其与其他基因或样本的关系上往往是相似的。故我们可以通过抽取基因之间或样本之间关系特征的方法来聚类基因或样本。在该方法中，我们首先让节点代表基因或样本，连边表示互表达，来构造出基因互表达网络：然后通过二值化基因互表达网络的连接权，而构成基因或样本的关系网络：再在关系网络中引入曲率( 此处曲率定义为任意多角关系的局部密度) 的概念，运用图论的知识抽取关系网络中节点周围的结构特征，它是所有多角关系的局部密度构成的密度向量，用以体现基因或样本之间的关系特征；最后把关系网络中具有相似结构特征的节点聚为一类，也即把关系特征作为聚类特征向量，在该关系特征空间进行基因或样本的聚类。本文方法具有聚类空间维数低的特点，很好地回避了维数灾难问题。我们把本文算法运用到y e a s t 和n c i 【2 0 l 基因数据上，这两个数据用已有的基因数据聚类算法都没能得到好的结果，而本文算法的实验结果显示聚类效果明显改善。4 2 1 关系网络的构建下面我们讨论基因关系网络( 用于基因聚类的关系网络) 的构建，样本关系网络( 用于样本聚类的关系网络) 的构建类似。基因互表达网络假设d m 微阵列数据集是由个基因在m 次不同的实验条件下( 或m 个不同基于关系的d n a 微阵列数据聚类分析的r m 样本上) 的表达水平组成，记为m 矩阵k 。，f - 1 ，= l ，m ，其每行表示一个基因在m 个样本上的表达水平( 表达图谱) 。我们关注基因之间相关性，通过基因& 和蜀的表达水平间的皮尔森( p e a r s o n ) 相关性( c o n 七l a t i o n ) r ( 七j )来度量它们之间的相关性：仪矿( 七，) =羔，( 五厂以) - ( 五，一h )吒q( 4 5 )其中，和盯。分别表示基因f 的均值和标准差，这样构造的j v 对称矩阵称为基因相关矩阵，描述了基因互表达关系。我们用节点代表基因，连边表示基因之间的相关性，边上的权值为如式( 4 5 ) 计算所得的相关系数r ( 屯，) 。这样构造出的网络称为基因互表达网络。基因关系网络在以上构建的基因互表达网络中，选择一个阈值t 。，【o ，1 1 ，如果。叭七，) 已，我们用l 来代替网络中连接边上的权值c 咿 ，) ，否则用。代替( 断开连接) ，这样就得到了基因关系网络g 。也可以理解为：通过阈值t 。，【0 ，l 】二值化相关矩阵获得了基因的邻接矩阵爿。如果节点代表基因，则一个有 ，个节点的图g 可被它的邻接矩阵爿所定义：若a ，= l ，则用一条边连接节点和节点岛，否则就不连接。这样我们以基因表达谱为联系纽带，运用经典的皮尔森相关系数来获得基因关系网络，图中的连接边反映了基因之间的相关性或相似性。4 2 2 关系特征的表征关系网络中节点周围结构特征的表征关系网络体现了基因之间或样本之间的关系，而要用数学量的方法表示出这种关系，还需要讨论关系特征的表征问题。由于基因或样本对应关系网络中的节点，而基因或样本之间的关系则对应关系网络中的节点的连接关系。一个节点与其他节点的连接关系就体现了对应基因或样本与其他基因或样本的关系，而这个第四章基于关系的d n a 微阵列数据聚类方法关系从关系网络上看就是图的结构特征。关系网络中，距离节点越远，与该节点的关系就越小。故基于距离越远，其关系越淡薄的前提条件我们只关注节点周围的结构特征，提出局部结构特征的概念：对于距离节点较远的连接关系，我们不予考虑。故要表征一个基因( 样本) 与其他基因( 样本) 的关系，即相应关系网络中个节点与其它节点的关系问题，这需要抽取对应节点周围的局部结构特征。下面我们通过在关系网络中抽取局部结构特征来表征基因之间或样本之间的关系特征。首先我们引入两个定义：节点的 一邻域、节点的( 所，盯) 一曲率。首先说明一下：图中两个节点间的距离是指连接这两个节点的最短路径长度：若两节点间没有路径连接，则这两个节点的距离为无穷大。定义1 在关系网络中，节点的向一邻域定义为到节点的距离不大于 的所有节点及其连接边的集合。其中， 0 ，且节点_ ，的峨域只有。即是其本身。j b称为节点的邻域大小。定义2 在关系网络中，节点_ ，的帆功一曲率( 脚，