--- title: "Term similarity" author: "Zuguang Gu ( z.gu@dkfz.de )" date: '`r Sys.Date()`' output: html_vignette: css: main.css toc: true vignette: > %\VignetteIndexEntry{05. Term similarity} %\VignetteEngine{knitr::rmarkdown} %\VignetteEncoding{UTF-8} --- ```{r, echo = FALSE, message = FALSE} library(knitr) knitr::opts_chunk$set( error = FALSE, tidy = FALSE, message = FALSE, warning = FALSE, fig.align = "center") ``` ```{r, echo = FALSE} knitr::knit_hooks$set(pngquant = knitr::hook_pngquant) knitr::opts_chunk$set( dev = "ragg_png", fig.align = "center", pngquant = "--speed=10 --quality=30" ) ``` The methods of semantic similarity implemented in **simona** are mainly from the [supplementary file](https://academic.oup.com/bib/article/18/5/886/2562801#supplementary-data) of the paper ["Mazandu et al., Gene Ontology semantic similarity tools: survey on features and challenges for biological knowledge discovery. Briefings in Bioinformatics 2017"](https://doi.org/10.1093/bib/bbw067). Original denotations have been slightly modified to make them more consistent. Also more explanations have been added in this vignette. ## Denotations The following denotations will be used throughout the vignette. The denotations are mainly from _Mazandu 2017_ only with small modifications. | Denotation | Description | | :----- | :------------------------ | | $r$ | The root term of the DAG. In **simona** there is always one root term. | | $\delta(x)$ | The depth of a term $x$ in the DAG, which is the longest distance from root $r$. | | $\delta_s(x)$ | The length of the longest path from root $r$ to a term $x$ via term $s$. | | $\delta_\max$ | The maximal depth in the DAG. | | $\eta(x)$ | The height of term $x$ in the DAG, which is the longest finite distance to leaf terms. | | $\mathcal{C}_s$ | The set of child terms of term $s$. | | $\mathcal{P}_s$ | The set of parent terms of term $s$. | | $\mathcal{A}_s$ | The set of ancestor terms of term $s$. | | $\mathcal{A}_s^+$ | The set of ancestor terms of term $s$, including $s$ itself. | | $\mathcal{D}_s$ | The set of offspring terms of term $s$. | | $\mathcal{D}_s^+$ | The set of offspring terms of term $s$, including $s$ itself. | | $\mathcal{L}_s$ | The set of leaf terms that term $s$ can reach. | | $\left| A \right|$ | Number of elements in set $A$. | | $D_\mathrm{sp}(a, b)$ | The shortest distance bewteen $a$ and $b$. | | $\mathrm{len}(a, b)$ | The longest distance bewteen $a$ and $b$. | | $\mathrm{len}_s(a, b)$ | The length of the longest path from $a$ and $b$ via $s$. | | $\mathrm{CA}(a, b)$ | The set of common ancestors of term $a$ and $b$, i.e. $\mathrm{CA}(a, b) = \mathcal{A}_a^+ \cap \mathcal{A}_b^+$. | | $\mathrm{LCA}(a, b)$ | Lowest common ancestor of $a$ and $b$, which is the common ancestor with the largest depth in DAG, i.e. $$\operatorname*{argmax}_{t \in \mathrm{CA}(a, b)} \delta(t)$$ 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 $a$ and $b$ is used. | | $\mathrm{NCA}(a, b)$ | Nearest common ancestor of $a$ and $b$, i.e. $$\operatorname*{argmin}_{t \in \mathrm{CA}(a, b)} \left( D_\mathrm{sp}(t, a) + D_\mathrm{sp}(t, b) \right)$$ If there are more than one NCA terms, the one with the largest depth (the lowest one) is used. | | $\mathrm{MICA}(a, b)$ | Most informative common ancestor of $a$ and $b$, i.e. $$\operatorname*{argmax}_{t \in \mathrm{CA}(a, b)} \left( \mathrm{IC}(t) \right )$$ There might be more than one MICA terms for given two terms, the one with the longest distance (the default) to $a$ and $b$ is used.| | $G_s$ | The set of annotated items on term $s$. | Assume term $a$ is an ancestor of term $b$, $D_\mathrm{sp}(a, b)$ (the order of $a$ and $b$ does not matter) is the normal shortest distance from $a$ to $b$ in a directed graph. The definition is similar for $\mathrm{len}(a, b)$. If term $a$ and $b$ are not in offspring/ancestor relationship, i.e. $a$ is not an ancestor of $b$, and $b$ is not an ancestor of $a$, then $$ \begin{align*} D_\mathrm{sp}(a, b) &= \min_{t \in \mathrm{CA}(a, b)} \left( D_\mathrm{sp}(t, a) + D_\mathrm{sp}(t, b) \right) \\ \mathrm{len}(a, b) &= \max_{t \in \mathrm{CA}(a, b)} \left( \mathrm{len}(t, a) + \mathrm{len}(t, b) \right) \end{align*} $$ ## General 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: ```{r} library(simona) all_term_sim_methods() ``` ## IC-based or node-based methods This type of methods consider a special ancestor term $c$ of terms $a$ and $b$, which has the highest IC among all $a$ and $b$'s ancestor terms. Term $c$ is called the most informative common ancestor (MICA) which can be given by: $$ \mathrm{IC}(c) = \max_{t \in \mathcal{A}_a^+ \cap \mathcal{A}_b^+} \mathrm{IC}(t) $$ 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, $c$ is always referred to the MICA of $a$ and $b$. ### Sim_Lin_1998 The similarity is calculated as the IC of the MICA term $c$ normalized by the average of the IC of the two terms: $$ \mathrm{Sim}(a, b) = \frac{\mathrm{IC}(c)}{(\mathrm{IC}(a) + \mathrm{IC}(b))/2} = \frac{2 * \mathrm{IC}(c)}{\mathrm{IC}(a) + \mathrm{IC}(b)} $$ 
term_sim(dag, terms, method = "Sim_Lin_1998")
Paper link: https://dl.acm.org/doi/10.5555/645527.657297. ### Sim_Resnik_1999 IC of the MICA term itself $\mathrm{IC}(c)$ can be a measure of how similar two terms are, but its range is not in `[0, 1]`. There are several ways to normalize $\mathrm{IC}(c)$ to the range of `[0, 1]`. Note some of the normalization methods are restricted to _IC_annotation_ as the IC method. #### Nunif It is normalized to the possible maximal IC value where a term only has one item annotated. $$ \mathrm{Sim}(a, b) = \frac{\mathrm{IC}(c)}{-\log(1/N)} = \frac{\mathrm{IC}(c)}{\log N} $$ where $N$ is the total number of items annotated to the whole DAG. #### Nmax 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. $$ \mathrm{Sim}(a, b) = \frac{\mathrm{IC}(c)}{\mathrm{IC}_\mathrm{max}} $$ #### Nunivers $\mathrm{IC}(c)$ is normalized by the maximal IC of term $a$ and $b$. $$ \mathrm{Sim}(a, b) = \frac{\mathrm{IC}(c)}{\max \{ \mathrm{IC}(a), \mathrm{IC}(b) \}} $$ 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"))
### Sim_FaITH_2010 It is calculated as: $$ \mathrm{Sim}(a, b) = \frac{\mathrm{IC}(c)}{\mathrm{IC}(a) + \mathrm{IC}(b) - \mathrm{IC}(c)} $$ The relation between the _FaITH_2010_ similarity and _Lin_1998_ similarity is: $$ \mathrm{Sim}_\mathrm{FaITH} = \frac{\mathrm{Sim}_\mathrm{Lin}}{2 - \mathrm{Sim}_\mathrm{Lin}} $$ 
term_sim(dag, terms, method = "Sim_FaITH_2010")
Paper link: https://doi.org/10.1007/978-3-642-17746-0_39. ### Sim_Relevance_2006 If thinking _Lin_1998_ is a measure of how close term $a$ and $b$ are to their MICA term $c$, the relevance method corrects it by multiplying a factor which considers the specificity of how $c$ brings the information. The factor is calculated as $1-p(c)$ where $p(c)$ is the annotation-based probability $p(c) = k/N$ where $k$ is the number of items annotated to $c$ and $N$ is the total number of items annotated to the DAG. Then under the Relevance method, the corrected IC of $c$ is: $$ \mathrm{IC}_\mathrm{corrected}(c) = (1-p(c)) * \mathrm{IC}(c) $$ If using _Lin_1998_ as the similarity method, the corrected version Relevance similarity is: $$ \begin{align*} \mathrm{Sim}(a, b) & = \frac{2*\mathrm{IC}_\mathrm{corrected}(c)}{\mathrm{IC}(a) + \mathrm{IC}(b)} \\ & = (1-p(c)) * \frac{2 * \mathrm{IC}(c)}{\mathrm{IC}(a) + \mathrm{IC}(b)} \\ & = (1-p(c)) * \mathrm{Sim}_\mathrm{Lin}(a, b) \end{align*} $$ The term $p(c)$ requires that terms should be annotated to items. However, it can be extended to more general scenarios: $$ \mathrm{IC}_\mathrm{corrected}(c) = \left(1 - \exp(-\mathrm{IC}(x))\right) * \mathrm{IC}(c) $$ 
term_sim(dag, terms, method = "Sim_Relevance_2006")
Paper link: https://doi.org/10.1186/1471-2105-7-302 ### Sim_SimIC_2010 The _SimIC_2010_ method is an improved correction method of the Relevance method because the latter works badly when $p(c)$ is very small. E.g., when $1-p(c)$ is used as a correction factor, it cannot nicely distinguish $p(c) = 0.01$ and $p(c) = 0.001$ because for both $1 - p(c)$ are very close to 1. The _SimIC_2010_ correction factor for MICA term $c$ is: $$ \mathrm{IC}_\mathrm{corrected}(c) = 1 - \frac{1}{1 - \log(p(c))} * \mathrm{IC}(c) $$ Then the similarity (if using _Lin_1998_ as the original similarity method) is: $$ \mathrm{Sim}(a, b) = \left( 1 - \frac{1}{1 - \log(p(c))} \right) * \mathrm{Sim}_\mathrm{Lin}(a, b) $$ Similarly, it can be generalized to: $$ \mathrm{Sim}(a, b) = \frac{\mathrm{IC}(x)}{1 + \mathrm{IC}(x)} * \mathrm{Sim}_\mathrm{Lin}(a, b) $$ 
term_sim(dag, terms, method = "Sim_SimIC_2010")
Paper link: https://doi.org/10.48550/arXiv.1001.0958. ### Sim_XGraSM_2013 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 $a$ and $b$, 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. $$ \mathrm{ICA}(a, b) = \{c \in \mathcal{A}_a^+ \cap \mathcal{A}_b^+: \mathrm{IC}(c) > 0\} $$ And mean IC among all ICA terms: $$ \mathrm{IC}_\mathrm{mean} = \frac{1}{|\mathrm{ICA}(a, b)|} \sum_{\mathrm{t \in \mathrm{ICA}(a, b)}} \mathrm{IC}(t) $$ And applying _Lin_1998_ method, the semantic similarity is: $$ \mathrm{Sim}(a, b) = 2 * \frac{\mathrm{IC}_\mathrm{mean}}{\mathrm{IC}(a) + \mathrm{IC}(b)} $$ 
term_sim(dag, terms, method = "Sim_XGraSM_2013")
Paper link: https://doi.org/10.1186/1471-2105-14-284 ### Sim_EISI_2015 It selects a specific subset of common ancestors of terms $a$ and $b$. It only selects a common ancestor $c$ which can reach $a$ or $b$ via one of its child terms that does not belong to the common ancestors (mutual exclusively in $a$'s ancestors or in $b$'s ancestors). The set of the selected common ancestors is called the exclusively inherited common ancestors (EICA). $$ \mathrm{EICA}(a, b) = \{c \in \mathcal{A}_a \cap \mathcal{A}_b: \mathcal{C}_c \cap \left( (\mathcal{A}_a \cup \mathcal{A}_b) - (\mathcal{A}_a \cap \mathcal{A}_b) \neq \emptyset \right) \} $$ And mean IC among all EICA terms: $$ \mathrm{IC}_\mathrm{mean} = \frac{1}{|\mathrm{EICA}(a, b)|} \sum_{\mathrm{t \in \mathrm{EICA}(a, b)}} \mathrm{IC}(t) $$ And applying _Lin_1998_ method, the semantic similarit is: $$ \mathrm{Sim}(a, b) = 2 * \frac{\mathrm{IC}_\mathrm{mean}}{\mathrm{IC}(a) + \mathrm{IC}(b)} $$ 
term_sim(dag, terms, method = "Sim_EISI_2015")
Paper link: https://doi.org/10.1016/j.gene.2014.12.062 ### Sim_AIC_2014 It uses the aggregate information content from ancestors. First define the semantic weight denoted as $S_w$ of a term $t$ in the DAG: $$ S_w(t) = \frac{1}{1 + \exp \left(-\frac{1}{\mathrm{IC}(t)} \right)} $$ Then the similarity is calculated as the fraction of aggegation from common ancestors and the average aggregation from ancestors of $a$ and $b$ separately. $$ \mathrm{Sim}(a, b) = \frac{2*\sum\limits_{t \in \mathcal{A}_a^+ \cap \mathcal{A}_b^+} S_w(t) }{ \sum\limits_{t \in \mathcal{A}_a^+} S_w(t) + \sum\limits_{t \in \mathcal{A}_b^+} S_w(t) } $$ 
term_sim(dag, terms, method = "Sim_AIC_2014")
Paper link: https://doi.org/10.1109/tcbb.2013.176. ### Sim_Zhang_2006 It uses the _IC_Zhang_2006_ IC method and uses _Lin_1998_ similarity method to calculate similarities: $$ \mathrm{Sim}(a, b) = \frac{2*\mathrm{IC}_\mathrm{Zhang}(c)}{\mathrm{IC}_\mathrm{Zhang}(a) + \mathrm{IC}_\mathrm{Zhang}(b)} $$ 
term_sim(dag, terms, method = "Sim_Zhang_2006")
### Sim_universal It uses the _IC_universal_ IC method and uses the _Nunivers_ method to calculate similarities: $$ \mathrm{Sim}(a, b) = \frac{2*\mathrm{IC}_\mathrm{Univers}(c)}{\max \{ \mathrm{IC}_\mathrm{Univers}(a), \mathrm{IC}_\mathrm{Univers}(b) \}} $$ 
term_sim(dag, terms, method = "Sim_universal")
### Sim_Wang_2007 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](v4_information_content.html). $$ \mathrm{Sim}(a, b) = \frac{\sum\limits_{t \in \mathcal{A}_a^+ \cap \mathcal{A}_b^+} (S_a(t) + S_b(t)) }{ \sum\limits_{t \in \mathcal{A}_a^+} S_a(t) + \sum\limits_{t \in \mathcal{A}_b^+} S_b(t) } $$ 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. ### Sim_GOGO_2018 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](v4_information_content.html), for a parent and a child, the weight variable $w_e$ 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 $w_e$: $$ w_e = \frac{1}{c + |\mathcal{C}_t|} + w_0 $$ where $|\mathcal{C}_t|$ is the number of child terms of the parent $t$, $w_0$ is the original contribution factor directly assigned for each relation type. $c$ is selected to ensure $w_e \leq 1$ (assuming minimal number of children is 1), which is normally: $$ c = \frac{\max \{w_0\}}{1 - \max \{w_0\}} $$ By default, 0.4 is assigned for "is_a" and 0.3 is assigned for "part_of", $c$ 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. ### Sim_Ancestor This is Jaccard-like coeffcient $$ \mathrm{Sim}(a, b) = \frac{\left| \mathcal{A}^+_a \cap \mathcal{A}^+_b \right|}{\left| \mathcal{A}^+_a \cup \mathcal{A}^+_b \right|} $$ 
term_sim(dag, terms, method = "Sim_Ancestor")
# Edge-based methods 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. ### Sim_Rada_1989 It is based on the distance between term $a$ and $b$. It is defined as: $$ \mathrm{Sim}(a, b) = \frac{1}{1 + D_\mathrm{sp}(a, b)} $$ which is based on the shortest distance between $a$ and $b$. Optionally, the distance can also be the longest distance via the LCA term $c$. $$ \mathrm{Sim}(a, b) = \frac{1}{1 + \mathrm{len}_c(a, b)} = \frac{1}{1 + \mathrm{len}(c, a) + \mathrm{len}(c, b)} $$ 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. ### Sim_Resnik_edge_2005 It is a normalized distance: $$ \mathrm{Sim}(a, b) = 1 - \frac{D_\mathrm{sp}(a, b)}{2*\delta_\mathrm{max}} $$ where $2*\delta_\mathrm{max}$ 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 $\delta_\mathrm{max}$ which are both based on the longest distance. $$ \mathrm{Sim}(a, b) = 1 - \frac{\mathrm{len}_c(a, b)}{2*\delta_\mathrm{max}} $$ 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. ### Sim_Leocock_1998 It is similar as the _Sim_Resnik_edge_2005_ method, but it applies log-transformation on the distance and the depth: $$ \mathrm{Sim}(a, b) = 1 - \frac{\log(D_\mathrm{sp}(a, b))}{\log(2*\delta_\mathrm{max})} $$ where $2*\delta_\mathrm{max}$ 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 $\delta_\mathrm{max}$ which are both based on the longest distance. $$ \mathrm{Sim}(a, b) = 1 - \frac{\log(\mathrm{len}_c(a, b))}{\log(2*\delta_\mathrm{max})} $$ 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. ### Sim_WP_1994 It is based on the depth of the LCA term $c$ and the longest distance between term $a$ and $b$ via $c$: $$ \begin{align*} \mathrm{Sim}(a, b) & = \frac{2*\delta(c)}{\mathrm{len}(c, a) + \mathrm{len}(c, b) + 2*\delta(c)} \\ & = \frac{2*\delta(c)}{\mathrm{len}_c(a, b) + 2*\delta(c)} \end{align*} $$ And it can also be written in the *Lin_1998* form: $$ \begin{align*} \mathrm{Sim}(a, b) & = \frac{2*\delta(c)}{\delta(c) + \mathrm{len}(c, a) + \delta(c) + \mathrm{len}(c, b)} \\ & = \frac{2*\delta(c)}{\delta_c(a) + \delta_c(b)} \end{align*} $$ where in the denominator are the depths of $a$ and $b$ via $c$. 
term_sim(dag, terms, method = "Sim_WP_1994")
Paper link: https://doi.org/10.3115/981732.981751. ### Sim_Slimani_2006 It is a correction of the *Sim_WP_1994* method. The correction factor for term $a$ and $b$ regarding to their LCA term $c$ is: $$ \mathrm{Sim}(a, b) = \mathrm{CF}(a, b) * \mathrm{Sim}_\mathrm{WP}(a, b) $$ The correction factor $\mathrm{CF}(a, b)$ is based whether $a$ and $b$ are in ancestor/offspring relationship or not. $$ \mathrm{CF}(a, b) = \left\{ \begin{array}{ll} \min\{ \delta(a), \delta(b)\} - \delta(c) = \min\{\mathrm{len}(c, a), \mathrm{len}(c, b)\} & \textit{a} \text{ and } \textit{b} \text{ are not ancestor-offspring} \\ \frac{1}{1 + |\delta(a) - \delta(b)|} = \frac{1}{1 + \mathrm{len}(a,b)} & \textit{a} \text{ and } \textit{b} \text{ are ancestor-offspring} \end{array} \right. $$ 
term_sim(dag, terms, method = "Sim_Slimani_2006")
Paper link: https://zenodo.org/record/1075130. ### Sim_Shenoy_2012 It is also a correction of the *Sim_WP_1994* method. The correction factor for term $a$ and $b$ is: $$ \mathrm{CF}(a, b) = \left\{ \begin{array}{ll} 1 & \textit{a} \text{ and } \textit{b} \text{ are not ancestor-offspring} \\ \exp(-\frac{D_\mathrm{sp}(a, b)}{\delta_\mathrm{max}})) & \textit{a} \text{ and } \textit{b} \text{ are ancestor-offspring} \end{array} \right. $$ $D_\mathrm{sp}$ can be replaced with $\mathrm{len}(a, b)$ 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. ### Sim_Pekar_2002 It is very similar to the _Sim_WP_1994_ method: $$ \begin{align*} \mathrm{Sim}(a, b) &= \frac{\delta(c)}{\mathrm{len}(c, a) + \mathrm{len}(c, b) + \delta(c)} \\ &= \frac{\delta(c)}{\delta(c) + \mathrm{len}(c, a) + \delta(c) + \mathrm{len}(c, b) - \delta(c)} \\ &= \frac{\delta(c)}{\delta_c(a) + \delta_c(b) - \delta(c)} \end{align*} $$ And the relationship to $\mathrm{Sim}_\mathrm{WP}$ is: $$ \mathrm{Sim}_\mathrm{Pekar}(a, b) = \frac{\mathrm{Sim}_\mathrm{WP}(a, b)}{2 - \mathrm{Sim}_\mathrm{WP}(a, b)} $$ 
term_sim(dag, terms, method = "Sim_Pekar_2002")
Paper link: https://aclanthology.org/C02-1090/. ### Sim_Stojanovic_2001 It is purely based on the depth of term $a$, $b$ and their LCA term $c$. $$ \mathrm{Sim}(a, b) = \frac{\delta(c)}{\delta(a) + \delta(b) - \delta(c)} $$ The similarity value might be negative because there is no restrction that the path from root to $a$ or $b$ must pass $c$. 
term_sim(dag, terms, method = "Sim_Stojanovic_2001")
Paper link: https://doi.org/10.1145/500737.500762. ### Sim_Wang_edge_2012 It is calculated as: $$ \begin{align*} \mathrm{Sim}(a, b) & = \frac{\mathrm{len}(r, c)^2}{\mathrm{len}_c(r, a)*\mathrm{len}_c(r, b)} \\ & = \frac{\delta(c)^2}{\delta_c(a)*\delta_c(b)} \end{align*} $$ where $r$ 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. ### Sim_Zhong_2002 For a term $x$, it first calculates a "mile-stone" value based on the depth as $$ m(x) = 2^{-\delta(x) - 1} $$ The the distance bewteen term $a$ and $b$ via LCA term $c$ is: $$ \begin{align*} D(a, b) & = D(c, a) + D(c, b) \\ & = m(c) - m(a) + m(c) + m(b) \\ & = 2^{-\delta(c)} - 2^{-\delta(a) - 1} - 2^{-\delta(b) - 1} \end{align*} $$ We can change original $\delta(a)$ and $\delta(b)$ to $\delta_c(a)$ and $\delta_c(b)$ to require that the depth to reach $a$ and $b$ should go through $c$. Then above equation becomes $$ \begin{align*} D(a, b) & = 2^{-\delta(c)} - 2^{-\delta_c(a) - 1} - 2^{-\delta_c(b) - 1} \\ & = 2^{-\delta(c)} - 2^{-\delta(c)-\mathrm{len}(c,a)-1} - 2^{-\delta(c)-\mathrm{len}(c,b)-1} \\ & = 2^{-\delta(c)} \left( 1 - 2^{-\mathrm{len}(c,a)-1} - 2^{-\mathrm{len}(c,b)-1} \right) \end{align*} $$ Then when $a = b$ (the two terms are identical), $D(a, b) = 0$ and when $c = r$ (common ancestor only includes root) and $\mathrm{len}(r, a) \to \infty$, $\mathrm{len}(r, b) \to \infty$ (root has infinite distance to the terms), $D(a, b)$ reaches maximal of 1. So the similarity $$ \mathrm{Sim}(a, b) = 1 - D(a, b)$$ 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. ### Sim_AlMubaid_2006 It also takes accout of the distance between term $a$ and $b$, as well as the depth of the LCA term $c$ in the DAG. The distance is calculated as: $$ D(a, b) = \log(1 + D_\mathrm{sp}(a, b)*(\sigma_\mathrm{max} - \sigma(c))) $$ To scale $D(a, b)$ into the range of `[0, 1]`, we can calculate the smallest value as zero when $a = b$. $D(a, b)$ reaches maximal when $D_\mathrm{sp}(a, b)$ reach possible maximal which is $2*\delta_\mathrm{max}$. Then we can define the maximal of $D(a, b)$ as $$ D_\mathrm{max} = \log(1 + 2*\delta_\mathrm{max} * \delta_\mathrm{max}) $$ And the similarity is: $$ \mathrm{Sim}(a, b) = 1 - D(a, b)/D_\mathrm{max} $$ 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. ### Sim_Li_2003 It is similar to the *Sim_AlMubaid_2006* method, but uses a non-linear form: $$ \mathrm{Sim}(a, b) = \exp(-0.2*D_\mathrm{sp}(a, b)) * \tanh(0.6*\delta(c)) $$ 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 Hybrid methods use both DAG structure information and IC. ### Sim_RSS_2013 The similarity is adjusted by the positions of term $a$, $b$ and the LCA term $c$ in the DAG. The similarity is defined as: $$ \mathrm{Sim}(a, b) = \frac{\delta_\mathrm{max}}{\delta_\mathrm{max} + D_\mathrm{sp}(a, b)} * \frac{\alpha}{\alpha + \beta} $$ where $D_\mathrm{sp}(a, b)$ can also be the longest distance via LCA. $\alpha$ and $\beta$ in the second term are defined as: $$ \begin{align*} \alpha & = \delta(c) \\ \beta & = \min\{ \eta(a), \eta(b) \} \end{align*} $$ where $\alpha$ is the depth of LCA, $\beta$ corresponds to the distance to leaves, which is the smaller height of $a$ and $b$ 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. ### Sim_HRSS_2013 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 $a$ and $b$ as the sum of the distance to their MICA term $c$: $$ D(a, b) = D(c, a) + D(c, b) $$ And the distance between an ancestor to a term is: $$ \begin{align*} D(c, a) & = \mathrm{IC}(a) - \mathrm{IC}(c) \\ D(a, b) & = D(c, a) + D(c, b) = \mathrm{IC}(a) + \mathrm{IC}(b) - 2*\mathrm{IC}(c) \end{align*} $$ Similarly, the similarity is also corrected by the position of MICA term and $a$, $b$ in the DAG: $$ \mathrm{Sim}(a, b) = \frac{1}{1 + D(a, b)} * \frac{\alpha}{\alpha + \beta} $$ where $$ \alpha = \mathrm{IC}(c) $$ And beta is the average of the maximal semantic distance of $a$ and $b$ to leaves. $$ \beta = \frac{D(a, l_a) + D(b, l_b)}{2} = \frac{\mathrm{IC}(l_a) - \mathrm{IC}(a) + \mathrm{IC}(l_b) - \mathrm{IC}(b)}{2} $$ where $l_a$ or $l_b$ is the leaf with the highest IC that $a$ or $b$ can reach (i.e. the most informative leaf) $$ \mathrm{IC}(l_a) = \max_{z \in \mathcal{L}(a)} \mathrm{IC}(z) $$ 
term_sim(dag, terms, method = "Sim_HRSS_2013")
Paper link: https://doi.org/10.1371/journal.pone.0066745. ### Sim_Shen_2010 It is based on the information content of terms on the path connecting term $a$ and $b$ via their MICA term $c$. Denote a list of terms `a, ..., c, ..., b` which are composed by the shortest path from $c$ to $a$ and from $c$ to $b$, the distance between $a$ and $b$ is the sum of $1/\mathrm{IC}$ of the terms on the path. Denote $L_c(a, b)$ as the set of terms on the shortest path connecting $a$ and $b$ via the MICA term $c$, the similarity is: $$ \mathrm{Sim}(a, b) = 1 - \frac{\arctan \left( \sum\limits_{x \in L_c(a, b)} \frac{1}{\mathrm{IC}(x)} \right)}{\pi/2} $$ The path $L_c(a, b)$ 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. ### Sim_SSDD_2013 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 $L_c(a, b)$ as the set of terms on the shortest path connecting $a$ and $b$ via the LCA term $c$, the similarity is calculated as: $$ \mathrm{Sim}(a, b) = 1 - \frac{\arctan \left( \sum\limits_{x \in L_c(a, b)} T(x) \right) }{\pi/2} $$ The T-value $T(x)$ depends on the DAG structure which considers both parents and children of $x$. The definition of $T(x)$ is: $$ T(x) = \left\{ \begin{array}{ll} 1 & \text{if }\textit{x}\text{ is a root} \\ \frac{1}{|\mathcal{P}_x|} \sum\limits_{t \in \mathcal{P}_x}(w * T(t)) & \text{otherwise} \end{array} \right. $$ which means T-value of a term is an average of the weighted T-values of its parents. The weight $w$ measures the fraction of information a parent $t$ transmitting to downstream of the DAG via $x$, defined as: $$ w = \frac{|D_x^+|}{|D_t^+|} $$ $w \leq 1$ as all offsprings of $x$ are also offspring of its parent $t$. The path $L_c(a, b)$ 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. ### Sim_Jiang_1997 First semantic distance between term $a$ and $b$ via MICA term $c$ is defined as: $$ D(a, b) = \mathrm{IC}(a) + \mathrm{IC}(b) - 2*\mathrm{IC}(c) $$ Then there are several normalization methods to change the distance to similarity and to scale it into the range of `[0, 1]`. - `"max"`: $1 - \frac{D(a, b)}{2*\mathrm{IC}_\mathrm{max}}$ - `"Couto"`: $\min\{ 1, \frac{D(a, b)}{\mathrm{IC}_\mathrm{max}} \}$ - `"Lin"`: $1 - \frac{D(a, b)}{\mathrm{IC}(a) + \mathrm{IC}(b)}$ which is the same as the *Sim_Lin_1998* method - `"Garla"`: $1 - \frac{\log(D(a, b) + 1)}{\log(2*\mathrm{IC}_\mathrm{max} + 1)}$ - `"log-Lin"`: $1 - \frac{\log(D(a, b) + 1)}{\log(\mathrm{IC}(a) + \mathrm{IC}(b) + 1)}$ - `"Rada"`: $\frac{1}{1 + D(a, b)}$ 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/. ## Annotation-count based methods Denote $A$ and $B$ as the sets of items annotated to term $a$ and $b$, and $U$ as the universe set of all items annotated to the DAG. ### Sim_Kappa The definition of kappa coeffient is a little bit complex. First let's format the two sets into a contigency table:
In set B
YesNo
In set AYesab
Nocd
where $a$, $b$, $c$, $d$ are the numbers of items that fall in each category. Let's calculate $p_\mathrm{obs}$ (probability of observed agreement, both yes or both no) and $p_\mathrm{exp}$ (probability of expected agreement) as: $$ \begin{align*} p_\mathrm{obs} & = \frac{a+d}{a+b+c+d} \\ p_\mathrm{Yes} & = \frac{a+b}{a+b+c+d} * \frac{a+c}{a+b+c+d} \\ p_\mathrm{No} & = \frac{c+d}{a+b+c+d} * \frac{b+d}{a+b+c+d} \\ p_\mathrm{exp} & = p_\mathrm{Yes} + p_\mathrm{No} \end{align*} $$ where $p_\mathrm{obs}$ is the probability of an item in both sets or neither in both sets, $p_\mathrm{Yes}$ is the probability of an item in both sets by random (by assuming the events of an item in set $A$ and set $B$ are independent), $p_\mathrm{No}$ is the probability of an item not in the two sets by random, and $p_\mathrm{exp}$ 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: $$ \mathrm{Sim}(a, b) = \mathrm{Kappa}(a, b) = \frac{p_\mathrm{obs} - p_\mathrm{exp}}{1 - p_\mathrm{exp}}$$ 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 = ...))
### Sim_Jaccard, Sim_Dice and Sim_Overlap Definitions of the Jaccard, Dice and overlap coeffcients are similar. The Jaccard coeffcient is: $$ \mathrm{Jaccard}(a, b) = \frac{|A \cap B|}{|A \cup B|} $$ The Dice coeffcient is: $$ \mathrm{Dice}(a, b) = \frac{2*|A \cap B|}{|A| + |B|} $$ The overlap coeffcient is: $$ \mathrm{Overlap}(a, b) = \frac{|A \cap B|}{\min\{|A|, |B|\}} $$ Dice and Jaccard coeffcients have a relation of: $$ \mathrm{Jaccard} = \frac{\mathrm{Dice}}{2 - \mathrm{Dice}} $$ 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 = ...))
## Session Info ```{r} sessionInfo() ```