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

相似性度量在基因表达聚类分析中的应用研究摘要：聚类分析是基因表达数据分析研究的主要技术之一，其算法的基本出发点在于根据对象间相似度将对象划分为不同的类，选择适当的相似性度量准则是获得有效聚类结果的关键。采用预处理过的基因数据集在不同相似性度量准则下进行的不同聚类算法的聚类分析，并得到聚类结果评价。其中算法本身的缺陷及距离相似性度量的局限性都是影响结果评价的因素，为了获得更有效的聚类结果，改进相关聚类算法并提出了一种比例相似性度量准则。关键词：dna微阵列； 聚类分析； 相似性度量； 基因表达 dna 微阵列(dna microarray) 技术的日益成熟导致了基因表达数据不断扩大,尤其在近十几年内更以指数形式增长。如何分析和处理大量的基因表达数据，从中提取有用的生物学或医学信息，已成为后基因组时代研究的瓶颈12。由于基因芯片产生巨量的表达谱数据，数据挖掘技术已经被广泛的应用到基因表达谱的许多方面，并取得成功。聚类分析是基因表达数据分析研究的主要技术之一23，并且作为一种有效的数据分析工具, 已广泛地应用于图像处理、信息检索、数据挖掘等领域。目前，作为研究基因表达数据的主要技术之一的聚类分析算法有很多种，如分层聚类(hierarchical clustering)，k均值聚类(k_means clustering)，自组织映射(self organizing maps，soms)，主成分分析(principal component analysis，pca)等等。但由于不同聚类算法，甚至同一聚类算法使用不同参数，一般都会产生不同的聚类结果。因此，在对数据处理过的基因表达矩阵聚类分析时，选择合适的聚类相似性准则至关重要，同时也是获得合理、精确的聚类结果的关键。1dna微阵列dna微阵列（dna microarray）,也叫基因芯片。它将几十个到上百万个不等的称之为探针的核苷酸序列固定在微小的（约1 cm2）玻璃或硅片等固体基片或膜上，该固定有探针的基片就称之为dna微阵列。1.1基因表达数据的获得和表示在不同的实验环境条件或是不同的时间点，通过对基因芯片的扫描，可以得到不同的实验数据，所以这些数据是基因在一定实验条件下或一段时间内的表达情况。经过对这些数据表达进行预处理和标准化后，产生得到的微阵列数据也就是基因表达数据。微阵列基因表达数据主要为数值型，并以矩阵的方式存储，“行”为各个基因在不同环境条件下或不同时间点的表达情况，“列”是同一环境或时间下一个样本所有基因的表达谱。每一个元素代表第i个基因在第j个样本中的表达水平。1.2基因数据的研究现状与已经发展了几十年的结构基因组学相比,基因表达谱的生物信息学仅处于起步阶段。现阶段基因芯片所遇到的挑战并不在于表达芯片实验技术本身,而是发展实验设计方法及数据分析4。实验数据的预处理、标准化的方式，度量相似性的方式以及所选择的聚类方法都会对分析结果产生影响。面对海量的基因数据，聚类算法也不只是拘泥于传统的k均值算法，层次聚类算法上，而是向着多元化、专门化、复杂化的方向发展。2聚类相似性研究在日常生活中进行识别时也总是利用相似性概念，但是人们又很难对“相似”或“不相似”做出明确的定量表述，因此通常所说的相似性只具有定性的或不确定的性质。怎样对相似性概念给以明确的定量表述是模式识别工作者要解决的任务之一。2.1相似性度量两个样本间的相似性或离散度的测量称为相似性度量，简称相似度。聚类通常按照样本间的相似性进行分组，因此如何描述对象间相似性是聚类分析的一个重要问题。聚类分析按照样本之间的亲疏远近程度进行分类。为了使类分得合理，必须描述样本之间的亲疏远近程度。刻画聚类样本之间的亲疏远近程度主要有以下2类函数：（1） 距离函数。可以把每个样本看作高维空间中的一个点，进而使用某种距离来表示样本之间的相似性，距离较近的样本性质较相似，距离较远的样本则差异较大。（2） 相似系数函数。两个样本愈相似，则相似系数值愈接近1；样本愈不相似，则相似系数值愈接近0。这样就可以使用相似系数值来刻画样本性质的相似性。d(i, j)是样本i和样本j之间相似性的量化表示，通常它是一个非负的数值，一般地，距离函数有如下数学要求：（1） d(i, j)0：距离是一个非负的数值；（2） d(i, i)=0：一个对象与自身的距离是0；（3） d(i, j)= d(j, i)：距离函数具有对称性；（4） d(i, j)d(j,h)+d(h,i)：从对象i到对象j的直接距离不会大于途经任何其他对象h的距离（三角不等式）。如何选择相似性的度量方法是一个相当复杂的问题，因为相似度的选择可以在很大程度上影响聚类算法的输出5。目前，有很多相似性度量应用到基因表达数据分析当中。例如：欧式距离、曼哈坦距离、pearson相关系数、无中心pearson相关系数（对应两个数据向量之间角度的余弦值）、spearman的排列相关系数等。在基因表达数据聚类分析中,相似度普遍采用pearson相关系数和欧氏距离67。在上述的几个相似性度量中，欧几里德距离和曼哈坦距离满足前述4个要求。但是其他几个度量标准是基于相关系数的函数，它们并不完全满足距离函数的要求。通常用相关系数r定义距离d为：d=1-r。这样，所有的基于相关系数的相似性度量标准都使用这个定义而被转化为距离。但是注意这种距离函数并不满足三角不等式。2.1.1欧氏距离设有两个基因样本xi，xj，这两个样本可能在同一类中，也可能在不同的类中，因此，可以计算同一个类内样本与样本之间的距离，也可以计算属于不同类样本与样本之间的距离。欧氏距离测量空间中两个点的绝对距离,故同时考虑了矢量的方向和幅度。则基因样本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)=nm=1(xi,mi)(yj,myj)ni=1(xi,mi)2nj=1(yj,myj)2式中：i，yj分别为基因i和j在n个实验条件下的平均表达水平；pearson相关系数取值于-1,1，两个相同的基因样本的相关系数为1，相关系数为0的两个基因样本被认为是不相关的，而相关系数为-1的两个基因样本是反相关的8。2.2类相似性度量层次聚类算法有两个关键问题，首先是如何选取类间相似性度量，它是由两类聚合为一类的依据；其次是聚合过程应该停留在哪一级上，这与最终聚合成几类有关，也与聚类相似性有关。如前面所述，根据不同的相似性度量标准(这里为某一距离标准或是相关系数)，可以有不同的层次聚类方法。在层次聚类算法中需要计算两个类之间的相似度度量。常见的类间距相似性有最短距离法层次聚类、最长距离法层次聚类、平均距离法层次聚类和重心法层次聚类。(1) 最短距离。规定两个类间相距最近的两个点之间的距离，为两个类的相似度。则简单连接定义为：di,j=min(di,j), dij=xixj,xii,xjj式中dij是i中任意一点与j中任意一点的欧式距离。(2) 最长距离。规定两个类间相距最远的两个点之间的距离，为两个类的相似度。则完全连接定义为：di,j=max(di,j), dij=xixj, xii,xjj式中dij是i中任意一点与j中任意一点的欧式距离。(3) 平均距离。计算两类之间所有样品的距离，求和，取距离的均值作为两类间的距离。则平均连接定义为：di,j=1ninjxiixjjxixj式中ni，nj分别是i，j类中的样品的个数。(4) 重心连接。各类中所有样品的平均值作为类的重心，用两类的重心间的距离作为两类距离，则重心连接定义为：di,j=x(i)x(j)式中：x(i)=1nixix，x(j) = 1nj xj x分别是i，j类所有样品的平均值，ni，nj分别是i、j类中的样品的个数。3聚类算法研究对基因表达矩阵的分析，往往是比较矩阵行和列的相似性或差别，如果发现两个行相似，则可以推测它们对应的基因具有协同调节和功能相关性。通过在不同水平的比较，可以发现哪些基因具有不同的表达，并且可以研究不同化合物对它们的影响。聚类分析的首要目标是将表达谱相似的基因归纳成类,然后聚焦于那些可能参与某些生物过程的基因群,对这些类进行生物学注释,同时获得新的生物学知识9。聚类分析技术是目前基因表达分析研究的主要计算技术之一，其算法的基本出发点在于根据对象间相似度将对象划分为不同的类。指将一组样本按其相互间的相似程度归入几个子类,根本思想是确定类群,使同一类内的各样本间差异最小,而不同类间的差距最大。（1） 层次聚类算法。层次聚类算法可分为自上而下和自下而上两种方向进行，根据不同的方向，层次聚类方法可以分为凝聚的层次聚类和分裂的层次聚类。自底向上的层次方法是首先将每个聚类样本自成一个类，根据一定的类间相似性度量标准计算两个类间的距离。然后反复地将距离最近的两类合并为一类,并重新计算类间距离,直到达到某个终止条件或只剩一个类。自上而下的层次方法是首先将所有聚类样本看成一类，然后按照一定的类间相似性度量进行不断分解为越来越小的聚类，直到所有聚类各成一类或满足某一终止条件。（2） k均值算法。k均值算法把n个观察样本分成k个类，必须先指定类数k和迭代次数或收敛条件。 开始先指定k个质心，根据一定的相度性度量将每一个样本分配到最接近或”相似”的质心，形成一类，从而类内的相似性高，类间的相似性低。然后以每一类的观察样本的均值矢量作为这一类的新质心，重新分配，反复迭代直到类收敛(类的质心不变)或达到最大的迭代次数。（3） 自组织映射(soms)。自组织映射算法是一种高维可视化的无监督学习方法，描述输入数据集的原型矢量也称作为模型矢量或权重矢量，同时将高维输入空间连续映射到低维的网格上。这个网格由一定数目的神经元组成。给网格节点(神经元)赋予一定权重,来表示类的质心，计算一种距离确定各输入矢量的匹配节点,并由输入矢量调整匹配节点及其邻域的权重。经过反复学习,模拟矢量以有序的方式描述数据的概率分布。训练好的soms网格节点上已分配好相应的基因表达谱，节点的权重矢量代表相应类内表达谱的平均，且相邻节点表示相似的类，类差别越大，其节点相距越远。3.1聚类算法结果分析3.1.1聚类结果评价不同的聚类算法应用于同一个基因表达数据时往往得到差别很大的结果，怎样去判定聚类结果好坏。为了解决这个问题，人们提出了好几种聚类指数来评价用聚类方法得出的划分结果。对基因表达数据聚类结果的评价在实验当中是必不可少的，聚类结果评价主要是指用客观的定量的方式对不同的聚类算法在聚类过程中得到的结果进行质量、可靠性的评价。外部确认是把实验得到的聚类结果与数据集的另一种分割的“金标准”去比较来评价聚类结果。因为有个已经事先分好的“金标准”作为依据去比较聚类结果，所以外部评价比较有利于对数据集的聚类质量进行独立无偏的评价。在基因表达数据聚类分析中，一般采用rand指数(rand index)去评价聚类结果与外部“金标准”的一致性。在基因表达聚类分析中，rand指数(rand index)被广泛用来评价聚类结果与外部标准的一致性。设s与r为一个数据集的两种独立划分，若a为s和r中都属于同一类的个体对数，b为s中属于同一类而v中不属同一类的个体对数，c为r中属于同一类而s中不属于同一类的个体对数，d为s和r中都不属于同一类的个体对数，则rand指数定义为(a+d)/(a+b+c+d)。如果两种划分的聚类数不相同，rand指数也能很好的检测不同划分的吻合度。rand指数在01之间，其数值越大，两种划分的一致程度越高。当rand指数为1时，表示两种聚类完全相同。3.1.2结果与分析由于分析各种聚类算法的实际效果需要已知类别的基因的表达数据，所以本文选用了酵母孢子化数据集(spor)。本文选用在减数分裂早期、中期和末期的10个时间点测量了每一条基因mrna转录水平变化，并对比研究了生长期细胞ndt80异常表达和缺失导致的基因表达变化，共得到10个实验样品的表达。选取其中分别属于6个不重叠功能表达模式的161条基因表达谱组成数据集(记为spor数据集，16110表达矩阵)，并以这6个功能类作为外部标准类。在经过以2为底对数化预处理之后，此数据集在进行聚类结果分析。如表1所示，该数据集经过对数化预处理之后，分别以pearson相关系数和欧氏距离作为相似性度量准则进行多种聚类算法得到的rand指数。表1 不同相似性度量下不同聚类算法的rand指数聚类方法pearson相关系数欧氏距离最短距离法层次聚类0.008 00.012 4最长距离法层次聚类0.395 80.337 7平均距离法层次聚类0.397 70.173 3重心法层次聚类0.415 40.051 1k均值聚类0.403 20.408 7自组织映射聚类0.404 50.467 4由表1可得到最短距离法的层次聚类的结果明显较差于其他三类距离层次聚类。k均值聚类算法中以欧式距离作为相似性准则的聚类结果稍好于pearson相关系数的聚类结果。自组织映射聚类中的以欧式距离作为相似性准则的聚类结果明显更优。总体而言，对两种不同的相似性准则的结果，k均值聚类和soms聚类结果显著优于分层聚类，soms聚类结果稍好于k均值聚类。得到这种结论的原因有很多种，其中聚类算法本身和相似性度量都存在的问题：层次聚类虽然方法简单，但有时在选择分裂或合并点时都有困难存在，因为一旦将一组个体分裂或合并，后续的类将在新类的基础上产生，而不能取消己经完成的分裂或合并，也不能在类间对个体进行调整。层次聚类分析不适于基因表达谱可能相似的复杂数据。在k均值聚类算法在开始时要初始化质心确定聚类数。不同的初始化质心方法得到不同的聚类结果，由于有多种初始化k类的可能,故难于选择最优化的结果。对有些实验,无法确定预期的类数，而且也没有很好的方法来选择算法应该运行的确切迭代次数。此外k均值算法对噪声和异常数据比较敏感，因为这类数据可能会影响到各个聚类的均值。自组织映射聚类算法中节点的初始权重是随机产生的，使得算法结果有一定的不确定性。网络连接权的初始状态、算法中的参数选择对网络的收敛性能有较大影响。当输入数据较少时，训练的结果通常依赖于样本的输入顺序。本文中应用的相似性度量是通过样本间的距离确定的。然而数据源中的两个对象实际中是否相似与这两个对象之间的距离并不是完全对应的。对象间的距离表示的是对象的相近程度，而相似不仅依赖于对象间的相近程度，还依赖于对象内在的性质，而距离不能反映这样的特征。3.2聚类算法问题分析基于上述层次聚类不适合处理大量复杂数据，k均值方法中，必须预先选择类数作为先验值，soms聚类算法对初始输入参数的敏感性和可能达到局部最小10，相似性度量准则的局限性等问题。可以做出通过尝试一些新的方法来解决这些问题。首先，不能局限在传统的聚类方法中，可以采用一些改进算法，如模糊k均值算法，通过soms算法对基因表达数据进行聚类,再用层次聚类将每个类对应的神经元权值二次聚类等新的算法，都在一定程度上克服原有的缺陷提高了基因聚类的效能。其次，需提出一种更确切的反映对象相似的计算方法，并且要求简单易行。在某些情况下，如果两个属性的比例来代替距离表示对象的相似性，将更准确地反映事物间的相似程度。图1是包含一个数据集中4个基因在5个属性上的表达值。图1模式相似性示意图可以看出，图1中任何两个基因的距离都比较远，如果用基于距离的聚类算法不可能把4条基因聚类在同一类中，但实际上，这4个模式表现出的是一种非常近似的“平行”模式。在这种情况下，两个属性的比例将更准确地反映事物间的相似程度。利用距离定义的相似度，当两个对象越接近，即距离越接近于0，相似度越大。而基于比例的相似度定义中，比例越接近于1，二者的相似度越大。4结语综上所述，基因表达数据分析研究的主要技术是聚类分析。而在进行聚类算法分析数据时，作为聚类参数的相似性度量准则的选择，是对获得聚类结果评价的一个重要的因素。在聚类分析中主要采用pearson相关系数和欧式距离作为相似性度量准则。本文采用预处理过的基因表达数据集试验结果显示相似度的选择对结果影响显著,不同的聚类算法需要选择不同的相似性度量准则才能获得更有效的聚类结果。针对距离作为相似性度量准则的局限，提出一种精确的相似性计算方法：基于比例的模式相似性度量。从模式相似性的角度聚类生物数据，逐渐成为近年来数据挖掘在生物信息中的研究焦点。参考文献1brahma a, vilo j. gene expression data analysis j.febs letters, 2000, 480(1): 1724.2jiang d, tang c, zhang a. cluster analysis for gene expression data j. ieee transactions on knowledge and data engineering, 2004, 16(11): 13701386.3amir b，friedman n，yakhini z. class discovery in gene