Graph-based Semantic Similarity Measure

Example(s):
- a GO-Graph-based Semantic Similarity Measure such as:
  - SimGIC Semantic Similarity Measure (e.g. Pesquita et al., 2008; 2007),
  - SimUI Semantic Similarity Measure (e.g. Genteman,2009, Guo et al., 2006),
  - GOGO Semantic Similarity Measure (Zhao & Wang, 2018),
- …
Counter-Example(s):
See: Weighted Directed Graph, Semantic Similarity Neural Network, Topological Semantic Similarity Measure,

References

(Zhao & Wang, 2018) &rArr Chenguang Zhao, and Zheng Wang (2018)."GOGO: An Improved Algorithm to Measure the Semantic Similarity between Gene Ontology Terms". In: Scientific Reports volume 8, Article number: 15107.
- QUOTE: Measuring the semantic similarity between Gene Ontology (GO) terms is an essential step in functional bioinformatics research. We implemented a software named GOGO for calculating the semantic similarity between GO terms. GOGO has the advantages of both information-content-based and hybrid methods, such as Resnik’s and Wang’s methods. Moreover, GOGO is relatively fast and does not need to calculate information content (IC) from a large gene annotation corpus but still has the advantage of using IC. This is achieved by considering the number of children nodes in the GO directed acyclic graphs when calculating the semantic contribution of an ancestor node giving to its descendent nodes. GOGO can calculate functional similarities between genes and then cluster genes based on their functional similarities. Evaluations performed on multiple pathways retrieved from the saccharomyces genome database (SGD) show that GOGO can accurately and robustly cluster genes based on functional similarities.

(Gentleman, 2009) ⇒ R. Gentleman (2009). "Visualizing and Distances Using GO".
- QUOTE: The relationships between different GO terms, within a specific ontology are represented in the form of a directed acyclic graph. The leaves of this graph represent the most specific terms and their are edges from a specific term (child) to all less specific terms (each is a parent). The induced GO graph is the graph that obtains from taking a set of GO terms and finding all parents of those terms, and so on until the root node has been obtained.

(Pesquita et al., 2007) ⇒ Catia Pesquita, Daniel Faria, Hugo Bastos, Antonio EN Ferreira, Andre O Falcao, and Francisco M Couto (2008). "Evaluating GO-based Semantic Similarity Measures". In: SMB/ECCB 2007 SIG Meeting Program Materials, International Society for Computational Biology.
- QUOTE: We also use two graph-based similarity measures: simUI (Gentleman, 2005) and the novel simGIC (for Graph Information Content). simUI calculates similarity as the number of GO terms shared by two proteins divided by the number of GO terms they have together. simGIC is an expansion of simUI where instead of counting the terms we sum their IC.

(Guo et al., 2006) ⇒ Xiang Guo, Rongxiang Liu, Craig D. Shriver, Hai Hu, and Michael N. Liebman (2006). "Assessing Semantic Similarity Measures For The Characterization Of Human Regulatory Pathways". In: Bioinformatics, Volume 22, Issue 8.
- QUOTE: Graph similarity-based measures are estimated using GOstats package of Bioconductor (Gentleman, 2005). Each protein is associated with an induced graph that is obtained by taking the most specific GO terms annotated with the protein and by finding all parents of those terms until the root node has been obtained. Two methods, union-intersection (UI) and longest shared path (LP), are used to calculate the between-graph similarity. The first method uses the number of nodes two induced graphs share divided by the total number of nodes in two graphs. The resulting similarity values are bounded between 0 and 1 with more similar proteins having values near 1. The second method, LP, adopts the depth of the longest path shared by two induced graphs as the similarity score. The larger the depth the more similar two proteins are. If two proteins are both quite specific and similar, they should have long shared path and thus high similarity score.