基于基因本体的语义相似度计算方法研究综述

彭佳杰　王亚东

摘 要：基因本体是一个被广泛使用的生物数据资源，主要用于描述基因和基因产物的属性，包括分子功能、生物过程和细胞组件三个方面。基于基因本体的术语相似度及基因功能相似度计算对基因功能分析、比较和预测等生物学研究热门领域具有非常重要的意义。本文综述了基于基因本体的语义相似度算法，主要包括基因本体同一分支中的术语相似度计算法和基因本体跨分支术语相似度算法两大部分内容，并对这些方法的优缺点做了一定的分析总结。

关键词：基因本体；语义相似度；术语相似度

中图分类号：TP391 文献标识号：A 文章编号：2095-2163（2015）06-

Abstract： Gene Ontology （GO） is a widely used resource to describe the attributes for gene and gene products， including three categories molecular function， biological process and cellular component. GO based term similarity and gene functional similarity calculation is of great benefit to gene function analysis， comparison and prediction. This article reviewes the common methods on semantic similarity based on gene ontology， including measures to calculate gene ontology term similarity in the same category and to compare gene ontology term in different categories. In the end， the paper summarizes some commonly used tools for analyzing gene ontology based semantic similarity calculation measurement.

Keywords： Gene Ontology； Semantic Similarity； Term Similarity

0 引言

基因本体是生物医学领域最成功的本体之一，为描述基因（基因产物）的分子功能、生物过程等相关信息提供一个规范、准确的术语集，目前被广泛应用于生物医学相关研究领域[1]。1998年至2014年之间每年发表的与基因本体相关的论文数目，由在PubMed中按年搜索关键字“Gene Ontology”而获得的统计数字。相关论文的数量由1998年的1篇开始，逐年增加到了2014年的1 388篇，增长趋势非常明显。基因本体目前已经广泛应用在基因功能比较与分析、蛋白质相互作用预测、基因集合富集分析等诸多领域，由此而成为一个不可或缺的生物医学本体。

基因本体最初由基因本体组织（Gene Ontology consortium）于1998年建立，最早的Gene Ontology consortium仅包含研究果蝇，老鼠和酵母的科学家[2]。随着基因本体的发展，越来越多的模式生物数据库加入了基因本体组织，包括大多数主要的植物数据库，动物数据库和微生物数据库，到2014年为止，基因本体已经能够为85个物种提供注释信息[3-4]。

1基因本体术语相似度计算的研究概述

基于本体计算两个实体之间的语义相似度一直以来都是计算机科学领域的热门问题[5]，已经有很长的研究历史[6]，在自然语言处理[7]、音频信号处理[8]、信息检索[9]等诸多重要领域都有非常广泛的运用。随着本体理论和技术的发展，在信息挖掘和数据整合领域，越来越多的研究试图建立本体和语义相似度为基础的机制来比较两个对象，以实现检索，数据集成等功能[10-13]。基于本体的相似度计算主要利用本体中节点之间的父子关系、兄弟关系等结构关系来计算本体中节点之间的相似度。

根据比较对象的不同，可以把基于基因本体的术语相似度算法分成两大类：一类是比较同一个基因本体分支中两个术语之间的相似度；另一类是比较基因本体不同分支中（跨分支）的两个术语之间的相似度。图1是基因本体生物过程分支和分子功能分支示意图，其中左图为生物过程分支，右图为分子功能分支。 前一类比较基因本体同一分支术语的相似度，比较的是图1中实现框内两个术语的相似度，即术语axis specification和adaxial/abaxial axis specification；后一类比较基因本体不同分支中术语的相似度，比较的是图1中虚线框内的两个术语的相似度，即术语adaxial/abaxial pattern formation和DNA binding。

2同分支术语相似度计算方法

