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

1、Analysis of microarray data,Cui Qinghua 2009-03-06,Outline,Introduction Databases Detection of differentially expressed genes Clustering Classification Principal component analysis (PCA) Pathway and Ontology analysis Survival analysis,Introduction,我只强调一点，基因芯片数值反应的是mRNA的丰度（abundancy），因此，可以在一定程度上反应基因的

2、表达水平。,Biological Question,Sample Preparation,Data Analysis & Modelling,Microarray Reaction,MicroarrayDetection,Taken from Schena & Davis,Microarray总流程,应用,差异表达基因检测（不同组织、不同时间、不同条件等） 基因联合调控 疾病诊断 基因功能鉴定 药物筛选和新药开发,应用：以人类疾病为例,神经系统：肿瘤、aging, CNS炎症、多发性硬化、老年痴呆、精神分裂症、癫痫、帕金森病等； 呼吸系统：肺癌、支气管哮喘、原发性肺动脉高压、肺间质纤维化、结节

3、病等； 消化系统：肿瘤，肠炎等 其他：造血系统疾病、传染性疾病、生殖系统疾病以及泌尿系统疾病等,s1 s2 s3 sj sM,g1 g2 gi gN,gene profile,array profile,Gi,Aj,Microarray data matrix,Mi,j,Databases-三大基因表达数据库,美国国立生物信息中心NCBI的Gene Expression Omnibus数据库 (GEO, /geo/),Databases-三大基因表达数据库,欧洲生物信息学研究所EBI的ArrayExpress数据库 (http:/www.eb

4、i.ac.uk/microarray-as/ae/),Databases-三大基因表达数据库,美国斯坦福大学的SMD数据库 (/),数据预处理,数据缺失 原因 图像受到污染 图像分辨率不足 片上灰尘或刮痕 缺失数据的处理方法 舍弃该数据（同时丢掉了有用信息！） 再做一次实验 （太昂贵了！） 用某个数取代，比如样本均值 K-nearest neighbors估计 奇异值分解（SVD） 估计 标准化 Log变换 线性回归 伸缩+平移,Detection of differentially expressed genes,两类样本 t te

5、st Wilcoxon test 多类样本 anova 多重检验校正 Bonferoni FDR,软件-SAM,Significance Analysis of Microarrays (Tusher et al. 2001) 需要R软件包 Excel嵌入式函数,Clustering,Clustering三要素,相似性度量 Pearsons correlation Spearmans correlation Euclidian distance City block distance 聚类准则 聚类算法,聚类算法,层次聚类：假设有N个样本，第一级，每个样本为1类，即有N类，依次合并，直到样本只

6、有一类。 非层次聚类 K-means Fuzzy c-means 自组织映射 。,Clustering软件-Cluster,Michael Eisen et al. 步骤： 打开软件 装入数据（格式解释） 选择聚类办法 设置参数 运行,层次聚类法的基本步骤,层次聚类法的基本步骤 对数据进行变换； 定义样本间的距离（如欧氏距离）、类别之间的距离（如最短距离）； 首先将t个样本各自视为一类：得到初始的分类G(1) （含有t类），计算t个样本两两之间的距离，它们等价于初始的类间距离，得到初始的距离矩阵D(1) ； 将距离最近的两类合并为一新类，得到新的分类G(2)（含有t-1类），并计算新类与其它类

7、的类间距离，得到新的类间距离矩阵D(2) ，再按照最小距离准则并类，得到G(3)（含有t-2类）、D(3), 。直到所有样本都并成一类 ； 画出谱系聚类图，决定分类的个数及各类的成员。,X1,X2,X3,X4,X5,X6,X1,X2,X4,X3,X5,X6,层次聚类法举例,已知：根据5种灵长类动物朊粒蛋白的氨基酸序列比较，得到它们之间的距离矩阵（经过数据变换处理）。 X(1)：Gibbon（长臂猿）； X(2)：Symphalangus； X(3) ：Human（人）； X(4) ：Gorilla（大猩猩）； X(5) ：Chimpanzee（黑猩猩）,构造： 样本间距离欧氏距离； 类间距离最

8、短距离；,步骤 1 5个物种各自构成1类，得到5类，有： 初始分类G (1)=X(i)(i=1, 2, 3, 4, 5) 初始类别数目m=5 初始类间距离矩阵D(1),D(1),步骤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 由D(2)知，合并X(3)和X(4)为一新类C(3)=X(3), X(4)，有： 新的G (3)= X(5) , C(4) , C(3) 新的类别数目m=3 新的类间距离矩阵D(3),D(3),步骤4

