相似性度量在基因表达聚类分析中的应用研究

1、论文发表专家一8 国学朮发叢网www,qikanwangnt相似性度量在基因表达聚类分析中的应用研究摘要：聚类分析是基因表达数据分析研究的主要技术之一，其算 法的基本出发点在于根据对象间相似度将对象划分为不同的类， 选 择适当的相似性度量准则是获得有效聚类结果的关键。 采用预处理 过的基因数据集在不同相似性度量准则下进行的不同聚类算法的 聚类分析，并得到聚类结果评价。其中算法本身的缺陷及距离相似 性度量的局限性都是影响结果评价的因素， 为了获得更有效的聚类 结果，改进相关聚类算法并提出了一种比例相似性度量准则。关键词：dna微阵列；聚类分析；相似性度量；基因表达dna微阵列(dna micro

2、array)技术的日益成熟导致了基因表达数据不断扩大，尤其在近十几年内更以指数形式增长。如何分析 和处理大量的基因表达数据，从中提取有用的生物学或医学信息，已成为后基因组时代研究的瓶颈12。由于基因芯片产生巨量的表达谱数据，数据挖掘技术已经被广泛的应用到基因表达谱的许 多方面，并取得成功。聚类分析是基因表达数据分析研究的主要技 术之一 2 3,并且作为一种有效的数据分析工具，已广泛地应用于图像处理、信息检索、数据挖掘等领域。目前，作为研究基因表达数据的主要技术之一的聚类分析算法有 很多种，如分层聚类(hierarchical clustering),k均俏聚类(k_means clusteri

3、ng)，自组织映射(self organizing maps, soms),主成分分析(principal component analysis,pca)等等。但由于匸交发表专家一LB 国学朮发叢网不同聚类算法， 甚至同一聚类算法使用不同参数， 一般都会产生不 同的聚类结果。因此，在对数据处理过的基因表达矩阵聚类分析时，选择合适的聚类相似性准则至关重要，同时也是获得合理、精确的 聚类结果的关键。1dna微阵列dna微阵列(dna microarray),也叫基因芯片。它将几十个到上 百万个不等的称之为探针的核苷酸序列固定在微小的(约1 cm2)玻璃或硅片等固体基片或膜上，该固定有探针的基片就称

4、之为dna微阵列。1.1基因表达数据的获得和表示在不同的实验环境条件或是不同的时间点，通过对基因芯片的扫 描，可以得到不同的实验数据， 所以这些数据是基因在一定实验条 件下或一段时间内的表达情况。经过对这些数据表达进行预处理和 标准化后，产生得到的微阵列数据也就是基因表达数据。微阵列基因表达数据主要为数值型，并以矩阵的方式存储，“行”为各个基因在不同环境条件下或不同时间点的表达情况，“列”是同一环境或时间下一个样本所有基因的表达谱。每一个元素代表第i个基因在第j个样本中的表达水平。1.2基因数据的研究现状与已经发展了几十年的结构基因组学相比，基因表达谱的生物信 息学仅处于起步阶段。现阶段基因芯

5、片所遇到的挑战并不在于表达论文发表专咅一01国SF/KJSB网wwwqikan训日ng.n巳t芯片实验技术本身，而是发展实验设计方法及数据分析4。实验 数据的预处理、标准化的方式，度量相似性的方式以及所选择的聚 类方法都会对分析结果产生影响。面对海量的基因数据，聚类算法 也不只是拘泥于传统的k均值算敢，层次聚类算法上，而是向着 多元化、专门化、复杂化的方向发展。2聚类相似性研究在日常生活中进行识别时也总是利用相似性概念，但是人们又很 难对“相似”或“不相似”做出明确的定量表述， 因此通常所说的 相似性只具有定性的或不确定的性质。 怎样对相似性概念给以明确 的定量表述是模式识别工作者要解决的任务

6、之一。2.1相似性度量两个样本间的相似性或离散度的测量称为相似性度量，简称相似 度。聚类通常按照样本间的相似性进行分组， 因此如何描述对象间 相似性是聚类分析的一个重要问题。聚类分析按照样本之间的亲疏远近程度进行分类。为了使类分得 合理，必须描述样本之间的亲疏远近程度。刻画聚类样本之间的亲 疏远近程度主要有以下2类函数：(1)距离函数。可以把每个样本看作高维空间中的一个点，进 而使用某种距离来表示样本之间的相似性，距离较近的样本性质较 相似，距离较远的样本则差异较大。(2)相似系数函数。两个样本愈相似，则相似系数值愈接近1;论文发表专家一m国学朮发叢网www.qikanwa ng.na样本愈不

