基于条目共享信息的本体条目语义相似性度量——毕业论文.docx

1、摘要摘要量化基因本体中条目对的语义相似性可以帮助人们探索生物实体在功能方面的关系。目前，一种通用的解决方法是基于条目公共祖先所包含的生物信息来衡量条目间共享的信息。然而，对于条目共享信息的测量，很多研究都有各自的缺陷和限制。本文提出了一种新的测量方法基于条目共享信息的本体条目语义相似性度量，该方法是基于一个在基因本体中多重继承关系的直观发现上提出的。该方法是从基于继承的公共祖先所包涵的生物信息上发展出来；基于继承的公共祖先节点是根据条目公共祖先的孩子节点的属性而从公共祖先集合中筛选出来的。测试结果显示，该方法计算的结果更贴近生物专家们的分析，而且该方法也有效支撑了人们对“酵母菌通路数据集中基因

2、功能分类”这一认识。另外，对于大规模数据集的实际应用，该方法是一个很有前途的基于多重继承的替代方法。关键词：语义相似性测量 基因本体 信息量 公共祖先 基于继承的公共祖先摘要ABSTRACTABSTRACTQuantifying the semantic similarities between pairs of terms in the Gene Ontology structure can help to explore the functional relationships between biological entities. A common approach to this p

3、roblem is to measure the information they have in common based on the information content of their common ancestors. However, many studies have their limitations in measuring the information two Gene Ontology terms share. This study presented a new measurement, exclusively inherited shared informati

4、on that captured the information shared by two terms based on an intuitive observation on the multiple inheritance relationships among the terms in the Gene Ontology graph. Exclusively inherited shared information was derived from the information content of the exclusively inherited common ancestors

5、, which were screened from the common ancestors according to the attribute of their direct children. As the test results show, it produced more relevant result with experts scores on the artificial dataset, and supported the prior knowledge of gene function in pathways on the Saccharomyces genome da

6、tabase. It is a promising alternative to multiple inheritance based methods for practical applications on large-scale dataset. Key words: Semantic similarity measurement Gene Ontology Information content Common ancestors Exclusively inherited common ancestorsABSTRACT目录 目录第一章 绪论 .11.1 引言 .11.2 研究现状 .

7、11.3 研究内容和目标 .31.4 论文章节安排 .3第二章 GO 与相似性度量 .52.1 GO 概述 .52.2 GO 条目的相似性度量 .52.2.1 基于边的相似性度量方法 .62.2.2 基于节点的相似性度量方法 .62.3 基因相似性度量 .82.3.1 成对比较 .82.3.2 成组比较 .92.4 本章小结 .9第三章 EISI 方法及其应用 .113.1 EISI 方法 .113.2 语义相似性计算 .133.2.1 条目相似性计算 .133.2.2 算法示例 .143.3 MICA、DCA 与 EICA 的对比分析 .163.3.1 EICA 和 MICA .163.3.

8、2 EICA 与 DCA .163.4 本章小结 .18第四章 实现与评估 .19 目录4.1 EISI 方法的实现 .194.2 实验环境和相关数据包 .204.2.1 R 语言简介以及优缺点分析 .204.2.2 GO.db 包 .214.3 测试数据处理与测试原理 .224.3.1 在人工评分数据集上测试 .224.3.2 在通路数据集上测试 .234.4 实验结果及分析 .264.4.1 人工评分数据集 .264.4.2 通路数据集 .274.5 本章小结 .29第五章 结论与展望 .315.1. 结论 .315.2 本文的不足之处和下一步的工作 .315.3 本章小结 .32致谢 .

9、33参考文献 .35第一章 绪论 1第一章 绪论1.1 引言在生物信息学中，生物实体间的比较对于生物研究来说非常重要。因为它可以帮助人们研究基因产物或基因（为了方便，下文统称为基因）之间的功能关系，并以此来推测基因的功能和生物学作用。比较传统的解决方案是基于比较进行实验的，但这既耗费时间又耗费资源。当然还有一些方案是应用生物信息学的方法来比较基因序列或结构 1。随着高通量技术的出现，造就了大量的各式各样的对基因功能进行注释的生物数据，这为我们提供了一种前途比较光明的在功能方面来比较基因的方式。除去从功能角度比较基因之外，从其它方面出发进行比较可能是不太理想的。因为即使结构相似的两个基因在功能方

10、面也未必有很高的相似性，反之亦然。然而，基于大量且多样化的生物数据来比较基因确实是一个富有挑战的任务，因为通常它们的结构都是比较松散的。为此，我们引入了各种各样的生物本体，基因本体（Gene Ontology，GO）就是其中之一，它提供了从不同数据资源关于基因功能方面比较统一的描述。这可以被用来探索生物实体之间功能联系以及在生物研究方面更多样化的应用，比如基因功能预测 3,4，基因表达数据分析 5,6，基因聚类分析 7,8，致病基因排序 9,10和蛋白质相互作用的分析 11,12等。由于基于比较实验来验证基因的功能以及基因之间的关系是一个非常耗时且代价高昂的过程，因此通过 GO 注释来预测基因

11、功能就成为了生物信息学研究理想的替代方式。当然为了更准确的探究基因本身，生物学家们也必须努力去探索如何更准确地表达 GO 条目以及基因的语义。1.2 研究现状在近几年，关于语义相似性方面的研究吸引了越来越多的生物组织关注，各种各样的方法被提出，而且一些软件包也被用于计算 GO 条目的语义相似性，其中包括 Fussimeg13、FunSimMat 14、G-SESAME 15、GFSAT 16、GOSemSim 172 基于条目共享信息的本体条目语义相似性度量和 SORA18等。这些被用来测量 GO 条目的语义相似性的方法本质上可以被分为两大类：基于边（也可以说是基于结构），该方法是基于概念上的

