生物信息学数据挖掘

1、2022-5-10生物信息学数据挖掘1生物信息学数据挖掘生物信息学数据挖掘 2022-5-10生物信息学数据挖掘2主要内容主要内容l数据挖掘的相关概念l数据挖掘的经典案例l生物信息学数据挖掘领域的现状、方向l课题的前景2022-5-10生物信息学数据挖掘3生物信息数据库生物信息数据库l(1) 综合数据库 如EMBL (欧洲) 、GenBank(美国) 、DDBJ (日本) 、TIGR Database)l(2) DNA 序列和结构数据库(BioSino (中国) 、CUTG、EPD、SCPD 等)l(4) RNA 序列和核糖体数据库( SCOR、NCIR、ncRNA 等)l(5) 基因图谱数据

2、库(RHdb、Mouse RH、GDB)l(6) 人类基因组相关数据库( Ensembl 、RefSeq、I.M.A. G. E 等)l(7) 其他物种基因组数据库(包括病毒、原核生物、真菌、昆虫、鱼类及其它高等动物的基因组数据库)l(8) 蛋白质序列数据库(SWISS - PROT、TrEMBL 、PIR 等)l(9) 蛋白质结构、分类和相互作用数据库(PDB、CSD、3Dee 等)l此外,还有比较基因组学和蛋白质组学数据库,基因表达数据库,基因突变、病理和免疫数据库,代谢途径和细胞调控数据库,农林牧相关数据库,医学l药学数据库,生物多样性和分类学数据库等等。2022-5-10生物信息学数据

3、挖掘4专门数据库目录网站专门数据库目录网站l核酸研究2000年开始创建了生物信息学数 据库目录。lDBCat：法国生物信息中心于1997年建立的数据库目录。到目前为止收录500多个数据库。l目前，绝大部分核酸和蛋白质数据库由美国、欧洲和日本的家数据库系统产生。它们共同组成国际核酸序列数据库，每天交换数据，同步更新 大部分数据库是可以免费下载的公用数据库。2022-5-10生物信息学数据挖掘5生物信息学中心生物信息学中心l1.NCBI：美国国立生物技术信息中心(The National Center Biotechnology Information)，设立了公共数据库，开发软件工具分析核酸序列

4、、基因组序列、基因表达序列、蛋白序列等提供了大量与基因、蛋白序列有关的信息与文献资料。l2.EBI：欧洲生物信息研究(The European BioinformationIntitute)，提供与生物学有关的各种信息、数据库、软件工具等l3.ExPASy：(Expert Protein Analysis System)日内瓦大学分子生物学服务站，提供与蛋白有关的各种在线工具。提供数据库中的链接，同时提供许多用于该方面查询的文件，并与本站点相链接。l4.BioSino：上海生命科学院生物信息中心，提供了有关生物信息学方面的新闻、论文、相关数据库、软件等。l5.CBI：北京大学生物信息中心，介绍

5、了丰富的生物信息学基本知识，国内外生物信息学网站，常用的生物信息学数据库的介绍和相关的软件等。2022-5-10生物信息学数据挖掘6KDD(Knowledge Discovery in Database) lKDD(Knowledge Discovery in Database) ,是指从存放在数据库、数据仓库或者其他信息库中的大量数据中挖掘出隐藏的有用信息(知识) 的技术。它被广泛的应用到各个领域,挖掘数据之间潜在的模式,找出有价值的信息。KDD 的基本过程如图1 所示,由以下部分组成:l(1) 数据预处理(包括数据清理、数据集成、数据变换、数据归纳,为数据挖掘做准备l(2) 数据挖掘(核心

6、步骤,使用智能方法提取数据模式)l(3) 模式评估(根据某种度量,识别表示知识的真正模式)l(4) 知识表示(使用可视化知识表示技术,向用户提供挖掘的结果知识)l可以看出,数据挖掘是KDD 的核心部分,是采用机器学习、运筹学、统计方法等进行知识发现的阶段。但是从广义上讲,数据挖掘的定义就是从海量数据中提取知识的过程,也就等同于KDD 2022-5-10生物信息学数据挖掘7KDD的基本过程的基本过程2022-5-10生物信息学数据挖掘8数据挖掘数据挖掘(data mining) 数据挖掘数据挖掘（Data mining），又译为资料探勘、数据采矿。它是数据库知识发现（Knowledge-Disc

7、overy in Databases，简称：KDD)中的一个步骤。数据挖掘一般是指从大量的数据中自动搜索隐藏于其中的有着特殊关系性（属于Association rule learning）的信息的过程。2022-5-10生物信息学数据挖掘9数据中搜索、发现知识数据中搜索、发现知识(KDD)2022-5-10生物信息学数据挖掘10数据挖掘的功能数据挖掘的功能l1分类（分类（classification） 按照分析个体的属性状态分别加以区分，并建立类组（class）。例如，将信用申请者的风险等级分为高风险、中风险和低风险三类。使用的方法有决策树（decision tree）、判别分析（discri

8、minant analysis）、类神经网络（artificial neural network），以及记忆基础推理（memory-based reasoning）等。 l2估计（估计（estimation） 根据已有的数值型变量和相关的分类变量，以获得某一属性的估计值或预测值。例如，根据信用卡申请者的教育程度和从事职业来设定其信用额度。使用的方法有相关分析、Logistic回归及类神经网络等。 l3预测（预测（prediction） 根据个体属性的已有观测值来估计该个体在某一属性上的预测值。例如，由顾客过去刷卡消费额预测其未来的刷卡消费额。使用的方法有回归分析、时间序列分析及类神经网络等。

9、l4关联分组（关联分组（affinity grouping） 从所有对象决定哪些相关对象应该放在一起。例如，超市中相关的洗漱用品（牙刷、牙膏、牙线）放在同一货架上。在客户营销系统上，这类分析可以用来发现潜在的交叉销售（cross-selling）商品聚类，进而设计出有价值的组合商品集合。 l5同质分组（同质分组（clustering） 将异质总体分成为同质性的类别（clusters），即聚类。其目的是识别出总体中所包含的混合类别的组间差异，并根据每个类别的特征对所有个体进行归类。同质分组相当于营销术语中的细分（segmentation）。应该注意的是：聚类分析根据数据自动产生各个类别，事先是不

10、知道或无须知道总体中潜在的类别信息。使用的方法有k-means等动态聚类法及agglomeration等层次聚类法。2022-5-10生物信息学数据挖掘11CRISP-DM是是Cross-Industry Standard Process for Data Mining的简称，中文翻译为的简称，中文翻译为“数据挖掘的跨行业标准过程数据挖掘的跨行业标准过程”lCRISP-DM分为六个阶段（phase）和四个层次（level）2022-5-10生物信息学数据挖掘12数据挖掘的经典案例数据挖掘的经典案例l啤酒和尿布的案例啤酒和尿布的案例 英国超级市场中的啤酒和尿布的摆放位置, 管理人员从每天商品销售

11、的记录中发现来超市购买婴儿尿布的年轻父亲约有一会顺便买几瓶啤酒。根据这一发现, 超市即调整了商品的摆放位置将以上商品尽可能摆放得近一些, 并扩大范围, 将男士的日常用品也靠近婴儿尿布处摆放此安排使这类商品的销售量成倍增长。l其他数据挖掘的案例其他数据挖掘的案例 顾客信誉卡 ：使用信誉卡将顾客的购买序列记录下来，顾客在不同时期购买的商品可以分组为序列，序列模式的挖掘可以分析顾客的消费或忠诚的变化，据此对价格和商品花样进行调整以便留住老顾客，吸引新顾客。 卡夫(Kraft)食品公司建立了一个拥有3000万客户资料的数据库，数据库是通过收集对公司发出的优惠券等其他促销手段作出积极反应的客户和销售记录

12、而建立起来的，卡夫公司通过数据挖掘了解特定客户的兴趣和口味，并以此为基础向他们发送特定产品的优惠券，并为他们推荐符合客户口味和健康状况的卡夫产品食谱。 2022-5-10生物信息学数据挖掘13在电信行业在电信行业 加拿大BC省电话公司要求加拿大Simon Fraser大学KDD研究组根据其拥有的十多年的客户数据，总结、分析并提出新的电话收费和管理办法，制定既有利于公司又有利于客户的优惠政策。竞技运动中的数据挖掘竞技运动中的数据挖掘 美国著名的国家篮球队NBA的教练，利用IBM公司提供的数据挖掘工具临场决定替换队员。电子商务的关联销售电子商务的关联销售 、客户类别销售分析、客户类别销售分析 数据

13、挖掘的经典案例数据挖掘的经典案例14 理解数据和数据的来源理解数据和数据的来源（understanding）。）。 获取相关知识与技术获取相关知识与技术（acquisition）。）。 整合与检查数据（整合与检查数据（integration and checking）。）。 去除错误或不一致的数据（去除错误或不一致的数据（data cleaning）。）。 建立模型和假设（建立模型和假设（model and hypothesis development）。）。 实际数据挖掘工作（实际数据挖掘工作（data mining）。）。 测试和验证挖掘结果（测试和验证挖掘结果（testing and v

14、erification）。）。 解释和应用（解释和应用（interpretation and use）。）。数据挖掘的过程数据挖掘的过程2022-5-10生物信息学数据挖掘15典型的数据挖掘系统结构典型的数据挖掘系统结构2022-5-10生物信息学数据挖掘16进行数据挖掘常用技术算法进行数据挖掘常用技术算法l1 神经网络神经网络l此方法是模拟人脑的神经元，具有并行地处理信息、分布式存储信息、可变结构、高度容错、非线性运算、自组织学习等特点，在分类、聚类、模式识别等领域已被普遍采用l2 统计分析方法统计分析方法l这种方法利用成熟的数理统计原理对关系表中的属性进行分析，找到它们之间存在的关系 方法

15、有多元回归分析、聚类分析、因子分析、相关分析等l 3 遗传算法遗传算法l这是一种搜索算法，具有计算简单、优化效果好的特点，主要用于分类，关联规则采掘等l方面2022-5-10生物信息学数据挖掘17进行数据挖掘常用技术算法进行数据挖掘常用技术算法l4 聚类分析聚类分析聚类分析聚类分析l根据在数据中发现的对象关系，将数据对象分组 同一个组内的对象是相似的，不同组中的对象是不同的l5 决策树决策树l决策树是一种由结点和有向边组成的层次结构 它利用信息论中信息增益来寻找数据库中具有最大信息量的字段，建立决策树的一个结点，再根据测试结果选择分支，对于每个子女结点重复建立下层结点和分支，便可构造一棵决策树

16、l最具有影响的决策树算法首推J R Quinlan 的ID3 算法 ID3 是在1979 年提出的，它是基于信息熵的一种自顶向下构造决策树的归纳学习方法，过程可以归结为2 个步骤，即属性确定和集合划分l6 关联规则关联规则l关联规则是R Agrawal 等人在SIGMOD93 上第一次提出来的，它描述了数据记录集中数据项之间存在的隐藏关系 关联规则的强度可以用支持度和置信度度量2022-5-10生物信息学数据挖掘18lApriori 算法该算法是由Agrawal 等在1993 年提出的，是最经典的产生关联规则频繁项目集的算法，是一种宽度优先的多趟扫描算法 在Apriori 算法中，项目是按字典

17、排序，Lk记为频繁k 项目集构成的集合，Ck记为候选k 项目集构成的集合l下面是Apriori 算法的伪代码:l输入: 事务数据库D，最小支持度minsup;l输出: D 中的频繁项目集L;l( 1) L1 = Frequent 1 itemsets ;l( 2) for ( k = 2; Lk 1; k + + ) do beginl( 3) Ck = apriori gen ( Lk 1l) ; / /从Lk 1l产生新的候选k 项目集/ /l( 4) for all transactiona t D do beginl( 5) Ct = subset ( Ckl，tl) ; / /产生t