7、相似，则相似系数值愈接近0。这样就可以使用相似系数值来刻画样本性质的相似性。d(i, j)是样本i和样本j之间相似性的量化表示，通常它是个非负的数值，一般地，距离函数有如下数学要求：(1)d(i, j)0:距离是个非负的数值；d(i, i)=0: 一个对象与自身的距离是0;d(i,j)=:d(j, i):距离函数具有对称性；d(i, j)d(j,h)+d(h,i):从对象i到对象j的直接距离不会大于途经任何其他对象h的距离(三角不等式)。如何选择相似性的度量方法是一个相当复杂的问题，因为相似度 的选择可以在很大程度上影响聚类算法的输出5。目前，有很多 相似性度量应用到基因表达数据分析当中。例如

8、：欧式距离、曼哈 坦距离、pearson相关系数、无中心pearson相关系数(对应两个 数据向量之间角度的余弦值)、spearman的排列相关系数等。在基 因表达数据聚类分析中，相似度普遍采用pears on相关系数和欧氏 距离6 7。在上述的几个相似性度量中，欧几里德距离和曼哈坦距离满足前 述4个要求。但是其他几个度量标准是基于相关系数的函数，它们并不完全满足距离函数的要求。通常用相关系数r定义距离d为:d=1-r。这样，所有的基于相关系数的相似性度量标准都使用这个定义而被转化为距离。但是注意这种距离函数并不满足二角不等2.1.1欧氏距离设有两个基因样本xi,xj，这两个样本可能在同一类中

9、，也可能 在不同的类中，因此，可以计算同一个类内样本与样本之间的距离，也可以计算属于不同类样本与样本之间的距离。欧氏距离测量空间 中两个点的绝对距离，故同时考虑了矢量的方向和幅度。 则基因样 本xi和xj之间的欧氏距离定义：di,j(xi,xj)=(xixj)t(xixj)二刀nk=1(xikxjk)2di,j越小，则两个样本距离越近，就越相似。2.1.2pearson相关系数pearson相关系数也是一种相似性测量， 大的相关系数意味着相 似性程度高。pearson相关系数从本质上说是测量两个表达矢量所 指方向的相似性。基因样本xi和xj之间的pearson相关系数定义:r(xi,yj)=刀

10、nm=1(xi,mi)(yj,myj)刀ni=1(xi,mi)2刀nj=1(yj,myj)2式中：i,yj分别为基因i和j在n个实验条件 下的平均表达水平；pearson相关系数取值于-1,1,两个相同的基因样本的相关系数为1,相关系数为0的两个基因样本被认为是 不相关的，而相关系数为-1的两个基因样本是反相关的8。2.2类相似性度量层次聚类算法有两个关键问题，首先是如何选取类间相似性度 量，它是由两tnii学朮友叢网wwwqikanwang.n论文发表专家一l类聚合为一类的依据；其次是聚合过程应该停留在哪匸交发表专家一m国学朮发叢网一级上，这与最终聚合成几类有关，也与聚类相似性有关。如前面

11、所述，根据不同的相似性度量标准(这里为某一距离标准或是相关 系数)， 可以有不同的层次聚类方法。在层次聚类算法中需要计算 两个类之间的相似度度量。常见的类间距相似性有最短距离法层次 聚类、最长距离法层次聚类、平均距离法层次聚类和重心法层次聚 类。(1)最短距离。规定两个类间相距最近的两个点之间的距离，为两个类的相似度。则简单连接定义为：di,j=mi n(di,j), dij=xixj,xi3i,xj3j式中dij是3i中任意一点与wj中任意一点 的欧式距离。(2)最长距离。规定两个类间相距最远的两个点之间的距离，为 两个类的相似度。则完全连接定义为：di,j=max(di,j), dij=x

12、ixj, xi3i,xj3j式中dij是3i中任意一点与3j中任意一点 的欧式距离。(3)平均距离。计算两类之间所有样品的距离，求和，取距离的均值作为两类间的距离。则平均连接定义为：di,j=1 ninj刀xi3ixj3jxixj式中ni,nj分别是3i,3j类中的样品的个数。(4)重心连接。各类中所有样品的平均值作为类的重心，用两类的重心间的距离作为两类距离，则重心连接定义为：di,j=x(3i)x(3j)式中：x(3i)=1 ni刀x3ix,x(3j) = 1njEx3j x分别是3i,3j类所有样品的平均值，ni,nj分别是3i、3j类匸交发表专家一LB 国学朮发叢网中的样品的个数。3聚

13、类算法研究对基因表达矩阵的分析，往往是比较矩阵行和列的相似性或差 别，如果发现两个行相似，贝何以推测它们对应的基因具有协同调 节和功能相关性。通过在不同水平的比较，可以发现哪些基因具有 不同的表达，并且可以研究不同化合物对它们的影响。聚类分析的 首要目标是将表达谱相似的基因归纳成类，然后聚焦于那些可能参 与某些生物过程的基因群，对这些类进行生物学注释，同时获得新 的生物学知识9。聚类分析技术是目前基因表达分析研究的主要计算技术之一，其 算法的基本出发点在于根据对象间相似度将对象划分为不同的类。指将一组样本按其相互间的相似程度归入几个子类，根本思想是确 定类群,使同一类内的各样本间差异最小，而不

