基于最小编码长度的基因数据聚类.doc

基于最小编码长度的基因数据聚类汪雪红1、焦清局2、常盼盼1、黄继风1 (1。上海师范大学信息与机电工程学院, 上海 200234；2.上海交通大学自动化系和系统控制和信息处理国家重点实验室，上海，200240)摘 要：在本文我们将基因数据的聚类看成是高维混合数据的聚类。对基因数据进行预处理之后，再利用主成分分析将基因数据降维，降维后基因数据呈类高斯分布。这样分布的基因数据能够被有效的聚类通过一个简单的基于有损数据压缩的聚类算法，此算法根据聚类后使基因的总体编码长度最小原则对基因进行聚类。我们分别利用本算法与传统聚类算法对酵母和拟南芥基因数据进行聚类，并通过基因聚类内部评价和功能评价来验证此算法的有效性。实验结果说明该算法优于现有聚类算法。关键词：基因聚类 有损压缩 高斯分布 最小编码长度Based on the minimum length coding genetic data clustering WANG Xue-Hong, JIAO Qing-Ju, CHANG Pan-Pan, HUANG Ji-Feng (1College of Information, Mechanical and Electrical Engineering, Shanghai Normal University, Shanghai 200234;2. Department of Automation, Shanghai Jiao Tong University, and Key Laboratory of System Control and Information Processing, Ministry of Education of China, Shanghai,200240)Abstract: In this paper we see the genetic data clustering as high dimension mixed data clustering. After preprocessing genetic data , we use principal component analysis to reduce genetic data dimensionality, when genetic data showing class Gaussian distribution. This distribution of genetic data can be clustered effectivly through a lossy data compression approach,which based on a simple clustering algorithm .This algorithm can achive its best clustering result whenthelengthofthecodesofencodingclusted genesreachitsminimumvalue. We use this algorithm and the traditional clustering algorithms for yeast and Arabidopsis gene data clustering , and through genetic clustering internal evaluation and function evaluation to verify the effectiveness of the algorithm. Experimental results show that the algorithm is the existing clustering algorithmsKeywords: Genetic clustering; lossy compression; Gaussian distribution; Minimum length coding; 1前言基因数据都是高维数据，且数量大、生物网络复杂，如何从大量的基因数据中得到有用的信息是目前面临的主要问题。聚类分析作为一种有效的数据分析工具，在基因表达数据的分析中已有广泛的应用。对基因进行聚类分析的主要任务是将功能相关的基因按表达谱的相似程度归纳成共同表达类别，因此根据同一类中已知基因的功能可以提示未知功能基因的可能作用。并且也可以对属于同一个类的基因进行功能分类、功能通路和信号通路分析，增加了这些基因的各种功能注释。基因表达聚类分析也能判别细胞所处状态或组织类型。目前有很多聚类算法已经应用到基因表达分析，例如分层聚类（hierarchial clustering）,K-均值聚类 (K-means clustering),以及模糊C-均值（Fuzzy C - Means ,简称FCM）等。这些聚类算法的共同缺点是需要事先给定聚类数，主观性很大。层次聚类方法简单直接，易于理解和应用，但它适用于反映真正的层次树结构，而基因表达数据的产生往往并非如此。而且其时间复杂度大，与所分析的表达谱数目的平方成正比，因此层次聚类不适用于高维基因表达数据集。K均值算法聚类收敛速度快 ,但对聚类数目敏感、易陷于局部最优，且比较适合于超球形数据的聚类,因此实际应用中会有一定的局限性。相对于K 均值算法,FCM对于聚类数目不是太敏感, 但是该算法也有很多缺陷，一方面参数太多,难于设置, 如隶属度的阈值, 在很多情况下很难由用户手工确定最好的阈值。另外对于数据较多和聚类数目较大时, FCM 算法的性能明显下降。123鉴于以上考虑 ,我们提出了一种全新的基因聚类方法。 其特点是: 不需要事先指定聚类数，算法可以自动确定。只有一个参数需要设置。样本的聚类不是根据相似性度量，因此避免了选择一个合适的标准指标，例如：层次聚类偏好于pearson相关系数准则，K均值聚类以Euclidean距离为相似性度量准则。4我们把本文算法运用到酵母和拟南芥两种基因数据上,这两种数据用以上传统的基因数据聚类算法都没能得到好的结果 ,而本文算法的实验结果显示聚类效果明显改善。2 算法2.1算法思想在本文我们用一种简单且有效地聚类算法，这个算法特别适合处理不知道数量的可能退化的高斯数据。5本段我们给出这个方法的简要综述以及相关的聚类算法。新的聚类算法遵循有损最小描述长度原理：原理1（通过有损压缩的数据分割）对于一个给定的率失真，我们定义最优的分割是对于分割后数据的编码需要的位数最少。为了应用这个原理到我们的问题，首先要解决的是对于一个混合高斯分布数据编码长度的准确测量。我们首先定义一个简单高斯数据的编码长度，假设给定一个随机的向量vRD,R是一个多元高斯分布N(，),我们希望对其进行编码是它能恢复到一个给定的率失真2,也就是Ev-v 22。根据信息论6，对于v编码所需要的位数可以根据高斯的率失真函数给出：R()=12log2det(I+D2) (1)其中I是单位矩阵，是协方差。现在考虑一个含有N个样品的样品集V=（v1,v2,vN）RD*N,让1NI=1Nvi, v=v-11*N, =1NvvT是一个估计，那么率失真函数R()为R= 12log2det(I+DN2vvT) (2)对V中N个向量的编码要求NR(V)位数，另外编码需要密码本，且密码本对于数据V是自适应的，因此需要用D R(V)位数代表。对于非零均值的数据，我们需要额外的D2log2(1+T2)位数去编码均值。因此对于向量V的编码所需总位数为L(V)=N+DN log2det(I+DN2vvT)+ D2log2(1+T2) (3)尽管上面的公式来自于高斯数据的推导，但是它也给出了任何一个子空间的有限数量的样本的编码长度的上限，例如一个退化的高斯分布。详细的证明在文献1如果V是一些独立高斯子集的并集，即V=W1 W2WK那么对V编码所需的总位数为LS(W1,。,Wk)i=1kLWi-Wilog2(Wi/N) (4)其中Wi是子集Wi含有样本的数目，i=1kWilog2(Wi/N)是编码在k组m个样本隶属度所需要的位数（无损,通常用哈弗曼编码）。2.2 算法描述基因数据经过主成分分析后，统计是一个类高斯分布（可能稍有退化），因此基因数据编码长度的计算可以利用上面的公式。利用原理1，为了找到最优的分割，原则上是应该计算基因数据所有可能分割的编码长度，但是基因数据相当大，不可能实现。为了找到编码长度最小的聚类方式，本文算法描述如下（算法1）（1） 每个基因分别为一类，并计算每个基因单独编码长度。（2） 分别计算两两（比如w1,w2）基因合并为一类后编码长度，并用这两个基因单独编码的长度和减去合并后编码（=L(w1,w2)-L(w1w2)） 并对从高到低进行排序。（3） 合并中排在第一位的两个基因（比如w1,w2），也就是按照编码减少最快的聚在一起。然后将L(w1w2)放在L(w1)中，L(w2)清零。重复（2）直到小于零。2.3 率失真的选择利用公式4计算编码长度需要确定率失真。本文利用基因数据聚类常用的评价函数Silhouette 指数和FOM12789来选择率失真。FOM是Yeung 等基于 Jackknife 方法提出的一种专门用于基因表达数据聚类分析的内部确认方法。FOM测量的基本思想是：从给定数据集中排除一个实验，用其他实验下的数据来聚类基因，再检测这一被排除实验下基因表达水平的类内相似性，以此来估计聚类算法的预测能力。从直观上看，若聚类结果中同一类的基因在未用来产生类的那个实验下有相似的表达水平，则说明该聚类结果有一定的生物学显著性。FOM越小,则用类平均来估计表达值的误差越小,聚类结果越稳定,聚类效果越高。Silhouettes 指数基于每一样本到其所属类距离与到邻近类距离的比值定义，它采用类间离散度和类内紧致性来评价聚类结果。Silhouette越大说明聚类正确率越高、聚类质量越好，反之越差。从原理上说，Silhouette 指数可用来预测数据结构的类数，Silhouette 指数最大的划分被认为是最优的。具体算法如下（算法2）（1） 将率失真从0.01到1间隔0.01循环,利用聚类算法1对基因进行聚类.然后对每一次聚类结果分别计算Silhouette 指数和FOM。本文对部分酵母和拟南芥基因进行聚类，结果如图2.1、2.2所示。（2） 综合考虑Silhouette 指数和FOM选择合适的。由图2.1可以看出，当率失真为0.13,0.14,0.15等时Silhouette 指数最大，结合fom最小的原则，本文酵母基因数据选择为0.15，同理根据图2.2拟南芥基因数据率失真选择为0.77。如图红色圆圈所示。（3） 利用选定的率失真对基因数据进行聚类。图2.1酵母数据中Silhouette 指数和FOM与率失真关系曲线图2.2 拟南芥数据中Silhouette 指数和FOM与率失真关系曲线3实验步骤与分析 3.1 实验步骤 实验流程图如下图3.1所示：基因数据（酵母或拟南芥） 数据预处理（滤波和标准化）对数据进行主成分分析 选择合适的率失真利用本文算法对数据进行聚类对聚类结果进行比较评价 图3.1试验流程(1) 本文酵母数据是利用Matlab自带的(6400*7)。拟南芥数据资源(TAIR)提供拟南芥各方面资源。网上 (/home/tair/pathways/)下载了所有拟南芥代谢通路数据。并取部分进行实验。(2) 在对数据进行聚类、分析之前必须对原始数据进行预处理，处理内容主要包括清除不完整数据、合并重复数据、估计缺失数据、删除在多次测量中变化不明显的基因、以及标准化处理。101112因为本文主要讨论聚类算法，预处理不做详细说明。(3) 因为基因数据是高维数据，需要对基因数据进行主成分分析对其进行降维，降维后数据保留源数据百分之九十以上信息，而且大大节约计算时间。13(4) 利用算法2选择的率失真根据算法1对处理后的基因数据进行聚类。(5) 为了验证本文算法的性能和聚类效果，分别从内部评价，功能评价，可视化来证明本文算法的有效性。3.2验结果与分析评价基因芯片数据的聚类结果可以从两个方面入手：一是从基因的分子功能入手观察聚类算法是否将分子功能相似的基因尽可能地聚到同一个类中；二是从数据的数学特征入手考察聚类算法是否将表达模式相似的基因尽可能地聚到同一个类中。第一种方法是最理想的方法。33.2.1聚类结果的内部评价正如上文所表述Silhouette 指数和FOM 测量能较好地反映聚类算法的性能和聚类结果的质量。因此本文采用这两个指标对聚类结果进行评价。表1 各种聚类算法对酵母基因数据(310*7)聚类结果评价方法 fom Silhouette指数本文方法3.74870.7054层次聚类5.36170.1565K-均值聚类3.99370.5158模糊C均值聚类3.75620.6679表2 各种聚类算法对拟南芥基因数据（300*79）聚类结果评价方法 fom Silhouette指数本文方法4.12970.2867层次聚类4.23090.2857K-均值聚类4.54580.0256模糊C均值聚类4.35350.08993.2.2聚类结果的功能评价对基因进行聚类的主要目的就是根据已知基因功能估计未知基因功能，因此基于基因表达数据的数学特征评价聚类结果并不一定能获得理想的聚类结果。理想的聚类结果是将功能上相似的基因尽可能地分到同一个类中，而将功能不同的基因尽可能地分到不同的类中。通路作为一条维持生命的分子反应链, 不同的生命过程有不同的通路,同一通路下基因功能相同。从互联网上(/home/tair/pathways/)下载了所有拟南芥代谢通路数据。用本文算法对这些数据进行聚类，结果发现大部分通路下基因都能聚到一起。比如在同一通路下AT4G16155、AT3G17240、AT1G48030、AT3G16950、AT3G52200、AT3G13930、AT1G54220、AT1G34430、AT3G25860、AT5G17380、AT4G33070、AT1G59900、AT1G30120、AT1G24180、AT1G01090、AT5G50850这些基因几本全部聚在一起。3.2.3实验结果可视化(1)率失真=0.15对酵母数据聚类结果,红色表示高表达值，绿色表示低表达值(2)率失真=0.77对拟南芥数据聚类实验结果可见，用本文算法得到的聚类效果要优于传统聚类算法，且避免了聚类数需要主观确定和对初始聚类中心敏感等问题。4结论与讨论目前,应用在基因表达数据上的聚类算法有很多。但各个聚类算法产生的聚类结果是不一样的，即使是同一个聚类算法选择不同的参数效果也是不一样的。而且传统的聚类算法需要主观确定聚类数。本文针对传统聚类算法的特点，来对基因表达数据的聚类算法进行研究，把信息论的一个很重要的结论和基因聚类联系起来，结果证明要优于传统聚类算法。但是本算法运行速度很慢，下一步的工作就是改进算法或者把本算法和其它的算法相结合，来提高运行速度。参考文献1 杨春梅,万柏坤.基因表达数据聚类分析算法研究和应用D:博士学位论文.天津大学精密仪器与光电子工程学院,2006.2高倩倩，基因表达数据的聚类算法研究及其实现D. 硕士学位论文. 江南大学,20093吴飞珍,万柏坤.基因芯片数据的聚类功能评价算法和判别分析算法研究 D:博士学位论文.上海大学,2009.4 杨春梅,万柏坤,高晓峰.基因聚类分析中数据预处理方式和相似度的选择 J. 自然科学进展, 2006 , 16(3): 293- 298.5 Yi Ma, Harm Derksen, Wei Hong, John Wright. Segmentation of Multivariate Mixed