欧氏距离类间距离——最短距离课件

Analysis of microarray dataCui Qinghua2009-03-06OutlineIntroductionDatabasesDetection of differentially expressed genesClusteringClassificationPrincipal component analysis(PCA)Pathway and Ontology analysisSurvival analysisIntroduction我只强调一点，基因芯片数值反应的是mRNA的丰度（abundancy），因此，可以在一定程度上反应基因的表达水平。Biological Question Sample PreparationData Analysis&ModellingMicroarray ReactionMicroarrayDetectionTaken from Schena&DavisMicroarray总流程应用差异表达基因检测（不同组织、不同时间、不同条件等）基因联合调控疾病诊断基因功能鉴定药物筛选和新药开发应用：以人类疾病为例神经系统：肿瘤、aging,CNS炎症、多发性硬化、老年痴呆、精神分裂症、癫痫、帕金森病等；呼吸系统：肺癌、支气管哮喘、原发性肺动脉高压、肺间质纤维化、结节病等；消化系统：肿瘤，肠炎等其他：造血系统疾病、传染性疾病、生殖系统疾病以及泌尿系统疾病等s1 s2 s3 sj sMg1g2gigNgene profilearray profileGiAjMicroarray data matrixMi,jDatabases-三大基因表达数据库美国国立生物信息中心NCBI的Gene Expression Omnibus数据库(GEO,http:/www.ncbi.nlm.nih.gov/geo/)Databases-三大基因表达数据库欧洲生物信息学研究所EBI的ArrayExpress数据库(http:/www.ebi.ac.uk/microarray-as/ae/)Databases-三大基因表达数据库美国斯坦福大学的SMD数据库(http:/genome-www5.stanford.edu/)数据预处理数据缺失原因图像受到污染图像分辨率不足片上灰尘或刮痕缺失数据的处理方法舍弃该数据（同时丢掉了有用信息！）再做一次实验（太昂贵了！）用某个数取代，比如样本均值K-nearest neighbors估计奇异值分解（SVD）估计标准化Log变换线性回归伸缩+平移Detection of differentially expressed genes两类样本t testWilcoxon test多类样本anova多重检验校正BonferoniFDR软件-SAMSignificance Analysis of Microarrays(Tusher et al.2001)需要R软件包Excel嵌入式函数ClusteringClustering三要素相似性度量Pearsons correlationSpearmans correlationEuclidian distanceCity block distance聚类准则聚类算法聚类算法层次聚类：假设有N个样本，第一级，每个样本为1类，即有N类，依次合并，直到样本只有一类。非层次聚类K-meansFuzzy c-means自组织映射。Clustering软件-ClusterMichael Eisen et al.步骤：打开软件装入数据（格式解释）选择聚类办法设置参数运行层次聚类法的基本步骤层次聚类法的基本步骤层次聚类法的基本步骤层次聚类法的基本步骤层次聚类法的基本步骤 对数据进行变换；对数据进行变换；定义样本间的距离（如欧氏距离）、类别之间的距离定义样本间的距离（如欧氏距离）、类别之间的距离（如最短距离）；（如最短距离）；首先将首先将t个样本各自视为一类：得到初始的分类个样本各自视为一类：得到初始的分类G(1)（含含有有t类），计算类），计算t个样本两两之间的距离，它们等价于初始个样本两两之间的距离，它们等价于初始的类间距离，得到初始的距离矩阵的类间距离，得到初始的距离矩阵D(1)；将距离最近的两类合并为一新类，得到新的分类将距离最近的两类合并为一新类，得到新的分类G(2)（含有含有t-1类），并计算新类与其它类的类间距离，得到新类），并计算新类与其它类的类间距离，得到新的类间距离矩阵的类间距离矩阵D(2)，再按照最小距离准则并类，得到再按照最小距离准则并类，得到G(3)（含有含有t-2类）、类）、D(3),。直到所有样本都并成一类直到所有样本都并成一类；画出谱系聚类图，决定分类的个数及各类的成员。画出谱系聚类图，决定分类的个数及各类的成员。X1X2X3X4X5X6X1X2X4X3X5X6层次聚类法举例层次聚类法举例层次聚类法举例层次聚类法举例已知已知已知已知：根据根据5种灵长类动物朊粒蛋白的氨基酸序列比较，得到它们之种灵长类动物朊粒蛋白的氨基酸序列比较，得到它们之间的距离矩阵（经过数据变换处理）。间的距离矩阵（经过数据变换处理）。X(1)：Gibbon（长臂猿）；长臂猿）；X(2)：Symphalangus；X(3)：Human（人）；人）；X(4)：Gorilla（大猩猩）；大猩猩）；X(5)：Chimpanzee（黑猩猩）黑猩猩）构造构造构造构造：样本间距离样本间距离欧氏距离；欧氏距离；类间距离类间距离最短距离；最短距离；X(1)X(2)X(3)X(4)X(5)X(1)013.557X(2)02.546X(3)01.53.5X(4)02X(5)0步骤步骤步骤步骤 1 15个物种各自构成个物种各自构成1类，得到类，得到5类，有：类，有：初始分类初始分类G(1)=X(i)(i=1,2,3,4,5)初始类别数目初始类别数目m=5初始类间距离矩阵初始类间距离矩阵D(1)X(1)X(2)X(3)X(4)X(5)X(1)013.557X(2)02.546X(3)01.53.5X(4)02X(5)0D(1)X(3)X(4)X(5)C(4)X(3)01.53.52.5X(4)024X(5)06C(4)0步骤步骤步骤步骤2 2由由D(1)知，合并知，合并X(1)和和X(2)为一新类为一新类C(4)=X(1),X(2)，有：有：新的新的G(2)=X(3),X(4),X(5),C(4)新的类别数目新的类别数目m=4新的类间距离矩阵新的类间距离矩阵D(2)D(2)步骤步骤步骤步骤3 3由由D(2)知，合并知，合并X(3)和和X(4)为一新类为一新类C(3)=X(3),X(4)，有：有：新的新的G(3)=X(5),C(4),C(3)新的类别数目新的类别数目m=3新的类间距离矩阵新的类间距离矩阵D(3)X(5)C(4)C(3)X(5)062C(4)02.5C(3)0D(3)步骤步骤步骤步骤4 4由由D(3)知，合并知，合并X(5)和和C(3)为一新类为一新类C(2)=X(5),C(3)，有：有：新的新的G(4)=C(4),C(2)新的类别数目新的类别数目m=2新的类间距离矩阵新的类间距离矩阵D(4)C(4)C(2)C(4)02.5C(2)0D(4)步骤步骤步骤步骤5 5由由D(4)知，最后合并知，最后合并C(4)和和C(2)为一新类为一新类C(1)=C(4),C(2)，有：有：新的新的G(5)=C(4),C(2)新的类别数目新的类别数目m=1新的类间距离矩阵新的类间距离矩阵D(5)C(1)C(1)0D(5)X(1)X(2)X(3)X(4)X(5)步骤步骤步骤步骤6 6画谱系聚类图画谱系聚类图1230GibbonSymphalangusHumanGorillaChimpanzee影响聚类结果的主要因素影响聚类结果的主要因素影响聚类结果的主要因素影响聚类结果的主要因素样本间距离的定义样本间距离的定义dij类间距离的定义类间距离的定义Dij层次聚类linkage方法Linkage方法直接影响了聚类结果，它取决于类间距离如何定义。关于类间距离有如下几种：Centroid linkage：几何中心距离。仅适用于欧氏距离。The distance between two clusters is the Euclidean distance between their centroidsSingle linkage：最短距离Complete linkage:最长距离Average linkage:平均距离centroid linkage centroid linkage 几何中心距离几何中心距离几何中心距离几何中心距离讨论（递推公式）讨论（递推公式）讨论（递推公式）讨论（递推公式）：设设Gr是由是由Gp和和Gq合并得到的新类，考虑合并得到的新类，考虑Gr与与Gs（s p,q）的类间距离（几何中心距离）的类间距离（几何中心距离）Drs，有：有：定义定义定义定义：用用Gp和和Gq两类几何中心的距离为两个类之间的距离。两类几何中心的距离为两个类之间的距离。用用Gp和和Gq表示两个类，它们所包含的样本数目分别为表示两个类，它们所包含的样本数目分别为tp和和tq，类类Gp和和Gq之间的距离用之间的距离用Dpq表示。表示。single linkage single linkage 最短距离最短距离最短距离最短距离讨论（递推公式）讨论（递推公式）讨论（递推公式）讨论（递推公式）：设设Gr是由是由Gp和和Gq合并得到的新类，考虑合并得到的新类，考虑Gr与与Gs（s p,q）的类间距离（最短距离）的类间距离（最短距离）Drs，有：有：定义定义定义定义：Gp和和Gq中最邻近的两个样本的距离为这两个类之间的距离。中最邻近的两个样本的距离为这两个类之间的距离。complete linkage complete linkage 最长距离最长距离最长距离最长距离讨论（递推公式）讨论（递推公式）讨论（递推公式）讨论（递推公式）：设设Gr是由是由Gp和和Gq合并得到的新类，考虑合并得到的新类，考虑Gr与与Gs（s p,q）的类间距离（最长距离）的类间距离（最长距离）Drs，有：有：定义定义定义定义：Gp和和Gq中相距最远的两个样本的距离为这两个类之间的距离。中相距最远的两个样本的距离为这两个类之间的距离。average linkage average linkage 类平均距离类平均距离类平均距离类平均距离讨论（递推公式）讨论（递推公式）讨论（递推公式）讨论（递推公式）：设设Gr是由是由Gp和和Gq合并得到的新类，考虑合并得到的新类，考虑Gr与与Gs（s p,q）的类间距离（类平均距离）的类间距离（类平均距离）Drs，有：有：定义定义定义定义：用用Gp和和Gq中每两两样本间距离的平均值作为两个类之间的距离。中每两两样本间距离的平均值作为两个类之间的距离。类别数目的确定类别数目的确定类别数目的确定类别数目的确定X(1)X(2)X(3)X(4)X(5)120Dcr1Dcr2Dcr3Dcr4Dcr5层次聚类结果的可视化-TreeView非层次聚类选取选取聚类种子点聚类种子点(Cluster seeds)初始分类初始分类初始分类初始分类修改分类修改分类修改分类修改分类分类是否分类是否合理？合理？最终分类最终分类最终分类最终分类是是是是否否否否例例例例Microarray数据模式分类预处理特征提取机器学习决策训练样本新样本分类器决策XF(X)Yx1x2L:c1x1+c2x2c=0G1G2模式分类算法线性分类器神经网络最近邻贝叶斯分类器隐马尔科夫模型分类器决策树支持向量机Principal component analysis(PCA,主成分分析)基因芯片数据维数高，难以可视化基因芯片数据噪音比较强PCA主要的应用降维去噪PCA 数学基础：统计和线性代数均值(mean):标准差(standard deviation):方差PCA 数学基础：统计和线性代数协方差（covariance）:以上测量都是针对一维变量的，然而，实际数据很多都包含2维以上的数据，统计分析的一个重要目标是检查这些维之间是否有某种关系。PCA 数学基础：统计和线性代数协方差（covariance）例子:样本：一个班里抽取12个学生。2维：一是每个学生的期末成绩，另一是每个学生花费在学习上的时间PCA 数学基础：统计和线性代数协方差距阵（covariance matrix）矩阵代数（线性代数）：这方面知识不介绍了，感兴趣的同学可以课下自学。PCA:举例说明PCA软件Too many!ExcelSPSSMatlabRClusterPathway and Ontology analysisGene set enrichment analysis(GSEA)BiNGO:Gene Ontology analysis of gene cluster二项分布如果进行n次独立试验，用X记成功次数，则有：超几何分布对N件产品（其中有M件次品）进行不放回抽样检查，在n件样品中的次品数X显然是随机变量，它的分布是超几何分布“Survival”analysisPIB5PA271241.9e-6Miz190630.08GROUCHO70880.004CBLB8680.08HBO1111430.008UBE3A73370.01RASGAP257800.04SKP165000.03SODD95300.03Biomarker!Survival analysisSurvival curve estimate and testSurvival curve:the fraction of patients who survive for at least one month,at least three months,etcSurvival curve estimateSurvival curve test(comparison,standard therapy compared to a newer therapy?)Survival curve estimates:Kaplan-MeierSurvival curve estimatingSurvival curve estimatingSurvival curve estimatingSurvival curve estimatingComparison of survival curvesLog-rank test(more standard)Mantel-Haenszel testGehan-Wilcoxon test提问与解答环节Questions And Answers谢谢聆听 学习就是为了达到一定目的而努力去干,是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal