vignettes/v05_term_similarity.Rmd
v05_term_similarity.Rmd
The methods of semantic similarity implemented in simona are mainly from the supplementary file of the paper “Mazandu et al., Gene Ontology semantic similarity tools: survey on features and challenges for biological knowledge discovery. Briefings in Bioinformatics 2017”. Original denotations have been slightly modified to make them more consistent. Also more explanations have been added in this vignette.
The following denotations will be used throughout the vignette. The denotations are mainly from Mazandu 2017 only with small modifications.
Denotation | Description |
---|---|
The root term of the DAG. In simona there is always one root term. | |
The depth of a term in the DAG, which is the longest distance from root . | |
The length of the longest path from root to a term via term . | |
The maximal depth in the DAG. | |
The height of term in the DAG, which is the longest finite distance to leaf terms. | |
The set of child terms of term . | |
The set of parent terms of term . | |
The set of ancestor terms of term . | |
The set of ancestor terms of term , including itself. | |
The set of offspring terms of term . | |
The set of offspring terms of term , including itself. | |
The set of leaf terms that term can reach. | |
Number of elements in set . | |
The shortest distance bewteen and . | |
The longest distance bewteen and . | |
The length of the longest path from and via . | |
The set of common ancestors of term and , i.e. . | |
Lowest common ancestor of and , which is the common ancestor with the largest depth in DAG, i.e. There might be more than one LCA terms for given two terms, to simplify the calculation, the one with the longest distance (the default) to and is used. | |
Nearest common ancestor of and , i.e. If there are more than one NCA terms, the one with the largest depth (the lowest one) is used. | |
Most informative common ancestor of and , i.e. There might be more than one MICA terms for given two terms, the one with the longest distance (the default) to and is used. | |
The set of annotated items on term . |
Assume term is an ancestor of term , (the order of and does not matter) is the normal shortest distance from to in a directed graph. The definition is similar for .
If term and are not in offspring/ancestor relationship, i.e. is not an ancestor of , and is not an ancestor of , then
The wrapper function term_sim()
calculates semantic similarities between terms in the DAG with a specific method. Note the method name can be partially matched. control
argument controls parameters for specific methods.
term_sim(dag, terms, method = ..., control = list(...))
All supported term similarity methods are:
## [1] "Sim_Lin_1998" "Sim_Resnik_1999" "Sim_FaITH_2010"
## [4] "Sim_Relevance_2006" "Sim_SimIC_2010" "Sim_XGraSM_2013"
## [7] "Sim_EISI_2015" "Sim_AIC_2014" "Sim_Zhang_2006"
## [10] "Sim_universal" "Sim_Wang_2007" "Sim_GOGO_2018"
## [13] "Sim_Rada_1989" "Sim_Resnik_edge_2005" "Sim_Leocock_1998"
## [16] "Sim_WP_1994" "Sim_Slimani_2006" "Sim_Shenoy_2012"
## [19] "Sim_Pekar_2002" "Sim_Stojanovic_2001" "Sim_Wang_edge_2012"
## [22] "Sim_Zhong_2002" "Sim_AlMubaid_2006" "Sim_Li_2003"
## [25] "Sim_RSS_2013" "Sim_HRSS_2013" "Sim_Shen_2010"
## [28] "Sim_SSDD_2013" "Sim_Jiang_1997" "Sim_Kappa"
## [31] "Sim_Jaccard" "Sim_Dice" "Sim_Overlap"
## [34] "Sim_Ancestor"
This type of methods consider a special ancestor term of terms and , which has the highest IC among all and ’s ancestor terms. Term is called the most informative common ancestor (MICA) which can be given by:
So if two terms are identical, MICA is the term itself, and if two terms have ancestor/offspring relationship, MICA is the ancestor term.
In the following sections, if not specially mentioned, is always referred to the MICA of and .
The similarity is calculated as the IC of the MICA term normalized by the average of the IC of the two terms:
term_sim(dag, terms, method = "Sim_Lin_1998")
Paper link: https://dl.acm.org/doi/10.5555/645527.657297.
IC of the MICA term itself can be a measure of how similar two terms are, but its range is not in [0, 1]
. There are several ways to normalize to the range of [0, 1]
. Note some of the normalization methods are restricted to IC_annotation as the IC method.
It is normalized to the possible maximal IC value where a term only has one item annotated.
where is the total number of items annotated to the whole DAG.
It is similar to Nunif, but normalized to the maximal IC of all terms in the DAG. If there is a term with only one item annotated, Nmax is identical to the Nunif method.
is normalized by the maximal IC of term and .
Paper link: https://doi.org/10.1613/jair.514, https://doi.org/10.1186/1471-2105-9-S5-S4, https://doi.org/10.1186/1471-2105-11-562, https://doi.org/10.1155/2013/292063.
The normalization method can be set with the norm_method
parameter:
term_sim(dag, terms, method = "Sim_Resnik_1999", control = list(norm_method = "Nunif")) term_sim(dag, terms, method = "Sim_Resnik_1999", control = list(norm_method = "Nmax")) term_sim(dag, terms, method = "Sim_Resnik_1999", control = list(norm_method = "Nunivers"))
It is calculated as:
The relation between the FaITH_2010 similarity and Lin_1998 similarity is:
term_sim(dag, terms, method = "Sim_FaITH_2010")
Paper link: https://doi.org/10.1007/978-3-642-17746-0_39.
If thinking Lin_1998 is a measure of how close term and are to their MICA term , the relevance method corrects it by multiplying a factor which considers the specificity of how brings the information. The factor is calculated as where is the annotation-based probability where is the number of items annotated to and is the total number of items annotated to the DAG. Then under the Relevance method, the corrected IC of is:
If using Lin_1998 as the similarity method, the corrected version Relevance similarity is:
The term requires that terms should be annotated to items. However, it can be extended to more general scenarios:
term_sim(dag, terms, method = "Sim_Relevance_2006")
Paper link: https://doi.org/10.1186/1471-2105-7-302
The SimIC_2010 method is an improved correction method of the Relevance method because the latter works badly when is very small. E.g., when is used as a correction factor, it cannot nicely distinguish and because for both are very close to 1.
The SimIC_2010 correction factor for MICA term is:
Then the similarity (if using Lin_1998 as the original similarity method) is:
Similarly, it can be generalized to:
term_sim(dag, terms, method = "Sim_SimIC_2010")
Paper link: https://doi.org/10.48550/arXiv.1001.0958.
Being different from the Relevance and SimIC_2010 methods that only use the IC of the MICA term, the XGraSM_2013 method as well as the next method use IC of a subset of common ancestor terms of and , and it uses the mean IC of them. The subset of common ancestor may have different names for different methods.
XGraSM_2013 is the simplest one which uses informative common ancestors (ICA) where IC of the common ancestor is positive.
And mean IC among all ICA terms:
And applying Lin_1998 method, the semantic similarity is:
term_sim(dag, terms, method = "Sim_XGraSM_2013")
Paper link: https://doi.org/10.1186/1471-2105-14-284
It selects a specific subset of common ancestors of terms and . It only selects a common ancestor which can reach or via one of its child terms that does not belong to the common ancestors (mutual exclusively in ’s ancestors or in ’s ancestors). The set of the selected common ancestors is called the exclusively inherited common ancestors (EICA).
And mean IC among all EICA terms:
And applying Lin_1998 method, the semantic similarit is:
term_sim(dag, terms, method = "Sim_EISI_2015")
Paper link: https://doi.org/10.1016/j.gene.2014.12.062
It uses the aggregate information content from ancestors. First define the semantic weight denoted as of a term in the DAG:
Then the similarity is calculated as the fraction of aggegation from common ancestors and the average aggregation from ancestors of and separately.
term_sim(dag, terms, method = "Sim_AIC_2014")
Paper link: https://doi.org/10.1109/tcbb.2013.176.
It uses the IC_Zhang_2006 IC method and uses Lin_1998 similarity method to calculate similarities:
term_sim(dag, terms, method = "Sim_Zhang_2006")
It uses the IC_universal IC method and uses the Nunivers method to calculate similarities:
term_sim(dag, terms, method = "Sim_universal")
Similar as the Sim_AIC_2014 method, it is also aggregation from ancestors, but it uses the “S-value” introduced in the IC_Wang_2007 sectionn in 4. Information content.
The contribution of different semantic relations can be set with the contribution_factor
parameter. The value should be a named numeric vector where names should cover the relations defined in relations set in create_ontology_DAG()
. For example, if there are two relations “relation_a” and “relation_b” set in the DAG, the value for contribution_factor can be set as:
term_sim(dag, terms, method = "Sim_Wang_2007", control = list(contribution_factor = c("relation_a" = 0.8, "relation_b" = 0.6)))
By default 0.8 is set for “is_a” and 0.6 for “part_of”.
If you are not sure what types of relations have been set, simply type the dag
object. The relation types will be printed there.
Paper link: https://doi.org/10.1093/bioinformatics/btm087.
It is very similar as Sim_Wang_2007 except there is a correction for the contribution factor. When calculating the “S-value” introduced in the IC_Wang_2007 sectionn in 4. Information content, for a parent and a child, the weight variable is directly determined by the relation type, e.g, 0.8 for “is_a”. In Sim_GOGO_2018, the number of child terms is also considered for :
where is the number of child terms of the parent , is the original contribution factor directly assigned for each relation type. is selected to ensure (assuming minimal number of children is 1), which is normally:
By default, 0.4 is assigned for “is_a” and 0.3 is assigned for “part_of”, is set to 2/3 (solve 1 = 1/(c + 1) + 0.4
).
term_sim(dag, terms, method = "Sim_GOGO_2018", control = list(contribution_factor = c("relation_a" = 0.4, "relation_b" = 0.3)))
Paper link: https://doi.org/10.1038/s41598-018-33219-y.
Methods introduced in this section relies on the distance between terms. Many methods are defined originally based on the shortest distance between two terms. This section extends them to also support their longest distance via the LCA term.
It is based on the distance between term and . It is defined as:
which is based on the shortest distance between and . Optionally, the distance can also be the longest distance via the LCA term .
There is a parameter distance which takes value of "longest_distances_via_LCA"
(the default) or "shortest_distances_via_NCA"
:
term_sim(dag, terms, method = "Sim_Rada_1989", control = list(distance = "shortest_distances_via_NCA"))
Paper link: https://doi.org/10.1109/21.24528.
It is a normalized distance:
where can be thought as the possible maximal distance between two terms in the DAG.
Similarly, the distance can also be the longest distance via LCA, then it is consistent with the definition of which are both based on the longest distance.
There is a parameter distance which takes value of "longest_distances_via_LCA"
(the default) or "shortest_distances_via_NCA"
:
term_sim(dag, terms, method = "Sim_Resnik_edge_2005", control = list(distance = "shortest_distances_via_NCA"))
Paper link: https://doi.org/10.1145/1097047.1097051.
It is similar as the Sim_Resnik_edge_2005 method, but it applies log-transformation on the distance and the depth:
where can be thought as the possible maximal distance between two terms in the DAG.
Similarly, the distance can also be the longest distance via LCA, then it is consistent with the definition of which are both based on the longest distance.
There is a parameter distance which takes value of "longest_distances_via_LCA"
(the default) or "shortest_distances_via_NCA"
:
term_sim(dag, terms, method = "Sim_Leocock_1998", control = list(distance = "shortest_distances_via_NCA"))
Paper link: https://ieeexplore.ieee.org/document/6287675.
It is based on the depth of the LCA term and the longest distance between term and via :
And it can also be written in the Lin_1998 form:
where in the denominator are the depths of and via .
term_sim(dag, terms, method = "Sim_WP_1994")
Paper link: https://doi.org/10.3115/981732.981751.
It is a correction of the Sim_WP_1994 method. The correction factor for term and regarding to their LCA term is:
The correction factor is based whether and are in ancestor/offspring relationship or not.
term_sim(dag, terms, method = "Sim_Slimani_2006")
Paper link: https://zenodo.org/record/1075130.
It is also a correction of the Sim_WP_1994 method. The correction factor for term and is:
can be replaced with if the longest distance is used.
There is a parameter distance which takes value of "longest_distances_via_LCA"
(the default) or "shortest_distances_via_NCA"
:
term_sim(dag, terms, method = "Sim_Shenoy_2012", control = list(distance = "shortest_distances_via_NCA"))
Paper link: https://doi.org/10.48550/arXiv.1211.4709.
It is very similar to the Sim_WP_1994 method:
And the relationship to is:
term_sim(dag, terms, method = "Sim_Pekar_2002")
Paper link: https://aclanthology.org/C02-1090/.
It is purely based on the depth of term , and their LCA term .
The similarity value might be negative because there is no restrction that the path from root to or must pass .
term_sim(dag, terms, method = "Sim_Stojanovic_2001")
Paper link: https://doi.org/10.1145/500737.500762.
It is calculated as:
where is the root term.
term_sim(dag, terms, method = "Sim_Wang_edge_2012")
Paper link: https://doi.org/10.1186/1477-5956-10-s1-s18.
For a term , it first calculates a “mile-stone” value based on the depth as
The the distance bewteen term and via LCA term is:
We can change original and to and to require that the depth to reach and should go through . Then above equation becomes
Then when (the two terms are identical), and when (common ancestor only includes root) and , (root has infinite distance to the terms), reaches maximal of 1. So the similarity
ranges between 0 and 1.
term_sim(dag, terms, method = "Sim_Zhong_2002")
Paper link: https://doi.org/10.1007/3-540-45483-7_8.
It also takes accout of the distance between term and , as well as the depth of the LCA term in the DAG. The distance is calculated as:
To scale into the range of [0, 1]
, we can calculate the smallest value as zero when . reaches maximal when reach possible maximal which is . Then we can define the maximal of as
And the similarity is:
There is a parameter distance which takes value of "longest_distances_via_LCA"
(the default) or "shortest_distances_via_NCA"
:
term_sim(dag, terms, method = "Sim_AlMubaid_2006", control = list(distance = "shortest_distances_via_NCA"))
Paper link: https://doi.org/10.1109/IEMBS.2006.259235.
It is similar to the Sim_AlMubaid_2006 method, but uses a non-linear form:
There is a parameter distance which takes value of "longest_distances_via_LCA"
(the default) or "shortest_distances_via_NCA"
:
term_sim(dag, terms, method = "Sim_Li_2003", control = list(distance = "shortest_distances_via_NCA"))
Paper link: https://doi.org/10.1109/TKDE.2003.1209005.
Hybrid methods use both DAG structure information and IC.
The similarity is adjusted by the positions of term , and the LCA term in the DAG. The similarity is defined as:
where can also be the longest distance via LCA. and in the second term are defined as:
where is the depth of LCA, corresponds to the distance to leaves, which is the smaller height of and in the DAG.
There is a parameter distance which takes value of "longest_distances_via_LCA"
(the default) or "shortest_distances_via_NCA"
:
term_sim(dag, terms, method = "Sim_RSS_2013", control = list(distance = "shortest_distances_via_NCA"))
Paper link: https://doi.org/10.1371/journal.pone.0066745.
It is similar to the Sim_RSS_2013 method, but it uses information content instead of the distance to adjust the similarity.
It first defines the semantic distance between term and as the sum of the distance to their MICA term :
And the distance between an ancestor to a term is:
Similarly, the similarity is also corrected by the position of MICA term and , in the DAG:
where
And beta is the average of the maximal semantic distance of and to leaves.
where or is the leaf with the highest IC that or can reach (i.e. the most informative leaf)
term_sim(dag, terms, method = "Sim_HRSS_2013")
Paper link: https://doi.org/10.1371/journal.pone.0066745.
It is based on the information content of terms on the path connecting term and via their MICA term .
Denote a list of terms a, ..., c, ..., b
which are composed by the shortest path from to and from to , the distance between and is the sum of of the terms on the path. Denote as the set of terms on the shortest path connecting and via the MICA term , the similarity is:
The path can also be defined as the longest path via MICA. The distance
parameter controls which type of paths to use.
term_sim(dag, terms, method = "Sim_Shen_2010", control = list(distance = "longest_distances_via_LCA"))
Paper link: https://doi.org/10.1109/BIBM.2010.5706623.
It is similar to the Sim_Shen_2010 method which also sums information along the path passing through the LCA term. Instead of summing the information contents, the Sim_SSDD_2013 method sums up a so-called “T-value” which relies on the DAG structure.
Denote as the set of terms on the shortest path connecting and via the LCA term , the similarity is calculated as:
The T-value depends on the DAG structure which considers both parents and children of . The definition of is:
which means T-value of a term is an average of the weighted T-values of its parents. The weight measures the fraction of information a parent transmitting to downstream of the DAG via , defined as:
as all offsprings of are also offspring of its parent .
The path can also be defined as the longest path via MICA. The distance
parameter controls which type of paths to use.
term_sim(dag, terms, method = "Sim_SSDD_2013", control = list(distance = "longest_distances_via_LCA"))
Paper link: https://doi.org/10.1016/j.ygeno.2013.04.010.
First semantic distance between term and via MICA term is defined as:
Then there are several normalization methods to change the distance to similarity and to scale it into the range of [0, 1]
.
"max"
:
"Couto"
:
"Lin"
: which is the same as the Sim_Lin_1998 method"Garla"
:
"log-Lin"
:
"Rada"
:
The normalization methods can be set via the parameter norm_method
:
term_sim(dag, terms, method = "Sim_Jiang_1997", control = list(norm_method = "max")) term_sim(dag, terms, method = "Sim_Jiang_1997", control = list(norm_method = "Couto")) term_sim(dag, terms, method = "Sim_Jiang_1997", control = list(norm_method = "Lin")) term_sim(dag, terms, method = "Sim_Jiang_1997", control = list(norm_method = "Garla")) term_sim(dag, terms, method = "Sim_Jiang_1997", control = list(norm_method = "log-Lin")) term_sim(dag, terms, method = "Sim_Jiang_1997", control = list(norm_method = "Rada"))
Paper link: https://aclanthology.org/O97-1002/.
Denote and as the sets of items annotated to term and , and as the universe set of all items annotated to the DAG.
The definition of kappa coeffient is a little bit complex. First let’s format the two sets into a contigency table:
In set B | |||
Yes | No | ||
In set A | Yes | a | b |
No | c | d |
where , , , are the numbers of items that fall in each category.
Let’s calculate (probability of observed agreement, both yes or both no) and (probability of expected agreement) as:
where is the probability of an item in both sets or neither in both sets, is the probability of an item in both sets by random (by assuming the events of an item in set and set are independent), is the probability of an item not in the two sets by random, and is the probability of an item either both in the two sets or not in the two sets by random.
The kappa coeffcient is calculated as:
Note the Kappa coeffcient is possible to be negative.
The universe set can be set via the parameter anno_universe
. By default it is the total items annotated to the whole DAG.
term_sim(dag, terms, method = "Sim_kappa", control = list(anno_universe = ...))
Definitions of the Jaccard, Dice and overlap coeffcients are similar. The Jaccard coeffcient is:
The Dice coeffcient is:
The overlap coeffcient is:
Dice and Jaccard coeffcients have a relation of:
The universe set can be set via the parameter anno_universe
. By default it is the total items annotated to the whole DAG.
term_sim(dag, terms, method = "Sim_Jaccard", control = list(anno_universe = ...)) term_sim(dag, terms, method = "Sim_Dice", control = list(anno_universe = ...)) term_sim(dag, terms, method = "Sim_Overlap", control = list(anno_universe = ...))
## R version 4.4.1 (2024-06-14)
## Platform: x86_64-apple-darwin20
## Running under: macOS Sonoma 14.5
##
## Matrix products: default
## BLAS: /Library/Frameworks/R.framework/Versions/4.4-x86_64/Resources/lib/libRblas.0.dylib
## LAPACK: /Library/Frameworks/R.framework/Versions/4.4-x86_64/Resources/lib/libRlapack.dylib; LAPACK version 3.12.0
##
## locale:
## [1] en_GB.UTF-8/en_GB.UTF-8/en_GB.UTF-8/C/en_GB.UTF-8/en_GB.UTF-8
##
## time zone: Europe/Berlin
## tzcode source: internal
##
## attached base packages:
## [1] stats graphics grDevices utils datasets methods base
##
## other attached packages:
## [1] simona_1.3.12 knitr_1.48
##
## loaded via a namespace (and not attached):
## [1] sass_0.4.9 xml2_1.3.6 shape_1.4.6.1
## [4] digest_0.6.37 magrittr_2.0.3 evaluate_0.24.0
## [7] grid_4.4.1 RColorBrewer_1.1-3 iterators_1.0.14
## [10] circlize_0.4.16 fastmap_1.2.0 foreach_1.5.2
## [13] doParallel_1.0.17 jsonlite_1.8.8 GlobalOptions_0.1.2
## [16] promises_1.3.0 ComplexHeatmap_2.20.0 codetools_0.2-20
## [19] textshaping_0.4.0 jquerylib_0.1.4 cli_3.6.3
## [22] shiny_1.9.1 rlang_1.1.4 crayon_1.5.3
## [25] scatterplot3d_0.3-44 cachem_1.1.0 yaml_2.3.10
## [28] tools_4.4.1 parallel_4.4.1 colorspace_2.1-1
## [31] httpuv_1.6.15 GetoptLong_1.0.5 BiocGenerics_0.50.0
## [34] mime_0.12 R6_2.5.1 png_0.1-8
## [37] matrixStats_1.3.0 stats4_4.4.1 lifecycle_1.0.4
## [40] S4Vectors_0.42.1 fs_1.6.4 htmlwidgets_1.6.4
## [43] IRanges_2.38.1 clue_0.3-65 ragg_1.3.2
## [46] cluster_2.1.6 pkgconfig_2.0.3 desc_1.4.3
## [49] pkgdown_2.1.0 bslib_0.8.0 later_1.3.2
## [52] Rcpp_1.0.13 systemfonts_1.1.0 xfun_0.47
## [55] xtable_1.8-4 rjson_0.2.22 htmltools_0.5.8.1
## [58] igraph_2.0.3 rmarkdown_2.28 Polychrome_1.5.1
## [61] compiler_4.4.1