14、同类间的差距最大。(1)层次聚类算法。 层次聚类算法可分为自上而下和自下而上 两种方向进行，根据不同的方向，层次聚类方法可以分为凝聚的层 次聚类和分裂的层次聚类。自底向上的层次方法是首先将每个聚类样本自成一个类，根据一 定的类间相似性度量标准计算两个类间的距离。然后反复地将距离 最近的两类合并为一类，并重新计算类间距离，直到达到某个终止 条件或只剩一个类。自上而下的层次方法是首先将所有聚类样本看成一类，然后按照论文发表专家一8 国学朮发舌网www,qikanwang.nEt一定的类间相似性度量进行不断分解为越来越小的聚类， 直到所有 聚类各成一类或满足某一终止条件。（2）k均值算法。k均值算法

15、把n个观察样本分成k个类， 必须先指定类数k和迭代次数或收敛条件。 开始先指定k个质心， 根据一定的相度性度量将每一个样本分配到最接近或”相似”的质心，形成一类，从而类内的相似性高，类间的相似性低。然后以每 一类的观察样本的均值矢量作为这一类的新质心，重新分配，反复 迭代直到类收敛（类的质心不变）或达到最大的迭代次数。（3） 自组织映射（soms）。自组织映射算法是一种高维可视化的无监督学习方法，描述输入数据集的原型矢量也称作为模型矢量或 权重矢量，同时将高维输入空间连续映射到低维的网格上。这个网 格由一定数目的神经元组成。给网格节点（神经元）赋予一定权重，来表示类的质心，计算一种距离确定各输

16、入矢量的匹配节点，并由输入矢量调整匹配节点及其邻域的权重。经过反复学习，模拟矢量 以有序的方式描述数据的概率分布。训练好的soms网格节点上已分配好相应的基因表达谱，节点的权重矢量代表相应类内表达谱的 平均，且相邻节点表示相似的类，类差别越大，其节点相距越远。3.1聚类算法结果分析3.1.1聚类结果评价不同的聚类算法应用于同一个基因表达数据时往往得到差别很 大的结果，怎样去判定聚类结果好坏。为了解决这个问题，人们提匸交发表专家一LB 国学朮发叢网出了好几种聚类指数来评价用聚类方法得出的划分结果。对基因表 达数据聚类结果的评价在实验当中是必不可少的，聚类结果评价主 要是指用客观的定量的方式对不同

17、的聚类算法在聚类过程中得到 的结果进行质量、可靠性的评价。外部确认是把实验得到的聚类结果与数据集的另一种分割的“金 标准”去比较来评价聚类结果。 因为有个已经事先分好的“金标准” 作为依据去比较聚类结果，所以外部评价比较有利于对数据集的聚 类质量进行独立无偏的评价。在基因表达数据聚类分析中，一般采 用rand指数(rand index)去评价聚类结果与外部“金标准”的一 致性。在基因表达聚类分析中，rand指数(rand index)被广泛用来评价 聚类结果与外部标准的一致性。设s与r为一个数据集的两种独立 划分，若a为s和r中都属于同一类的个体对数，b为s中属于同 一类而v中不属同一类的个体

18、对数，c为r中属于同一类而s中不 属于同一类的个体对数，d为s和r中都不属于同一类的个体对数，则rand指数定义为(a+d)/(a+b+c+d)。如果两种划分的聚类数不相 同，rand指数也能很好的检测不同划分的吻合度。rand指数在01之间，其数值越大，两种划分的一致程度越高。当rand指数为1时，表示两种聚类完全相同。3.1.2结果与分析论文发表专家一L8 国学朮发叢网由于分析各种聚类算法的实际效果需要已知类别的基因的表达数据，所以本文选用了酵母孢子化数据集（spor）。本文选用在减数 分裂早期、中期和末期的10个时间点测量了每一条基因mrna转录 水平变化，并对比研究了生长期细胞ndt8

19、0异常表达和缺失导致的 基因表达变化，共得到10个实验样品的表达。 选取其中分别属于6个不重叠功能表达模式的161条基因表达谱组成数据集（记为spor数据集，161X10表达矩阵），并以这6个功能类作为外部标准类。在经过以2为底对数化预处理之后，此数据集在进行聚类结果分析。如表1所示，该数据集经过对数化预处理之后，分别以pearson相关系数和欧氏距离作为相似性度量准则进行多种聚类算法得到 的rand指数。表1不同相似性度量下不同聚类算法的rand指数聚类方法pears on相关系数欧氏距离最短距离法层次聚类0.00800.012 4最长距离法层次聚类0.395 80.337 7平均距离法层次