在基因本体术语相似度计算相关研究领域，大部分研究者都关注同一基因本体分支中术语相似度的计算方法。具体地说，大部分研究者关注的是如何计算基因本体这一有向无环图中，两个节点之间的相似度，这些术语相似度计算方法可以分为两类：一类是基于边距离（Edge-based）的术语相似度计算，即利用基因本体中术语之间的关系作为术语相似度计算的基础；另一类是基于节点（Node-based）的术语相似度计算，即利用基因本体中节点和节点的注释信息作为术语相似度计算的基础[14]。

基于边的术语相似度计算方法主要是考虑在基因本体这一有向无环图中，连接两个术语的路径的长度。在这一类算法中，最常用的方法是计算两个术语在基因本体中的最短路径[15]，或者当两个术语之间存在多条路径时，考虑所有可能路径长度的平均值。另外，也可以通过两个术语在有向无环图中的公共祖先节点到根节点的距离来衡量两个术语时间的相似度。上述方法都是很直观的，都是基于以下两个假设：本体中的节点和边是均匀分布的；本体中同一个层次的边所代表的语义距离是一致的。但是这两个假设在基因本体中并不是完全正确的，因此加权的方法被提出来计算术语之间的相似度。

Pekar等人在2002年提出了一个基于边的语义相似度算法[16]，利用本体中两个术语的最低公共祖先（lowest common ancestor，lca）节点到根节点的最长路径距离来衡量两个术语之间的相似度，并且考虑了每一个术语到最低公共祖先节点之间的距离，如公式（1）所示。

（1）

公式中，c1和c2?分别表示本体中的两个术语，clca表示c1和c2的最低公共祖先节点，root表示根节点，L（x，y）表示两个术语x和y在本体中的最长路径距离。2005年，Yu等人第一次使用这个方法计算基因本体术语之间的语义相似度[17]。

Cheng等人提出了一个加权的最大公共祖先深度算法，通过不同的权值来反映每一个边在本体中的层次位置[18]。为了体现不同层次上的边所反映的不同信息，定义了一个权重因子（weighting factor），记作wt，基因本体中属于不同层次的边对应一个权重因子。给定两个基因本体术语c1和c2?，其最低公共祖先到根节点的最长路径距离为p，c1和c2的相似度如公式（2）所示。

（1-2）

式中，p大于0，特别地，当p等于0时，术语c1和c2的相似度等于0。

Wu等人提出了一个非加权的基于边的相似度算法[19]。给定两个基因本体术语c1和c2该算法，首先分别得到两个术语到根节点的所有可能路径的集合，分别记为P1和P2，c1和c2的相似度如公式（3）所示。

（3）

式中，pi和pj分别表示c1和c2到根节点的一条路径，Ti和Tj分别对应于路径pi和路径pj经过的术语的集合。

2007年，Wu Xiaomei等人改进了Wu等人的算法，提出了一个既考虑公共祖先到根节点的路径距离，又考虑了公共祖先到被比较的术语的路径距离的算法[20]。和上述基于基因本体计算两个术语之间的相似度不同，Pozo等人另辟奇径，根据基因本体分子功能分支中术语在Interpro数据库[21]中共同出现在相同集合中的次数构建出了一个功能相关的树结构，然后再计算两个术语在这个树结构中的最低公共祖先的深度[22]。此方法不完全基于基因本体计算术语相似度，提出了一种全新的思路，同时也为衡量基因本体的准确性提供了重要依据。

基于节点的术语相似度算法比较术语节点的属性以及相关节点的父亲节点、子孙节点等信息。在基于节点的术语相似度计算中被广泛运用的一个概念是信息量（Information Content），可以用其来衡量一个术语的特殊性和信息。给定一个术语t，对应信息量的定义为对数似然度的负值[23]，计算公式为：

（7）

公式中，Gt表示术语t注释的所有基因的集合，G表示基因本体中包含的所有基因的集合，|X|表示集合X中元素的数量。

虽然这个算法可以有效地计算两个术语的相似度，但是却忽略了被比较的两个术语到其最低公共祖先之间的距离。因此，Lin[24]和Jiang[25]基于信息量计算方法，分别提出了考虑被比较术语到其最低公共祖先距离的算法。

