基于基因本體的語義相似度計算方法研究綜述

彭佳杰　王亞東

摘 要：基因本體是一個被廣泛使用的生物數據資源，主要用于描述基因和基因產物的屬性，包括分子功能、生物過程和細胞組件三個方面?；诨虮倔w的術語相似度及基因功能相似度計算對基因功能分析、比較和預測等生物學研究熱門領域具有非常重要的意義。本文綜述了基于基因本體的語義相似度算法，主要包括基因本體同一分支中的術語相似度計算法和基因本體跨分支術語相似度算法兩大部分內容，并對這些方法的優缺點做了一定的分析總結。

關鍵詞：基因本體；語義相似度；術語相似度

中圖分類號：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篇，增長趨勢非常明顯?；虮倔w目前已經廣泛應用在基因功能比較與分析、蛋白質相互作用預測、基因集合富集分析等諸多領域，由此而成為一個不可或缺的生物醫學本體。

基因本體最初由基因本體組織（Gene Ontology consortium）于1998年建立，最早的Gene Ontology consortium僅包含研究果蠅，老鼠和酵母的科學家[2]。隨著基因本體的發展，越來越多的模式生物數據庫加入了基因本體組織，包括大多數主要的植物數據庫，動物數據庫和微生物數據庫，到2014年為止，基因本體已經能夠為85個物種提供注釋信息[3-4]。

1基因本體術語相似度計算的研究概述

基于本體計算兩個實體之間的語義相似度一直以來都是計算機科學領域的熱門問題[5]，已經有很長的研究歷史[6]，在自然語言處理[7]、音頻信號處理[8]、信息檢索[9]等諸多重要領域都有非常廣泛的運用。隨著本體理論和技術的發展，在信息挖掘和數據整合領域，越來越多的研究試圖建立本體和語義相似度為基礎的機制來比較兩個對象，以實現檢索，數據集成等功能[10-13]?；诒倔w的相似度計算主要利用本體中節點之間的父子關系、兄弟關系等結構關系來計算本體中節點之間的相似度。

根據比較對象的不同，可以把基于基因本體的術語相似度算法分成兩大類：一類是比較同一個基因本體分支中兩個術語之間的相似度；另一類是比較基因本體不同分支中（跨分支）的兩個術語之間的相似度。圖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.