18、 中的候选子集/ /l( 6) for all candidates c Ct dol( 7) c count + + ;l( 8) endl( 9) Lk = c Ck c countminsup ;l( 10) endl( 11) L =kLkl;2022-5-10生物信息学数据挖掘19lApriori gen 是以频繁( k 1) 项目集Lk 1l为自变量的后选生成函数 该函数返回所有频繁k 项目l集的超集，分连接和剪枝2 步执行:l函数Apriori gen ( Lk 1l) :l( 1) insert into Ckl;l( 2) select p1，p2，pk 1，qk 1;l(

19、3) from Lk 1p，Lk 1q;l( 4) where p1= q1，p2= q22，pk 2= qk 2，pk 1 qk 1; / /连接( join) / /l( 5) For all itemsets c Ck dol( 6) For all ( k 1) subset s of c dol( 7) If ( s Lk1l) thenl( 8) delete c from Ckl; / /剪枝( prune) / /l( 9) end;l( 10) end;l( 11) answer = c Ckl ;2022-5-10生物信息学数据挖掘20运用运用Apriori 算法挖掘数据库

20、算法挖掘数据库D 的过程的过程2022-5-10生物信息学数据挖掘21数据挖掘在生物信息学中的应用数据挖掘在生物信息学中的应用l( 1) 数据清理数据清理, 数据集成数据集成, 异种、分布式数据库的语义集成。异种、分布式数据库的语义集成。l许多国家和研究组织都建立了生物序列数据库、蛋白质结构和功能数据库, 为人们提供了丰富的信息。但是这些数据分散, 且存储介质多样, 在同一数据库中存在着大量具有重复信息的序列及一些高度相似的数据, 造成数据冗余。因此对这种异构的和广泛分布的数据库的语义集成就成为一项重要任务。数据挖掘中的数据清理、数据集成方法有助于该问题的解决。l( 2) DNA 序列相似搜索

21、和比对。序列相似搜索和比对。l为识别一个新发现的基因和一个已知基因家族之间的进化关系, 确定他们的同源性或相似性, 通常需要序列比对, 找出它们之间的最大匹配, 从而定量给出其相似程度。由于序列数据是非数字的, 其内部不同种类核苷酸之间的精确交叉扮演着重要的角色。因此探索高效的搜索和比对算法在序列分析中非常重要。l( 3) 基因组特征及同时出现的基因序列的分析。基因组特征及同时出现的基因序列的分析。l对于基因家族的成组序列来说, 必须阐明多个序列之间的关系, 才能揭示整个基因家族的特征。多序列比对在识别一组相关序列中有重要生物意义。多比对算法的计算量可观, 为降低算法复杂性, 必须研究有实用价

22、值的比对算法。利用关联规则、聚类分析有助于发现一组序列之间的差异以及相似性关系, 以便对一个基因家族的特征有基本了解。另外在生物医学研究上, 人们发现疾病的产生大多数是由多基因决定的, 利用关联规则分析帮助确定在目标( 疾病) 样本中同时出现的基因种类。2022-5-10生物信息学数据挖掘22l( 4) 路径分析路径分析: 发现在不同阶段的致病因。发现在不同阶段的致病因。l引起一种疾病的基因不止一个, 不同基因在疾病的不同阶段发挥作用。利用路径分析、演变分析等找到在不同阶段的致病遗传基因序列, 可开发不同阶段的治疗药物,从而取得更有效的治疗效果。l( 5) 生物数据可视化和可视的数据挖掘。生物

23、数据可视化和可视的数据挖掘。l由于生物数据的复杂性和高维性, 既不能以数字公式表示, 也不能以逻辑公式表示, 可借助各种可视化工具以图、树、方体、链的形式展现其复杂结构和序列模式。常用的生物数据可视化工具有语义镜技术、信息壁技术、基因调控网格等。同时, 将经过数据挖掘工具得到的数据结果也以图形、图像的形式展现给用户, 便于用户寻找数据间规律和关系。l( 6) 生物文献的挖掘。生物文献的挖掘。lInternet 上生物文献日益增多, 人们通过搜索引擎获取相关信息, 但检索结果数目巨大, 准确率不高, 而且一般搜索结果只能给出标题和摘要, 不能给出文章总的关键词句。特别是生物文献数据中, 大多数蛋