Lin和Jiang这两个方法都是利用被比较的两个术语和其最低公共祖先的信息量的不同来衡量两个术语的相似度，和只利用公共祖先的信息量的计算方法是独立的，没有充分考虑到最低公共祖先在基因本体中的绝对位置信息。

为了解决这一问题，Schlicker等人基于Lin等人的方法提出了关联相似度方法[26]。给定两个术语c1和c2，Schlicker方法利用相应最低公共祖先所注释的基因在整个基因本体分支中所有术语注释的基因中所占的比例作为权值，用来衡量最低公共祖先在基因本体中的绝对层次位置信息。

以上方法存在一个共同的缺点：虽然两个术语可能有多个共同祖先，但是只考虑其中的一个。为了解决这个问题，Couto 等人提出了GraSM算法[27]。GraSM算法用所有共同祖先的信息量的平均值代替最低共同祖先的信息量，且GraSM算法可以运用在以上几种算法中。类似地，Wang等人也提出了一种考虑所有祖先术语的算法[28]。给定一个术语c1和其父亲术语p，用Sc1，p表示p对c1的语义贡献，定义为从c1到p的所有路径中，语义贡献最大的路径。

基因本体中，同一分支内术语相似计算方法如上述介绍，主要分为基于基因本体中边的计算模型和基于基因本体中节点的计算模型两类，以上详细介绍的几个模型代表了该方向近几年的研究趋势和最新成果，是利用基因本体进行基因功能分析的重要基础之一。

3跨分支术语相似度计算方法

基因本体包含三个不同的分支：分子功能，生物过程和细胞组件。虽然三个分支在结构上是三个独立的本体，但是彼此之间的生物学关系（特别是生物过程术语和分子功能术语之间）可能为注释基因提供更好的证据[29]。更重要的是，发现不同基因本体不同分支中术语之间的关联关系可能帮助研究者解释生物现象并做出生物假设。例如，如果一个具有相同分子功能的基因集合往往会参与到多个生物过程中，类似地，这些生物过程可能相互关联，相互作用，从而在代谢层实现了这一分子功能。尽管如此，当前大多数研究者都致力于计算基因本体中同一分支内的术语相似度，只有很少的研究是关于计算基因本体中不同分支间的术语相似度。目前，研究分支之间术语的语义相似度算法可以分为两类：一种是基于关联规则挖掘 （Association Rule Mining）方法；另一种是基于文本挖掘（Text Mining）的方法，例如向量空间模型（Vector Space Model）。

Bodenreider等人提出了基于关联规则挖掘的算法来计算基因本体不同分支间的术语相似度[30]。关联规则挖掘是数据挖掘领域最基本的方法之一，主要用于从海量数据中挖掘频繁数据项之间的相互关联关系，这一方法最早是为了研究购物篮分析问题（Market Basket Analysis）而提出的[31]。关联规则挖掘可解决的问题例如：“如果一个顾客采购了商品A，那么这个顾客采购商品B的可能性是多大？如果一个顾客采购了商品A，那么这个顾客还会采购什么产品？”精确地，关联关系挖掘的相关问题可以定义为：给定I = {i1，i2，…，in}为一组值为“1”或“0”的属性集合，T={t1，t2，…，tn}为一组数据记录的集合。T中的每一条记录都是唯一的，且包含了I中的部分属性。一条规则定义为：XY，其中X，Y满足X，Y I且X∩Y为空集。为了从所有可能的规则中找出重要的规则，即可用支持度（Support score）和置信度（Confidence score）来衡量一个规则的重要程度。具体地，支持度可由公式（8）计算得到。数学公式为：

（8）

公式中，T表示所有数据记录的集合，TX表示集合T中满足属性集X的所有数据记录的集合，|T|表示集合T中包含的元素的个数。支持度主要用来衡量属性集X在所有数据记录中出现的频率。置信度可由公式（9）计算得到。计算公式为：

（9）

置信度表示的是包含属性集X的所有数据记录中，同时包含Y的百分比。在挖掘关联规则时，通常给定最小的支持度阈值和置信度阈值，如果关联规则XY在T中对应的支持度和置信度都大于给定的最小阈值，那么则认为此关联规则是重要的。