20、聚 类0.39770.173 3重心法层次聚类0.415 40.051 1k均俏聚类0.403 20.408 7自组织映射聚类0.404 50.467 4由表1可得到最短距离法的层次聚类的结果明显较差于其他三类距离层次聚类。k均個聚类算法11以欧式丽肉作为相似性征则的 聚类结果稍好于pears on相关系数的聚类结果。自组织映射聚类中 的以欧式距离作为相似性准则的聚类结果明显更优。总体而言，对 两种不同的相似性准则的结果，k均俏聚类和soms聚类结果显著论文发表专家一m国学朮发叢网www,qikan训日优于分层聚类，soms聚类结果稍好于k得到这种结论的原因有很多种，其中聚类算法本身和相似性度

21、量都存在的问题：层次聚类虽然方法简单，但有时在选择分裂或合并点时都有困难 存在，因为一旦将一组个体分裂或合并，后续的类将在新类的基础 上产生，而不能取消己经完成的分裂或合并，也不能在类间对个体 进行调整。层次聚类分析不适于基因表达谱可能相似的复杂数据。在k均借聚艾算法在开始疋陵初始化血心确定聚类数不同的初始化质心方法得到不同的聚类结果，由于有多种初始化k类的可能,故难于选择最优化的结果。对有些实验，无法确定预期的类数， 而且也没有很好的方法来选择算法应该运行的确切迭代次数。此外k均他算法对噪声和京用数据比较械感，因为这类数据口能会影 响到各个聚类的均值。自组织映射聚类算法中节点的初始权重是随机

22、产生的，使得算法 结果有一定的不确定性。网络连接权的初始状态、算法中的参数选 择对网络的收敛性能有较大影响。当输入数据较少时，训练的结果 通常依赖于样本的输入顺序。本文中应用的相似性度量是通过样本间的距离确定的。然而数据 源中的两个对象实际中是否相似与这两个对象之间的距离并不是 完全对应的。 对象间的距离表示的是对象的相近程度，而相似不仅 依赖于对象间的相近程度，还依赖于对象内在的性质，而距离不能论文发表专乐一B 国学朮发丢网反映这样的特征。3.2聚类算法问题分析基于上述层次聚类不适合处理大量复杂数据，k均個力法屮，必须预先选择类数作为先验值，soms聚类算法对初始输入参数的敏 感性和可能达到

23、局部最小10,相似性度量准则的局限性等问题。 可以做出通过尝试一些新的方法来解决这些问题。首先，不能局限 在传统的聚类方法中，可以采用一些改进算法，如模糊k均俏算法，通过soms算法对基因表达数据进行聚类，再用层次聚类将每个 类对应的神经元权值二次聚类等新的算法， 都在一定程度上克服原 有的缺陷提高了基因聚类的效能。其次，需提出一种更确切的反映 对象相似的计算方法，并且要求简单易行。在某些情况下，如果两 个属性的比例来代替距离表示对象的相似性，将更准确地反映事物 间的相似程度。图1是包含一个数据集中4个基因在5个属性上的 表达值。图1模式相似性示意图可以看出，图1中任何两个基因的距离都 比较远

24、，如果用基于距离的聚类算法不可能把4条基因聚类在同一类中，但实际上，这4个模式表现出的是一种非常近似的“平行” 模式。在这种情况下，两个属性的比例将更准确地反映事物间的相 似程度。利用距离定义的相似度，当两个对象越接近，即距离越接 近于0,相似度越大。而基于比例的相似度定义中，比例越接近于1,二者的相似度越大。论文发表专家一m国手朮友叢网4结语综上所述，基因表达数据分析研究的主要技术是聚类分析。而在 进行聚类算法分析数据时，作为聚类参数的相似性度量准则的选 择，是对获得聚类结果评价的一个重要的因素。在聚类分析中主要 采用pears on相关系数和欧式距离作为相似性度量准则。 本文采用 预处理过

25、的基因表达数据集试验结果显示相似度的选择对结果影 响显著，不同的聚类算法需要选择不同的相似性度量准则才能获得更有效的聚类结果。针对距离作为相似性度量准则的局限，提出一 种精确的相似性计算方法：基于比例的模式相似性度量。从模式相 似性的角度聚类生物数据，逐渐成为近年来数据挖掘在生物信息中 的研究焦点。参考文献1brahma a, vilo j. gene expression data analysisj.febs letters, 2000, 480(1): 172jiang d, tang c, zhang a. clusteranalysis for gene expressi on data j. ieee tra nsacti ons on kno wledgeanddata engin eeri ng, 2004, 16(11): 13703amir b,friedman n,yakhini z. class