12、距离被提出的，所谓“概念距离”是源于 GO 图中与边的长度或类型等相关的信息；基于节点（也就是基于注释或基于信息量），在该方法中采用节点和它们的属性来计算信息量并以此来计算条目语义相似性。当然，也有些方法将上述两类方法结合来使用，也就是结合信息量和 GO 结构来计算语义相似性。基于节点的测量语义相似性的方法可能是在文献中最频繁被提及的方法了。该方法是建立在信息论上的，其原理是：两个对象共享的信息越多，相似性越高。对象包含的信息可以通过信息量（Information Content，IC）来量化，信息量是依据某个条目在 GO 结构或某个注释集合中出现的概率来计算的。信息量可以作为评估条目所拥有的

13、信息和其具体程度的一个指示器。另外，它被定义为条目 t 出现概率的负对数。Resnik 19提出了一种基于最大信息量公共祖先（Most Informative Common Ancestor，MICA 20）的衡量相似性的方法，它计算出所有公共祖先的信息量并选出其中的最大值作为条目的相似性度量。因为 Resnik 方法计算的相似性值可能大于 1，Lin 21、Jiang&Conrath 22提出了他们的改进策略，他们通过归一化使相似性值映射在 01 范围内。尽管如此，这两种计算相似性的方法还是基于 Resnik 方法的，因为它们只考虑了单一的祖先的信息量，即 MICA，它被两条目都继承了。当

14、GO 是树结构时，该理论是成立的；但是当 GO 为有向无环图（Directed Acyclic Graph，DAG）时，这些方法有问题的。因为一个节点可能有多个父节点，所以某些继承自多个祖先的生物信息将被遗漏。为了解决由多重继承引起的问题，Couto 等人 23提出了分离式公共祖先（Disjunctive Common Ancestors，DCA 23）的概念并定义了一种基于图的相似性测量方法 GraSM24（Graph-Based Similarity Measure）。在该方法中，两个条目共享的信息是源自它们的所有 DCA 并通过取它们信息量的平均值作为共享信息的衡量。随后他们改进了该方法

15、并作为一种新的方法 DiShIn20（dubbed Disjunctive Shared Information）来解决由于递归定义 DCAs 和并行解释所引起的计算复杂度的问题。无论是 GraSM 还是 DiShIn 都可以直接和那些基于 MICA 的相似性计算方法结合起来。然而，动态执行 GraSM 和 DiShIn 是非常耗时的，因为它们需要第一章 绪论 3在 GO 结构中查询两节点间的路径。为了绕过这个问题，他们预先查询并将结果存储在数据集里，以备后面计算所需。1.3 研究内容和目标为了有效地解决多重继承的问题，本文提出了一种基于继承式公共祖先（Exclusively Inherite

16、d Common Ancestors，EICA）的新理论来度量两个 GO 条目共享的信息。在此的基础上，作者提出了本体条目语义相似性度量方法-EISI（ Exclusively Inherited Shared Information）。当然，该方法也是基于条目共享信息的。类似于 GraSM 和 DiShIn，EISI 也考虑了两条目所共享的多重公共祖先，而且定义了它们公共祖先即 EICA 的信息量的平均值作为条目间共享的信息量。然而，EISI 方法只考虑了那些其孩子节点被条目对之一完全继承的那些祖先节点，即并非所有的祖先节点都被考虑在内，这意味着可以降低计算共享信息的复杂度。该方法实际上是基

17、于条目队的部分公共祖先来量化共享的信息。EISI 方法的提出是基于对 GO 多重继承的一个直观发现：只有那些被完全继承的公共祖先才能决定条目对共享的信息。我们首先构造条目的公共祖先的集合，该集合中的每一个元素代表被条目对同时继承的一个节点。然后，检查所有的公共祖先，那些其孩子被条目对之一所完全继承的节点被当作 EICA。最后取所有 EICA 的信息量的平均值作为两条目共享信息的度量。通过在人工评分数据和酵母菌数据集上做验证，结果表明利用 EISI 所计算的相似性在人工评分数据集上与专家的结果更为一致，而且其结果也有力支撑了当前人们在酵母菌通路数据集上的认识。EISI 方法有两点优势：首先，通过

18、考虑多重继承，该方法能更有效的定义两个 GO 条目之间的关系；其次，计算所有的 EICA 的时间复杂度只有 ，算法效率较基于()DCA 的方法更高。1.4 论文章节安排本文主要分为 5 个章节，如下简单介绍了一下每一章节的内容：第一章作为引言部分，分别从当前的研究背景，国内外研究现状以及本文的4 基于条目共享信息的本体条目语义相似性度量主要工作内容等几个方面对本文作一个大致的介绍。第二章介绍了本文需要用到的理论基础，包括 GO 概述、基因注释，并对当前流行的关于条目相似性和基因相似性计算方法进行分类叙述，其中涉及到了几种经典的算法。本章主要是为了使读者对整个研究领域有个初步的了解，以便于后续工

19、作的理解。第三章详细介绍 EISI 方法，包括它的理论基础以及在条目相似性和基因相似性方面的具体应用。另外，还对当今几大主流的方法和 EISI 方法进行理论上的区分和优缺点分析。 第四章对 EISI 方法进行实现以及对该方法进行测试评估。首先对 EISI 方法分步论述并代码实现；其次介绍了相关的软件环境，包括 R 语言介绍与分析以及介绍了算法实现过程中需要用到的包；最后通过在人工评分数据集和酵母菌通路数据集进行测试验证了 EISI 方法的合理性和高效性。第五章对全文进行总结性的概括，其中包括对 EISI 方法的总结；其后又提出了本文的不足之处以及相应的处理措施，以备感兴趣的读者进行下一步工作。