给定两个基因本体术语c1和c2，c1属于分子功能分支，c2属于生物过程分支，可以利用关联规则挖掘算法发现两者之间的关系。具体地，所有数据记录集合T={g1，g2，…，gn}，表示两个基因本体分支中涉及到的所有基因的集合，X={ c1}，Y={c2}。术语c1的基因注释中包含g1，表示数据记录g1满足属性集X。同理，术语c2的基因注释中包含g1，表示数据记录g1满足属性集Y。因此，可以利用公式（8）和公式（9）计算相应的支持度和置信度，从而进一步衡量基因本体术语c1和c2之间的关系。

当前，和基因本体同一分支内术语相似度计算方法相比，没有太多研究者关注跨分支术语相似计算方法，这是一个新兴的前沿方向。以上详细介绍的两个模型代表了该方向最近几年的最新成果，对在该方向进一步开展研究工作具有非常重要的借鉴意义，也是该方向未来研究工作的基础。

4 结束语

本文综述了基于基因本体的术语相似度算法的研究现状，从基因本体同一分支中的术语相似度计算和基因本体跨分支术语相似度计算两个方面，总结和分析了已有的术语相似度算法，并对这些方法的优缺点做了一定的分析总结。当前，基于基因本体的术语相似度算法的研究成果非常丰富，是一个热门的研究领域。但是，目前的研究主要集中在相同基因本体分支的术语相似度方法上，对于跨基因本体分支术语相似度方法研究较少，因此，跨分支基因本体术语相似度计算可能是今后的热点方向，需要进一步的投入研究。

参考文献：

[1] GENE ONTOLOGY C. The Gene Ontology project in 2008 [J]. Nucleic acids research， 2008， 36（Database issue）： D440-444.

[2] ASHBURNER M， BALL C A， BLAKE J A， et al. Gene ontology： tool for the unification of biology. The Gene Ontology Consortium [J]. Nature genetics， 2000， 25（1）： 25-29.

[3] GENE ONTOLOGY C. Gene Ontology Consortium： going forward [J]. Nucleic acids research， 2015， 43（Database issue）： D1049-1056.

[4] HARRIS M A， CLARK J， IRELAND A， et al. The Gene Ontology （GO） database and informatics resource [J]. Nucleic acids research， 2004， 32（Database issue）： D258-261.

[5] COLLINS A M， LOFTUS E F. A spreading-activation theory of semantic processing [J]. Psychological review， 1975， 82（6）： 407.

[6] MCCARTHY D. Relating WordNet senses for word sense disambiguation [J]. Making Sense of Sense： Bringing Psycholinguistics and Computational Linguistics Together， 2006： 17-24.

[7] INKPEN D， D?SILETS A. Semantic similarity for detecting recognition errors in automatic speech transcripts [C]//proceedings of the Human Language Technology Conference 2005， Vancouver， Canada：[s.n.]， 2005： 49-56.

[8] HASSAN H， HASSAN A， EMAM O. Unsupervised information extraction approach using graph mutual reinforcement[C]//proceedings of the Conference on Empirical Methods in Natural Language Processing，[S.l.]： Association for Computational Linguistics.，2006.

[9] GUARINO N， MASOLO C， VETERE G. Ontoseek： Content-based access to the web [J]. Intelligent Systems and Their Applications， IEEE， 1999， 14（3）： 70-80.

[10] HEARST M A. Automated discovery of WordNet relations [J]. WordNet： an electronic lexical database， 1998， 5： 131-151.

[11] SMEATON A F， QUIGLEY I. Experiments on using semantic distances between words in image caption retrieval[C]//Proceedings of the Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval 1996， Dublin， Ireland， 1996： 174-180 .

[12] LEE J H， KIM M H， LEE Y J. Information retrieval based on conceptual distance in IS-A hierarchies [J]. Journal of documentation， 1993， 49（2）： 188-207.