9、 由D(3)知，合并X(5)和C(3)为一新类C(2)=X(5), C(3)，有： 新的G (4)=C(4) , C(2) 新的类别数目m=2 新的类间距离矩阵D(4),D(4),步骤5 由D(4)知，最后合并C(4)和C(2)为一新类C(1)=C(4), C(2)，有： 新的G (5)=C(4) , C(2) 新的类别数目m=1 新的类间距离矩阵D(5),D(5),X(1),X(2),X(3),X(4),X(5),步骤6 画谱系聚类图,1,2,3,0,Gibbon,Symphalangus,Human,Gorilla,Chimpanzee,影响聚类结果的主要因素 样本间距离的定义dij 类间

10、距离的定义Dij,层次聚类linkage方法,Linkage方法直接影响了聚类结果，它取决于类间距离如何定义。关于类间距离有如下几种： Centroid linkage：几何中心距离。仅适用于欧氏距离。The distance between two clusters is the Euclidean distance between their centroids Single linkage：最短距离 Complete linkage:最长距离 Average linkage:平均距离,centroid linkage 几何中心距离,讨论（递推公式）：设Gr是由Gp和Gq合并得到的新类，考

11、虑Gr与Gs（s p, q）的类间距离（几何中心距离） Drs ，有：,定义：用Gp和Gq两类几何中心的距离为两个类之间的距离。,用Gp和Gq表示两个类，它们所包含的样本数目分别为tp和tq，类Gp和Gq之间的距离用Dpq表示。,single linkage 最短距离,讨论（递推公式）：设Gr是由Gp和Gq合并得到的新类，考虑Gr与Gs（s p, q）的类间距离（最短距离） Drs ，有：,定义： Gp和Gq中最邻近的两个样本的距离为这两个类之间的距离。,complete linkage 最长距离,讨论（递推公式）：设Gr是由Gp和Gq合并得到的新类，考虑Gr与Gs（s p, q）的类间距离（

12、最长距离） Drs ，有：,定义： Gp和Gq中相距最远的两个样本的距离为这两个类之间的距离。,average linkage 类平均距离,讨论（递推公式）：设Gr是由Gp和Gq合并得到的新类，考虑Gr与Gs（s p, q）的类间距离（类平均距离） Drs ，有：,定义：用Gp和Gq中每两两样本间距离的平均值作为两个类之间的距离。,类别数目的确定,X(1),X(2),X(3),X(4),X(5),1,2,0,Dcr1,Dcr2,Dcr3,Dcr4,Dcr5,层次聚类结果的可视化-TreeView,非层次聚类,选取 聚类种子点 (Cluster seeds),初始分类,修改分类,分类是否 合理？

13、,最终分类,是,否,例,Microarray数据模式分类,预处理,特征提取,机器学习,决策,训练样本,新样本,分类器,决策,X,F(X),Y,模式分类算法,线性分类器 神经网络 最近邻 贝叶斯分类器 隐马尔科夫模型分类器 决策树 支持向量机,Principal component analysis (PCA, 主成分分析),基因芯片数据维数高，难以可视化 基因芯片数据噪音比较强 PCA主要的应用 降维 去噪,PCA 数学基础：统计和线性代数,均值(mean): 标准差(standard deviation): 方差,PCA 数学基础：统计和线性代数,协方差（covariance）:以上测量都是

14、针对一维变量的，然而，实际数据很多都包含2维以上的数据，统计分析的一个重要目标是检查这些维之间是否有某种关系。,PCA 数学基础：统计和线性代数,协方差（covariance）例子:样本：一个班里抽取12个学生。2维：一是每个学生的期末成绩，另一是每个学生花费在学习上的时间,PCA 数学基础：统计和线性代数,协方差距阵（covariance matrix） 矩阵代数（线性代数）：这方面知识不介绍了，感兴趣的同学可以课下自学。,PCA:举例说明,PCA软件,Too many! Excel SPSS Matlab R Cluster,Pathway and Ontology analysis,Ge

15、ne set enrichment analysis (GSEA),BiNGO: Gene Ontology analysis of gene cluster,二项分布 如果进行n次独立试验，用X记成功次数，则有： 超几何分布 对N件产品（其中有M件次品）进行不放回抽样检查，在n件样品中的次品数X显然是随机变量，它的分布是超几何分布,“Survival” analysis,PIB5PA271241.9e-6 Miz190630.08 GROUCHO70880.004 CBLB8680.08 HBO1111430.008 UBE3A73370.01 RASGAP257800.04 SKP1650

16、00.03 SODD95300.03,Biomarker!,Survival analysis,Survival curve estimate and test Survival curve: the fraction of patients who survive for at least one month, at least three months, etc Survival curve estimate Survival curve test (comparison, standard therapy compared to a newer therapy?),Survival curve estimates: Kaplan-Meier