1、生物信息学中数据挖掘生物信息学中数据挖掘李 荣1212月月第1页后基因组时代研究方向后基因组时代研究方向vv基因组怎样产生功效基因组怎样产生功效vv主要问题：主要问题：vv不一样基因，不一样细胞过程中功效不一样基因，不一样细胞过程中功效n n基因调控方式基因调控方式基因调控方式基因调控方式n n基因与基因产物互作用方式基因与基因产物互作用方式基因与基因产物互作用方式基因与基因产物互作用方式n n以上以上以上以上2 2种网络种网络种网络种网络vv基因表示水平在不一样细胞类型和状态下基因表示水平在不一样细胞类型和状态下不一样不一样第2页基因芯片基因芯片vv建立基因表示模式：基因表示矩阵建立基因表示
2、模式：基因表示矩阵n n基因为行基因为行基因为行基因为行n n情形情形情形情形为列为列为列为列第3页基因表示分析举例基因表示分析举例vv1.发觉一些基因表示与某癌症相关发觉一些基因表示与某癌症相关vv2.探索哪些情况影响这些基因表示探索哪些情况影响这些基因表示vv 探索哪些基因有相同表示模式探索哪些基因有相同表示模式vv3.调查哪些化合物（潜在药品）能降低这些调查哪些化合物（潜在药品）能降低这些基因表示基因表示第4页基因表示矩阵分析基因表示矩阵分析vv不一样基因表示模式比较：行比较不一样基因表示模式比较：行比较vv不一样情形表示模式比较：列比较不一样情形表示模式比较：列比较vv以上两种结合（前
3、提：数据规范化）以上两种结合（前提：数据规范化）第5页比较比较-发觉相同或不一样发觉相同或不一样vv行比较：行比较：n n两行相同意味两基因共调控或功效相关两行相同意味两基因共调控或功效相关两行相同意味两基因共调控或功效相关两行相同意味两基因共调控或功效相关vv列比较：列比较：n n哪些基因表示改变了哪些基因表示改变了哪些基因表示改变了哪些基因表示改变了第6页相同性（距离）度量相同性（距离）度量vv将对象（行或列）作为将对象（行或列）作为n维空间点或维空间点或n维向维向量量vv计算点间距离计算点间距离vv欧几里德距离：结果显著但非最正确欧几里德距离：结果显著但非最正确vv将将n维向量作为随机变
4、量用相关系数计算（维向量作为随机变量用相关系数计算（与与n维向量间角度相关）维向量间角度相关）vv将将n维向量长度规范化为维向量长度规范化为1，则以上两种相则以上两种相关关第7页相同性（距离）度量相同性（距离）度量vv无怎样选择最正确距离度量理论无怎样选择最正确距离度量理论vv最适当距离度量方法不一定存在最适当距离度量方法不一定存在vv选择依赖于详细问题选择依赖于详细问题vv已知共调控基因标准集和基因调控网络模已知共调控基因标准集和基因调控网络模型可能有利于发觉潜在相同性度量型可能有利于发觉潜在相同性度量第8页矩阵分析矩阵分析vv无监督方法：聚集无监督方法：聚集vv有监督方法：结构分类器有监督
5、方法：结构分类器 有其它信息，如功效分类，作为行或有其它信息，如功效分类，作为行或列标签列标签第9页无监督分析：聚集无监督分析：聚集vv用相同性分组用相同性分组vv可看作维规约可看作维规约vv层次聚集、层次聚集、k-means、自组织图自组织图vv桶方法桶方法vv专用方法：如在图中发觉近似系方法专用方法：如在图中发觉近似系方法第10页第11页例例vvK-means方法：方法：3000基因基因15个时间点，聚个时间点，聚为为30 类类vv层次聚类：层次聚类：8600基因基因80次试验，次试验，10个类个类第12页选择有趣基因选择有趣基因vv比较两个或多个情形，得到表示改变基因比较两个或多个情形，
6、得到表示改变基因第13页双路（双路（two-way)聚类聚类-基于分片基于分片聚类聚类vv行聚类与列聚类结合行聚类与列聚类结合vv哪些基因在列聚类中做主要哪些基因在列聚类中做主要 如：如：6500个基因，个基因，40肿瘤，肿瘤，20正常组织正常组织第14页有监督分析：结构分类器有监督分析：结构分类器vv线性识别线性识别vv决议树决议树vv支持向量机（支持向量机（SVM）vv邻居分析邻居分析第15页有监督分析有监督分析-优化优化vv属性（基因）多于对象（情形）属性（基因）多于对象（情形）vv不限制分类器复杂度也可找到优良识别器不限制分类器复杂度也可找到优良识别器vv能够结构简单分类器，满足简单性
7、与分类能够结构简单分类器，满足简单性与分类准确性准确性第16页一个新算法一个新算法vv用无监督聚类得到表示模式空间层次结构用无监督聚类得到表示模式空间层次结构vv用有监督方法发觉与聚类结构相关最正确用有监督方法发觉与聚类结构相关最正确阈值阈值第17页vv发觉调控原因发觉调控原因vv从聚类中发觉基因功效从聚类中发觉基因功效vv原理：原理：第18页识别推定调控信号方法识别推定调控信号方法vv1 基于选定度量聚类基因基于选定度量聚类基因vv2 在聚类基因中提取推定激发序列在聚类基因中提取推定激发序列vv3 在过表示聚类中发觉序列模式在过表示聚类中发觉序列模式vv4 用统计显著性标准评价发觉模式质量用
8、统计显著性标准评价发觉模式质量第19页计算分析步骤计算分析步骤vvStep 1 聚类表示数据聚类表示数据vvStep 2 发觉序列模式发觉序列模式vvStep 3 发觉显著性阈值，其中会重复发觉显著性阈值，其中会重复Step 2vvStep 4 模式选择模式选择vvStep 5 模式分组模式分组vvStep 6 评价发觉模式评价发觉模式第20页结论结论vv基因表示分析方法处于初级阶段基因表示分析方法处于初级阶段vv使用粗糙使用粗糙n n未系统地研究适当相同性度量方法未系统地研究适当相同性度量方法未系统地研究适当相同性度量方法未系统地研究适当相同性度量方法n n评定度量质量方法评定度量质量方法评
9、定度量质量方法评定度量质量方法n n来自不一样平台数据比较来自不一样平台数据比较来自不一样平台数据比较来自不一样平台数据比较第21页发展方向发展方向vv分析方法大量涌现分析方法大量涌现vv可靠相同表示分析方法可靠相同表示分析方法vv度量方法研究度量方法研究vv聚类结果评价方法聚类结果评价方法vv系统化分析基因方法系统化分析基因方法vv逐基因分析方法被网络式分析取代逐基因分析方法被网络式分析取代vv结合生物知识深入分析结合生物知识深入分析第22页基因表示数据聚类分析算法评价基因表示数据聚类分析算法评价vv系统、定量地评定聚类算法结果系统、定量地评定聚类算法结果第23页方法方法vv将某个聚类算法作
10、用于各试验数据中，保将某个聚类算法作用于各试验数据中，保留一个情况，用于评价算法预测能力留一个情况，用于评价算法预测能力vv三个聚类算法：平均连接层次聚类、三个聚类算法：平均连接层次聚类、CAST、自组织图自组织图vv三个公共数据库三个公共数据库第24页传统方法：用生物学知识可视化传统方法：用生物学知识可视化地评价（地评价（1）vv构建模拟数据集构建模拟数据集D(i,j)vvi:基因基因I平均表示水平平均表示水平vvj：每个情形（试验）每个情形（试验）j平均表示水平平均表示水平vv dij：用用i+j为均值，为均值，1为参数标准正态分为参数标准正态分布布vv所以模拟数据集无本质模式。所以模拟数
11、据集无本质模式。第25页传统方法：用生物学知识可视化传统方法：用生物学知识可视化地评价（地评价（2）vv将计算作用于模拟数据集将计算作用于模拟数据集vv结果可视化结果可视化第26页第27页vv之前无系统数据驱动方法定量地评定之前无系统数据驱动方法定量地评定vv提出一个定量数据驱动方法评定与比较不提出一个定量数据驱动方法评定与比较不一样聚类算法算法一样聚类算法算法第28页相同矩阵相同矩阵vv预聚类预聚类 将两个基因表示原始序列归约为一个值：对将两个基因表示原始序列归约为一个值：对相同数相同数第29页聚类算法评价历史方法聚类算法评价历史方法vv外部标准分析外部标准分析n n将聚类结果与已知将聚类结
12、果与已知将聚类结果与已知将聚类结果与已知“金金金金”标准比较标准比较标准比较标准比较vv内部标准分析内部标准分析n n用给定数据集内信息评价用给定数据集内信息评价用给定数据集内信息评价用给定数据集内信息评价第30页问题描述问题描述vvn个基因，个基因，m个试验个试验vv共调控基因表示水平相同共调控基因表示水平相同vv比较聚类算法比较聚类算法A与算法与算法B结果结果第31页方法方法 vv用用m-1个试验聚类个试验聚类vv用剩下用剩下1个试验评定算法预测能力个试验评定算法预测能力vv同一聚类基因在此试验中表示是否相同同一聚类基因在此试验中表示是否相同vv优良指数优良指数FOM（figure of
13、menz）第32页FOMvv情形情形情形情形0,1,(0,1,(e-1),(e+1),(m-1)e-1),(e+1),(m-1)被用于聚类被用于聚类被用于聚类被用于聚类vv情形情形情形情形e e用于评定用于评定用于评定用于评定vv产生产生产生产生K K个聚类个聚类个聚类个聚类C C1 1，C C2 2，C CK Kvv聚类大小为聚类大小为聚类大小为聚类大小为S S1 1，S S2 2，S SK KvvR(iR(i，j)j)表示基因表示基因表示基因表示基因i i在情形在情形在情形在情形j j表示表示表示表示n nFOM(eFOM(e，k)k)：e e情形验证情形验证情形验证情形验证K K个聚类个
14、聚类个聚类个聚类FOMFOMn n ：聚类聚类聚类聚类C Ci i 基因在情形基因在情形基因在情形基因在情形e e平均表示平均表示平均表示平均表示第33页续续vvm个情形轮番作为校验情形个情形轮番作为校验情形vv总总FOM越小越好越小越好第34页第35页vv由上图可知：由上图可知：B方法优于方法优于A方法方法vv聚类质量与聚类数相关聚类质量与聚类数相关vv对给定数据集预先不能确定最正确聚类数对给定数据集预先不能确定最正确聚类数第36页小结小结vv本质为评价分类器准确度本质为评价分类器准确度vv并假设对象标签并假设对象标签vv轮番隐藏每个对象标签轮番隐藏每个对象标签vv用分类器统计对象标签用分类
15、器统计对象标签第37页作者提出算法作者提出算法vv不预先假设任何基因信息不预先假设任何基因信息vv用用FOM评定评定vv可用于任意聚类算法与相同矩阵可用于任意聚类算法与相同矩阵第38页试验用算法试验用算法vvCAST、重复算法、重复算法、K-meansvv 随机聚类算法随机聚类算法第39页vv ：情形：情形e下聚类下聚类Ci中最高表示水平中最高表示水平vv ：情形：情形e下聚类下聚类Ci中最低表示水平中最低表示水平vv表示范围表示范围=vv范围范围FOM第40页vv情形情形e最小可达最小可达FOM：情形情形e下最小可能下最小可能FOMvv计算复杂度为计算复杂度为第41页vv将重复、将重复、CA
16、ST、K-means算法随机聚类算法随机聚类n n分别作用于三个基因表示数据集分别作用于三个基因表示数据集分别作用于三个基因表示数据集分别作用于三个基因表示数据集vv计算得到可信计算得到可信FOM（e,k）n n随机聚类主要步骤重复了随机聚类主要步骤重复了随机聚类主要步骤重复了随机聚类主要步骤重复了10001000次次次次n n重复聚类主要步骤重复了重复聚类主要步骤重复了重复聚类主要步骤重复了重复聚类主要步骤重复了1010次次次次n nK-meansK-means主要步骤重复了主要步骤重复了主要步骤重复了主要步骤重复了3030次次次次第42页第43页第44页第45页分析分析vv聚类数目增加聚类
17、数目增加FOM减小减小n n算法可取得高质量聚类算法可取得高质量聚类算法可取得高质量聚类算法可取得高质量聚类n n简单地增加聚类数目简单地增加聚类数目简单地增加聚类数目简单地增加聚类数目FOMFOM减小减小减小减小第46页相同矩阵效果（相同矩阵效果（1）vv用信息熵作为相同矩阵用信息熵作为相同矩阵第47页结论结论vv聚类算法效果依赖于聚类算法效果依赖于n n给定数据集给定数据集给定数据集给定数据集n n聚类数目聚类数目聚类数目聚类数目n nFOMFOM定义定义定义定义第48页此方法也用于验证给定数据集聚此方法也用于验证给定数据集聚类存在类存在vv计算模拟数据集计算模拟数据集FOM，其趋势与有内
18、在模其趋势与有内在模式完全不一样式完全不一样vv模拟数据集趋势更靠近于随机聚类算法模拟数据集趋势更靠近于随机聚类算法第49页没有聚类算法是完全优异没有聚类算法是完全优异vvK-means快快n n例某一试验，例某一试验，例某一试验，例某一试验，K-meansK-means 2 2秒，其它算法秒，其它算法秒，其它算法秒，其它算法5050秒以上秒以上秒以上秒以上vvCAST可信度高可信度高第50页深入工作方向深入工作方向vv比较不一样算法聚类结果相同性比较不一样算法聚类结果相同性n n基因基因基因基因x,yx,y在算法在算法在算法在算法A A中处于同一个聚类中处于同一个聚类中处于同一个聚类中处于同
19、一个聚类n n计算其在算法计算其在算法计算其在算法计算其在算法B B中处于同一个聚类可能性中处于同一个聚类可能性中处于同一个聚类可能性中处于同一个聚类可能性vv数据集中变量标准化数据集中变量标准化vv不一样标准化方法对算法预测能力作用不一样标准化方法对算法预测能力作用第51页交互可视聚类算法交互可视聚类算法vv用用3维空间直接可视化对象间距离维空间直接可视化对象间距离n n设计距离矩阵设计距离矩阵设计距离矩阵设计距离矩阵n n依据要求距离查找点依据要求距离查找点依据要求距离查找点依据要求距离查找点n n单值分析算法单值分析算法单值分析算法单值分析算法n n弹性着床方法弹性着床方法弹性着床方法弹
20、性着床方法n n用用用用3-3-D D浏览器，可视化这些点浏览器，可视化这些点浏览器，可视化这些点浏览器，可视化这些点第52页无监督神经元网络无监督神经元网络vv自组织树算法自组织树算法SOTA(self-organizing tree algorithm)n n按照二叉树拓扑生长按照二叉树拓扑生长按照二叉树拓扑生长按照二叉树拓扑生长n n结合了层次聚类表示能力与神经元网络强壮性结合了层次聚类表示能力与神经元网络强壮性结合了层次聚类表示能力与神经元网络强壮性结合了层次聚类表示能力与神经元网络强壮性第53页数据质量挖掘数据质量挖掘DQMvv数据质量：一直满足用户期望数据质量：一直满足用户期望vv
21、DQM：精细地利用数据挖掘技术度量与提精细地利用数据挖掘技术度量与提升数据质量升数据质量vv在大型数据库中，检测、量化、解释、校在大型数据库中，检测、量化、解释、校正数据质量缺点正数据质量缺点第54页已用到算法已用到算法vv偏差和异常检测偏差和异常检测vv聚类与依赖分析聚类与依赖分析vv分类分类vv神经元网络神经元网络第55页度量和解释数据质量缺点度量和解释数据质量缺点vv了解何种方法适合何种数据了解何种方法适合何种数据vv怎样用怎样用KDD方法方法第56页校正有缺点数据校正有缺点数据vv检测并剔除有缺点数据检测并剔除有缺点数据vv预计丢失值和不正确值预计丢失值和不正确值第57页扩展扩展KDD
22、处理模型处理模型vv在在KDD过程中加入显示数据质量阶段过程中加入显示数据质量阶段vv度量与提升数据质量不但作为度量与提升数据质量不但作为KDD项目标项目标初始阶段，在实际挖掘与调度阶段也是主初始阶段，在实际挖掘与调度阶段也是主要部分要部分第58页建立处理模型为建立处理模型为“纯纯DQM”vvDQM从数据分析中分离出来从数据分析中分离出来第59页用关联规则用关联规则DQMvv数据库数据库D，任何满足质量度量阈值规则都能任何满足质量度量阈值规则都能够有效产生够有效产生n n例：例：例：例：Zip code:80801City:MunichZip code:80801City:Munich可信度稍
23、低于可信度稍低于可信度稍低于可信度稍低于100%.100%.则任何事务不满足此规则认为有缺点则任何事务不满足此规则认为有缺点则任何事务不满足此规则认为有缺点则任何事务不满足此规则认为有缺点vv可信度较低规则不满足，考虑其它规则，可信度较低规则不满足，考虑其它规则，仍不满足则可疑度加强。仍不满足则可疑度加强。vv条件：使用由数据集本身导出规则条件：使用由数据集本身导出规则 缺点是极少数缺点是极少数第60页深入工作深入工作vvDQM中关联规则挖掘与经典算法不一样中关联规则挖掘与经典算法不一样n n如：支持度低，置信度高如：支持度低，置信度高如：支持度低，置信度高如：支持度低，置信度高vv应用此算法于半自动化校正数据应用此算法于半自动化校正数据vv应用此算法于质量监测系统应用此算法于质量监测系统第61页谢谢 谢谢 ！第62页