[13] PESQUITA C， FARIA D， FALCAO A O， et al. Semantic similarity in biomedical ontologies [J]. PLoS computational biology， 2009， 5（7）： e1000443.

[14] CHERKASSKY B V， GOLDBERG A V， RADZIK T. Shortest paths algorithms： Theory and experimental evaluation [J]. Math Program， 1996， 73（2）： 129-174.

[15] WU Z B， PALMER M. Verb Semantics and Lexical Selection [C]// 32nd Annual Meeting of the Association for Computational Linguistics， 1994， New Mexico， USA：[s.n.]， 1994： 133-138.

[16] PEKAR V， STAAB S. Taxonomy learning： factoring the structure of a taxonomy into a semantic classification decision[C]//Proceedings of the Proceedings of the 19th international conference on Computational linguistics 2002， Stroudsburg， USA：[s.n.]， 2002： 1-7.

[17] YU H， GAO L， TU K， et al. Broadly predicting specific gene functions with expression similarity and taxonomy similarity [J]. Gene， 2005， 352：75-81.

[18] CHENG J， CLINE M， MARTIN J， et al. A knowledge-based clustering algorithm driven by gene ontology [J]. Journal of biopharmaceutical statistics， 2004， 14（3）： 687-700.

[19] WU H， SU Z， MAO F， et al. Prediction of functional modules based on comparative genome analysis and Gene Ontology application [J]. Nucleic acids research， 2005， 33（9）： 2822-2837.

[20] WU X， ZHU L， GUO J， et al. Prediction of yeast protein-protein interaction network： insights from the Gene Ontology and annotations [J]. Nucleic acids research， 2006， 34（7）： 2137-2150.

[21] APWEILER R， ATTWOOD T K， BAIROCH A， et al. InterPro--an integrated documentation resource for protein families， domains and functional sites [J]. Bioinformatics， 2000， 16（12）： 1145-1150.

[22] DEL POZO A， PAZOS F， VALENCIA A. Defining functional distances over gene ontology [J]. BMC bioinformatics， 2008， 9：50.

[23] RESNIK P. Using information content to evaluate semantic similarity in a taxonomy [C]// Int Joint Conf Artif 1995， Montreal， Canada：[s.n.]， 1995： 448-453.

[24] LIN D. An information-theoretic definition of similarity[C]// proceedings of the ICML 1998， Madison， USA：IMLS， 1998： 296-304.

[25] JIANG J J， CONRATH D W. Semantic similarity based on corpus statistics and lexical taxonomy [J]. arXiv preprint cmp-lg/9709008， 1997，

[26] SCHLICKER A， DOMINGUES F S， RAHNENFUHRER J， et al. A new measure for functional similarity of gene products based on Gene Ontology [J]. BMC bioinformatics， 2006， 7：302.

[27] COUTO F M， SILVA M J， COUTINHO P M. Semantic similarity over the gene ontology： family correlation and selecting disjunctive ancestors[C]// Proceedings of the Proceedings of the 14th ACM international conference on Information and knowledge management 2005， Bremen， Germany：ACM， 2005： 343-344.

[28] WANG J Z， DU Z， PAYATTAKOOL R， et al. A new method to measure the semantic similarity of GO terms [J]. Bioinformatics， 2007， 23（10）： 1274-1281.

[29] MYHRE S， TVEIT H， MOLLESTAD T， et al. Additional gene ontology structure for improved biological reasoning [J]. Bioinformatics， 2006， 22（16）： 2020-2027.

[30] BODENREIDER O， AUBRY M， BURGUN A. Non-lexical approaches to identifying associative relations in the gene ontology[C]// Proceedings of the Pacific Symposium on Biocomputing Pacific Symposium on Biocomputing 2005， Hawaii， USA：[s.n.]， 2005： 91-102.

[31] AGRAWAL R， IMIELI?SKI T， SWAMI A. Mining association rules between sets of items in large databases[C]// Proceedings of the ACM SIGMOD 1993， Washington， D. C：ACM， 1993： 207-216.