欧氏距离类间距离——最短距离精编版

1、 Outline Introduction Databases Detection of differentially expressed genes Clustering Classification Principal component analysis (PCA) Pathway and Ontology analysis Survival analysis Introduction 我只强调一点，基 因芯片数值反应的 是mRNA的丰度 （abundancy）， 因此，可以在一定 程度上反应基因的 表达水平。 Biological Question Sample Preparation

2、 Data Analysis & Modelling Microarray Reaction Microarray Detection 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.ebi.ac.uk/microarray-as/ae/) Databases-

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

5、nferoni 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类，依次合并，直 到样本只有一类。 非层次聚类 K-means Fuzzy c-means 自组

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

7、始的距离矩阵D(1) ； 将距离最近的两类合并为一新类，得到新的分类将距离最近的两类合并为一新类，得到新的分类G(2) （含有含有t-1类），并计算新类与其它类的类间距离，得到新类），并计算新类与其它类的类间距离，得到新 的类间距离矩阵的类间距离矩阵D(2) ，再按照最小距离准则并类，得到再按照最小距离准则并类，得到G(3) （含有含有t-2类）、类）、D(3), 。直到所有样本都并成一类直到所有样本都并成一类 ； 画出谱系聚类图，决定分类的个数及各类的成员。画出谱系聚类图，决定分类的个数及各类的成员。 X1 X2 X3 X4 X5 X6 X1 X2 X4 X3 X5 X6 根据根据5种灵长类

8、动物朊粒蛋白的氨基酸序列比较，得到它们之种灵长类动物朊粒蛋白的氨基酸序列比较，得到它们之 间的距离矩阵（经过数据变换处理）。间的距离矩阵（经过数据变换处理）。 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.557 X(2)02.546 X(3)01.53.5 X(4)02 X(5)0

9、 5个物种各自构成个物种各自构成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.557 X(2)02.546 X(3)01.53.5 X(4)02 X(5)0 D(1) X(3)X(4)X(5)C(4) X(3)0 X(4)024 X(5)06 C(4)0 由由D(1)知，合并知，合并X(1)和和X(2)为一新类为一新类C(4)=X(1), X(2)，有：有： 新的新的G (2)=X(

10、3) , X(4) , X(5) , C(4) 新的类别数目新的类别数目m=4 新的类间距离矩阵新的类间距离矩阵D(2) D(2) 由由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)062 C(4)02.5 C(3)0 D(3) 由由D(3)知，合并知，合并X(5)和和C(3)为一新类为一新类C(2)=X(5), C(3)，有：有： 新的新的G (4)=C(4) , C(2

11、) 新的类别数目新的类别数目m=2 新的类间距离矩阵新的类间距离矩阵D(4) C(4)C(2) C(4)02.5 C(2)0 D(4) 由由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)0 D(5) X(1) X(2) X(3) X(4) X(5) 画谱系聚类图画谱系聚类图 1230 Gibbon Symphalangus Human Gorilla Chimpanzee 样本间距离的定义样本间距

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

13、虑Gr与与Gs （s p, q）的类间距离（几何中心距离）的类间距离（几何中心距离） Drs ，有：有： qp t i q i q q t i p i p p qp pq X t XX t X XXdD 1 )()( 1 )()( )()( 11 , 用用Gp和和Gq两类几何中心的距离为两个类之间的距离。两类几何中心的距离为两个类之间的距离。 )()( , sr rs XXdD 用用Gp和和Gq表示两个类，它们所包含的样本数目分别为表示两个类，它们所包含的样本数目分别为tp和和tq，类类Gp和和 Gq之间的距离用之间的距离用Dpq表示。表示。 设设Gr是由是由Gp和和Gq合并得到的新类，考虑合

14、并得到的新类，考虑Gr与与Gs （s p, q）的类间距离（最短距离）的类间距离（最短距离） Drs ，有：有： ,|min qpijpq GjGidD Gp和和Gq中最邻近的两个样本的距离为这两个类之间的距离。中最邻近的两个样本的距离为这两个类之间的距离。 ,min ,|min,|minmin ,|min qsps sqijspij srijrs DD GjGidGjGid GjGidD 设设Gr是由是由Gp和和Gq合并得到的新类，考虑合并得到的新类，考虑Gr与与Gs （s p, q）的类间距离（最长距离）的类间距离（最长距离） Drs ，有：有： ,|max qpijpq GjGidD G

15、p和和Gq中相距最远的两个样本的距离为这两个类之间的距离。中相距最远的两个样本的距离为这两个类之间的距离。 ,max ,|max,|maxmax ,|max qsps sqijspij srijrs DD GjGidGjGid GjGidD 设设Gr是由是由Gp和和Gq合并得到的新类，考虑合并得到的新类，考虑Gr与与Gs （s p, q）的类间距离（类平均距离）的类间距离（类平均距离） Drs ，有：有： qp t i t j ij qp pq GjGid tt D pq , 1 11 用用Gp和和Gq中每两两样本间距离的平均值作为两个类之间的距离。中每两两样本间距离的平均值作为两个类之间的距

16、离。 1 )( 1 , 1 111 11 sq r q sp r p sqqsspps sr t i t j ij t j ij sr sr t i t j ij sr rs D t t D t t DttDtt tt dd tt GjGid tt D s qp rs X(1) X(2) X(3) X(4) X(5) 120 Dcr1Dcr2Dcr3Dcr4Dcr5 层次聚类结果的可视化- TreeView 非层次聚类 选取选取 聚类种子点聚类种子点 (Cluster seeds) 分类是否分类是否 合理？合理？ Microarray数据模式分类 预处理特征提取机器学习决策 训 练 样 本 新

17、 样 本 分类器决策 X F(X)Y x1 x2 L: c1x1+c2x2c=0 G1 G2 模式分类算法 线性分类器 神经网络 最近邻 贝叶斯分类器 隐马尔科夫模型分类器 决策树 支持向量机 Principal component analysis (PCA, 主成分分析) 基因芯片数据维数高，难以可视化 基因芯片数据噪音比较强 PCA主要的应用 降维 去噪 PCA 数学基础：统计和线性代数 均值(mean): 标准差(standard deviation): 方差 PCA 数学基础：统计和线性代数 协方差（covariance）:以上测量都是针对 一维变量的，然而，实际数据很多都包 含2维

18、以上的数据，统计分析的一个重要 目标是检查这些维之间是否有某种关系。 PCA 数学基础：统计和线性代数 协方差（covariance）例子:样本：一个班里抽 取12个学生。2维：一是每个学生的期末成绩， 另一是每个学生花费在学习上的时间 PCA 数学基础：统计和线性代数 协方差距阵（covariance matrix） 矩阵代数（线性代数）：这方面知识不介绍了， 感兴趣的同学可以课下自学。 PCA:举例说明 PCA软件 Too many! Excel SPSS Matlab R Cluster Pathway and Ontology analysis Gene 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 HBO1111