BACKGROUND
biologists often need to know the set s′ of genes that are semantically related to a given set s of genes.
determining the set s′ helps in understanding gene-disease interactions and advanced disease diagnosis.
for instance, biologists in the uae are trying to determine the set of genes that are related to the genes involved in type  <dig> diabetes  .
some works  propose tools that return the set of genes that are semantically related to a given set of genes.
for instance, dyngo “retrieves genes and gene products that are relatives of input genes based on similar go annotations, and displays the related genes and gene products in an association tree”  <cit> .
other works use the concept of gene clustering in order to identify semantically related genes  <cit> .
however, most of these methods determine the semantic similarities among the genes based solely on the proximity to each other of the go terms annotating the genes, while overlook the structural dependencies among these go terms, which may lead to low recall and precision of results.
most similarity measure approaches can be classified into three: edge-based, node-based, and hybrid methods.
edge-based measures  <cit>  rely on counting edges in the graph.
in most of these measures, the shortest path length is used as a distance measure between two terms in a graph.
node-based measures  <cit>  exploit the information content  of two terms being compared and of their lca.
if this lca has high information content, the two terms are considered to be semantically similar.
hybrid methods  <cit>  combine edge-based and node-based methods.
edge-based measures assume that:  nodes and edges are uniformly distributed, and  edges at the same level in a hierarchy correspond to the same semantic distance between terms.
these assumptions are not always true in biological ontologies.
as for node-based measures, their limitations are:  they do not take into account the distance separating go terms from their lca  <cit> ,  they use ic as the major factor for determining the semantic similarity of go terms, which is inappropriate,  some of them rely only on the number of common ancestor terms, while overlooking their semantic contributions to the two terms under consideration, and  many of these methods overlook the information contained in the structure of the ontology and concentrate only on the information content of a term derived from the corpus statistics.
most of these algorithms determine the semantic similarities on term by term basis and therefore ignore the context of a gene which consists of multiple terms.
thus, such method cannot be easily implemented to infer the functional similarities among different groups of genes.
nagar et al.
<cit>  define the path length  function between two go terms as the minimum path length in the go graph between the two terms.
chagoyen and pazos  <cit>  relate the functional coherence of go terms goi and goj to the number of proteins in goj that are functionally associated with proteins in goi and use the cumulative hypergeometric distribution.
methods
in the framework of grank, the structure of go is described in terms of a graph, which we call go graph.
in this graph, go terms are nodes and the relationships between the terms are edges.
for example, figure  <dig> presents a fragment of a go graph showing the ontological relationships of  <dig> go terms.
grank accepts keyword-based queries with the form q , where gi denotes a gene  keyword.
user selects an input .
grank would then map these genes to a set of go terms.
let st denote these go terms.
grank finds the meaningful lowest common ancestors  and the meaningful top common descendants  of the set st. a meaningful lca is a lca in go graph, on which the existence of st depends.
a meaningful tcd is a tcd in go graph, whose existence depends on the set st. grank would then rank the meaningful lcas and tcds, which are then converted back to genes based on annotations and retrieved back to the user.
the genes annotated to the meaningful lcas and the meaningful tcds are the most semantically related to the user’s input genes.
figure  <dig> is an overview of our approach.
it shows the sequential processing steps for answering a query.
because there are many abbreviations of concepts in the paper, we summarize them in table  <dig>
constructing a graph based on part-of relations
notation  <dig>  keyword context : a kc is a go term annotated to a query gene product.
for example, consider figures1and3and the query q. the term “organ morphogenesis”  is a kc because the gene “jag1” is annotated to it.
let skc be a set of kcs annotating the user’s input genes.
to construct the answer for this query, grank needs to identify the meaningful lcas and the meaningful tcds of the set skc based on the concept of existence dependency.
towards this, grank will need to check all “part-of” relations in go graph, because: “part of has a specific meaning in go and a part of relation would only be added between a and b if b is necessarily part of a: wherever b exists, it is as part of a, and the presence of the b implies the presence of a”  <cit> .
“part-of relation embodies some aspects of existence dependency.
a part-of relation with existence dependent parts can simply be replaced by existence dependency: in case of existence dependent components, the existence dependency relation is identical to the part of relation”  <cit> .
since not all “part-of” relations are explicitly expressed in go graph , grank converts the go graph into a graph called part-of graph , which contains only the explicit and inferred “part-of” relations.
the lcas/tcds of kcs will be determined from the pog and not from the go graph.
a pog is a go graph after:  removing all its relations except for the “part-of” ones, and  adding the inferred “part-of” relations.
the terms a and b are connected by a “part-of” relation in the pog, if the go graph either states this relation expressly or it can be inferred from the graph using the following two inference rules described in  <cit> :  if a “is-a” b and b is “part-of” c, a is “part-of” c, and  if a is “part-of” b and b “is-a” c, a is “part-of” c.
figure  <dig> shows a fragment of pog derived from the go graph in figure  <dig>  for example, since in figure 1:  the term multicellular organismal process  “is-a” the term biological process ,  the term multicellular organismal development  “is-a” the term multicellular organismal process , and  the term system development  is “part-of” the term multicellular organismal development , then in figure  <dig> the term system development  is “part-of” the term biological process .
in figure  <dig>  each term node is accompanied with the genes annotated to it.
determining the depths of terms
we observe that in order for a lca/tcd of kcs to be meaningful, the terms located in each path from the lca/tcd to a kc in pog should have unique depths based on their “is-a” relations in go graph.
“is-a” is a simple type-subtype relation between two go terms  <cit> .
consider that:  a′ “is-a” a,  a “is-a” c,  b′ “is-a” b, and  b “is-a” c. both of the terms a and b inherit the characteristics and properties of their supertype c. therefore, a and b share common characteristics.
since a′ and b′ inherit from the characteristics and properties of terms that have the same depth , a′ and b′ share also common characteristics.
that is, if two terms have the same “is-a” depth, they share common characteristics.
on the other hand, consider that term a “part-of” term c and term b “part-of” term c. we may not be able to infer common characteristics between a and b. therefore, we use “is-a” relation and not “part-of”  for computing the depth of terms, because the depth  of a go term t based on its “is-a” relations influences the semantic relationships of t with the other terms that have no hierarchical relationships with t. thus, the depth of a term node is the number of “is-a” relations that connect it with the root term node .
for example, recall figure  <dig>  the root term biological process  has its own depth.
since both of the terms multicellular organismal process  and developmental process  inherit the same characteristics from their supertype go: <dig>  they both have the same depth.
alternatively, we can determine that these terms have the same depth, because they have the same distance to the root based on their is-a relations.
as another example, the terms kidney development , system development , multicellular organismal development , and anatomical structure morphogenesis  have the same “is-a” depth and also common characteristics.
in the pog in figure  <dig>  each set of terms that have the same depth are colored with the same color for easy reference.
for example, the terms kidney development , system development , and anatomical structure morphogenesis  are colored with the same color as an indicative that they have the same depth.
we note that the depths computed may not reveal equal conceptual depths for terms located in different subtrees in go graph.
for instance, in the example presented above, the terms kidney development and system development have the same depth even though the term kidney development is more specific than the term system development.
this is because the two terms are located in two different subtrees in go graph.
if a term has multiple “is-a” inheritances, only its longest “is-a” distance to the root is considered.
we constructed an algorithm called assigndepth  that determines the depths of go terms.
it employs breadth-first search techniques.
the input to the algorithm is go graph g = , where v is the set of term and e is the set of edges representing the relations between the terms.
g is represented by its adjacency list.
the algorithm assigns an alphabetical letter to each hierarchical level in the graph based on “is-a” relations to denote the depth of the terms in this level.
it starts at the root s, which is at level  <dig>  in the first stage, it visits all the terms that are at the distance of one “is-a” edge away.
then, it visits all the new terms that can be reached at the distance of two “is-a” edges away from root term s. this process continues until every term has been visited.
to keep track of progress, the algorithm colors each node either white or gray.
a node is discovered the first time it is encountered during the search, at which time it becomes gray.
the color of each node u ∈v is stored in variable color.
the algorithm uses a queue q to manage the set of gray nodes.
in line  <dig>  function getrelation returns the relation between two input terms u and v. each term v is assigned an alphabetical letter that depicts its depth, which is stored in variable d.
determining the meaningful lowest common ancestors and the meaningful top common descendants of kcs
we observe that in order for a lowest common ancestor  to be meaningful and in order for a top common descendant  to be meaningful:  the lca/tcd in pog should have a different depth than the kc, and  the path from the lca/tcd to the kc in the pog should not include two or more terms with the same depth.
for example, consider figure  <dig> and the query q. the kc annotating the gene “gga.4082” is nephron epithelium morphogenesis  and the kcs annotating the gene “lhx1” are nephron development , and renal vesicle morphogenesis .
one of the lcas of the two kcs go: <dig> and go: <dig> is the term nephron epithelium development .
however, go: <dig> is not a meaningful lca for go: <dig> , because its depth is the same as that of go: <dig> .
based on these observations, we now introduce proposition  <dig>
proposition 1: meaningful lca/tcd; a lca/tcd is considered meaningful, if:  the depth of the lca/tcd is different than the depths of the kcs, and  the path in the pog from the lca/tcd to each of the kcs does not include two or more terms with the same depth.
notation  <dig>  dptx; dptxdenotes the depth of go term x.
we prove observation/proposition  <dig> heuristically as follows.
first, we prove: if a lca/tcdsrkc, then dptlca/tcd≠ dptkc.
that is, in order for a lca/tcd to be meaningful, its depth should be different than the depth of the kc.
we are going to validate this observation by checking whether it conforms to the structural characteristics of existence dependency.
the concept of existence dependency was first proposed for entity-relationship modelling  <cit> .
an object x is existence-dependent on an object y if the existence of x is dependent on the existence of y <cit> .
the existence dependency concept and the srkc concept have correspondences: both denote that an object has a strong association with another object.
srkc is a set of go terms, whose existence in pog is dependent on the existence of the kc .
snoeck et al.
<cit>  argue that the existence dependency relation is a partial ordering of object types .
the authors transform an oo schema into a graph consisting of the object types found in the schema and their relations.
the object types in the graph are related only through associations that express existence dependency.
the authors demonstrated through the graph that an object type is never existence-dependent on itself.
that is, if the two objects oi and oj belong to the same type, oi cannot be dependent on oj and vice versa.
this finding is in agreement with our proposed rule, when we view:  a go term in go graph as an object, and  the go term’s depth as the type of the object.
thus, if a lca/tcd has the same depth as the kc, the lca/tcd can never be existence-dependent on the kc ; therefore, this lca/tcd is meaningless and the genes annotated to it may not be semantically related to the genes annotated to the kcs.
second, we prove: if a lca/tcd is semantically related to the kc, then dpttxdpttywhere txand tyare term nodes located between the lca/tcd and the kc in pog.
we can verify this rule as follows.
in order for lca/tcd ∈srkc, all term nodes located between the lca/tcd and the kc in the pog have to be related to the kc.
let:  term ty∈srkc,  ty be a descendant of the kc, and  term tx be a descendant of ty.
in order for tx to be semantically related to the kc, intuitively tx has to be semantically related ty, because ty relates  tx with the kc.
if tx and ty have the same depth, then tx∉srty .
therefore, in order for tx to be semantically related to the kc, dpttxdptty.
example 1: consider figure  <dig> and the query q. as shown in figure 4:  the kcs annotating the gene “lhx1” are nephron development  and renal vesicle morphogenesis , and  the kc annotating the gene “gga.4082” is nephron epithelium morphogenesis .
as shown in figure  <dig>  one of the lca of the two kcs is the term organ development .
however, by applying proposition  <dig>  this lca is meaningless, because the path in the pog from the lca to the kc  includes two terms with the same depth .
also, as shown in figure  <dig>  the term nephron epithelium development  is a meaningless lca of the two kcs, because this lca and the kc  have the same depth.
therefore, the genes annotated to these two meaningless lcas  will not be returned as the answer for the query q. by applying proposition  <dig>  the term metanephric renal vesicle morphogenesis  is a meaningful tcd of the kcs .
therefore, the gene annotated to go: <dig>  will be returned to the user as the answer for the query.
example 2: consider figure  <dig> and the query q. by applying proposition  <dig> and as demonstrated by figure  <dig>  the term organ development  is a meaningful lca for the kcs nephron xdevelopment  and nephron epithelium development .
therefore, the genes annotated to go: <dig>  are semantically related to both of the input genes “lhx1” and “jag1”.
therefore, these genes will be returned as the answer for the query.
by applying proposition  <dig>  the term metanephric renal vesicle morphogenesis  is a meaningless tcd for the kcs, because the path from go: <dig> to the kc  includes two terms with the same depth .
therefore, the gene annotated to go: <dig>  will not be returned to the user as an answer for the query.
we constructed an algorithm called determinemlca  that checks whether an input lca of kcs is meaningful.
the input to the algorithm is a set of kcs and their lca.
for each kc in the set, lines 4– <dig> examine recursively each term t′ located between the kc and the lca to check if its depth is different than the depth of the lca and also different than the depths of all terms located between t′ and the kc.
if the depths of terms between each kc and the lca are distinct, line  <dig> will report that the lca is a meaningful lca.
we also constructed an algorithm called determinemtcd that checks whether an input tcd of kcs is meaningful.
the algorithm is similar to algorithm determinemlca in figure  <dig>  except that it examines the descendants of kcs rather than their ancestors.
ranking meaningful lcas and meaningful tcds
each gene keyword of a query can be annotated to more than one go term.
therefore, there may be more than one meaningful lca/tcd for the query’s kcs.
the degree of relativity of these lcas/tcds to the kcs may vary.
accordingly, the relativity of the genes described by these lcas/tcds to the input genes may vary.
therefore, we need a mechanism that ranks these lcas/tcds.
we propose below techniques for ranking the lcas/tcds.
ranking with respect to one input gene keyword
let lcai denote that go term i is a lca for a query’s kcs; let rdenote the rank oflcai.
let kc1denote the kc annotating input gene g <dig>  intuitively, the rank of lcai ) with respect to kc <dig> is r scaled down appropriately to account for the specificity of lcai.
we scale down the rank r by a factor decayj− <dig> for each hierarchical level located between kc <dig> and lcai in go graph.
decay is a parameter that can be set to a value in the range  <dig> to  <dig> .
“j” is the number of hierarchical levels between kc <dig> and lcai.
let r denote the rank of lcai with respect to kc <dig>  r is computed as follows:
rlcai,kc1=rkc1×decayj− <dig>
in the discussion above and in equation  <dig>  we implicitly assumed that there is only one go term annotating the gene g <dig>  in case g <dig> is annotated to n go terms, we compute the rank of each term using equation  <dig>  let the computed ranks be r <dig>  r <dig>  …, rn.
the combined rank is:
r^lcai,kc1=fr <dig> r <dig> …,rn
where f is some aggregation function.
we set f = max by default, but other choices  are also possible.
overall ranking
equations  <dig> and  <dig> show the rank of lcai with respect to only one gene keyword.
in case there are m gene keywords in the query , the overall ranking is the rank of lcai with respect to the m kcs annotating these genes.
that is, the overall ranking of lcai for query q is computed as shown in equation  <dig>
rlcai=∑1≤j≤mr^lcai,kcj×proxlcai,g <dig> g <dig> …,gm
the overall ranking is the sum of the ranks with respect to each gene keyword in the query, multiplied by a measure of keyword proximity: prox).
the keyword proximity function prox) can be any function that ranges from  <dig>  to  <dig> .
by default, we set our proximity function to be inversely proportional to the size of the smallest text window in lcai containing the occurrences of all the input gene keywords g <dig>  g <dig>  …, gm.
the smallest text window is the rectangle in go graph that contains the relevant occurrences of all input gene keywords.
the height of the window/rectangle is the number of hierarchical levels between the highest and lowest go terms annotating the input gene keywords.
the width of the window/rectangle is the number of go terms between the right-most and left-most terms annotating the input gene keywords.
computingr
the algorithm for computing pagerank <cit>  of html documents employs the following formula:
pv=1−dnd+d×∑u,v∈hepunhu
•p: the pagerank of a document v
•nd: the total number of documents.
•nh: the number of out-going hyperlinks from document v.
•d is a parameter usually set to  <dig> .
•he: hyperlink edge.
as the formula above shows, pagerank is a sum of two probabilities.
the first is /nd, which is the probability of visiting document v at random.
the second is the probability of visiting document v by navigating through other documents, which is calculated by the sum of the normalized pageranks of all documents that connect to v by hyperlinks, multiplied the probability of navigation d.
we are going to adapt the pagerank formula to go graphs by mapping go terms to documents and hyperlink edges to edges connecting the go terms.
as there is a tight coupling between each two web pages connected by a hyperlink, there is a tight coupling between each two go term nodes connected by a containment edge.
if term node u is important , it is likely that its children and parents are important too.
if the children and parents of u are important , it is likely that u is important too.
by performing mapping, adaptation, and adjustments to the pagerank formula, we constructed the following formula for computing r:
rkcj=1−p1−p2skcj+p1∑svniv+p2∑svniv
sv=∑i=0k−1bia−bc−iac
•v: the parent of kcj
•p1: a discretionary parameter that denotes the probability of navigating from kcjthrough an edge to term v, because the gene the user is looking for is better described by v. in our experiments we set p <dig> to  <dig> .
•p2: a discretionary parameter that denotes the probability of navigating from term v through an edge to kcj, because the gene the user is looking for is better described by kcj.
in our experiments we set p <dig> to  <dig> .
•ni: the number of edges entering node v.
•s and s: the scores of terms v and kcj respectively, and are computed as follows.
let:  “a” be the set of genes in microarray,  “b” be the set of genes annotated to term v , and  “c” be the number of significant genes in microarray.
the score s is the probability that the number of significant genes annotated to term v is exactly “k” out of the “c” significant genesa, and it is given by the following fisher’s exact test  <cit> :
to compute s, grank provides reference sets of microarrays.
example  <dig>  provides an example illustrating the calculation of s.
example 3: consider the microarray titled “genechip human genome u133a  <dig>  array”, which represents  <dig> unique human genes and  <dig> significant unique genes.
let us compute the probability that the number of significant genes annotated to the term anatomical structure development  is exactly  <dig> out of the  <dig> significant genes of the microarray.
that is, we want to compute the score s. there are  <dig> unique genes annotated to go: <dig>  therefore, the probability is computed as shown in equation 7:
sgo:0048856=∑i=029910153i14500−10153417−i145007= <dig>
RESULTS
we experimentally evaluated the quality of grank and compared it with dyngo  <cit> .
dyngo “retrieves genes and gene products that are relatives of input genes based on similar go annotations, and displays the related genes and gene products in an association tree”  <cit> .
dyngo “can support heavier computations and supports semantic retrieval of both similar terms and gene products”  <cit> .
we implemented grank in java, run on intel core <dig> duo cpu processor, with a cpu of  <dig>  ghz and  <dig> gb of ram, under windows  <dig>
benchmarking datasets
pathways are sets of genes shown to have high functional similarity and can be used to validate similarity measures  <cit> .
a fully described pathway represents the dynamics and dependencies among a set of gene/gene products.
therefore, we used in our experiments pathways as a reference for evaluating and comparing the similarity measures/relationships of grank and of dyngo  <cit> .
given a set s of genes, the methods should return another set s′ of genes that are semantically related to s. in order for sets s and s′ to be related, s and s′ should be part of a same pathway.
we used for the evaluation two different benchmarks: kegg and pfam benchmarks.
we selected a set of  <dig> human and  <dig> yeast diverse kegg pathways ; the genes were retrieved using the dbget database  <cit> .
we selected  <dig> groups of highly related pfam entries  from the sanger pfam database  <cit> .
the percentage of non-iea annotations is different in the yeast and human.
it is about 70% for the yeast annotations compared to about 60% for the human annotations.
that is, there is a higher contribution of non-iea annotation in yeast than in human.
for each group, we retrieved the corresponding human and yeast gene identifiers from the uniprot database  <cit> .
assuming that genes belonging to the same kegg pathway are often related to a similar biological process , the similarity values calculated for this dataset should be related to the bp aspect.
also, genes sharing common domains in a pfam clan often have a similar molecular function , the similarity values calculated for this second dataset should be related to the mf aspect.
evaluating recall and precision
we measured the recall  and precision of grank and of dyngo  <cit> .
let:  gp be all genes in a pathway and n be the number of these genes, and  gm be the m genes retrieved by one of the methods as semantically related to the input gene keywords:
recall=gm∩gp/n
precision=gm∩gp/m
figures  <dig> and  <dig> show the overall average recall and precision respectively for dyngo and grank using the  <dig> genes of the two benchmarks.
figure  <dig> shows the recall and precision results obtained with the kegg pathways.
figure  <dig> shows the recall and precision results obtained with the pfam clans.
for each kegg and pfam pathway/clan , the recall and precision values are represented as histograms .
as the figures show, recall and precision values vary based on:  pathways, and  the accuracy of each of the two methods to capture the semantic similarities and relationships among gene annotations within pathways.
we can conclude that the recall and precision values for the two benchmarking datasets showed that grank significantly outperforms dyngo.
the results reveal the robustness of the grank’s method and its ability to reflect the semantic relationships among gene annotations.
table  <dig> shows the proportion of the meaningful lcas versus the meaningful tcds in the different sets of the benchmarks, where the significant answer genes are annotated to.
to further analyze the behavior of the two methods, we classified go graphs into six criteria based on the relative position of a kc in the graph and on the type of relations that connect the kc with other term nodes .
we analyzed the behavior of grank and of dyngo in terms of their recall and precision under each of the six criteria.
we computed the average recall and precision of the two methods under each of the six criteria.
the results are shown in table  <dig>
as table  <dig> shows:
grank outperforms dyngo under criteria 2– <dig>
grank does not perform well under criterion  <dig>  more research work needs to be conducted to overcome the shortcoming of this criterion.
grank achieved the same recall values and the same precision values under criteria  <dig>   <dig>  and  <dig>  which is an indicative that the locations of kcs in go graph are irrelevant to the performance of grank and that its performance does not vary with the height of a go graph.
grank performance under criteria 2– <dig> is due to:  its consideration to the structural dependencies among annotation terms and to its term-depth consideration, and  the fact that each of these criteria requires a method to account for the structural dependencies among annotation terms.
the extent of the importance of the structural dependencies among annotation terms to a criterion differs from criterion to another: it is more important to criterion  <dig> than to the other five criteria, which explains the substantial performance of grank over dyngo methods under criterion  <dig>
evaluating the impact of disregarding the ranking of meaningful lca and tcd
we modified a copy of grank by removing its capability to rank meaningful lcas and tcds.
our objective is to study the impact of overlooking the ranking of meaningful lcas and tcds on the search quality of grank.
we aim at:  measuring the decline in grank’s recall and precision as a result of disregarding ranking, and  comparing the modified copy’s recall and precision with dyngo.
if the modified copy outperforms the dyngo method, this performance would be attributed to only grank’s computation of meaningful lcas and tcds.
figures  <dig> and  <dig> show the overall average recall and precision respectively of the modified copy using the  <dig> genes of the two benchmarks .
as figure  <dig> shows, the overall average recall has not changed, which is expected, since ranking does not have an impact on recall; rather, it has an impact on precision.
as the figure  <dig> shows, the overall average precision of the modified copy is:
less than that of the original copy by 26%.
higher than that of dyngo.
we can conclude that the concept of meaningful lca and tcd has significant impact on grank’s search quality, while ranking has important but not significant impact on grank’s search quality.
evaluating an alternative approach to overcoming the shortcoming of criterion 1
as discussed previously that grank does not perform well under query criterion  <dig>  and that more research work needs to be done to overcome this limitation.
however, our objective in this test is to evaluate a counter-technique, where a complete go graph is used instead of pog for computing meaningful lcas and tcds.
therefore, terms that connect with other terms via only is-a relations will also be considered in the computation of meaningful lcas and tcds.
towards this, we modified a copy of grank so that it processes go graph instead of pog for computing meaningful lcas and tcds.
figures  <dig> and  <dig> show the average recall and precision of the modified copy using the  <dig> genes.
as figure  <dig> shows, the average recall of the modified copy is less than that of the original version by 15%, but is still higher than that of dyngo.
however, as figure  <dig> shows, the average precision of the modified copy is less than that of the original copy by 33%, and is slightly less than dyngo.
we conclude that the concept of pog has a significant impact on grank’s search quality and it compensates for the shortcoming of criterion  <dig>
CONCLUSIONS
in this paper, we proposed a search engine called grank that determines the semantic relationships among genes and gene products.
grank overcomes the limitations of current gene similarity measures by using the concept of existence dependency to determine the semantic relationships among gene annotations.
it determines the structural dependencies among the go terms annotating a given set s of genes in order to identify the set of other genes that are semantically related to the set s. towards this, the framework of grank refines the concept of lca and tcd by introducing the concept of meaningful lca and meaningful tcd.
given a set of genes g <dig>  g <dig>  …gn, grank identifies the meaningful lca and the meaningful tcd of the terms annotating g <dig>  g <dig>  …gn.
the genes annotated to the meaningful lca and the meaningful tcd have the closest semantic relationships with g <dig>  g <dig>  …gn.
grank ranks the meaningful lcas and the meaningful tcds based on their semantic relationships with kcs.
we experimentally evaluated the quality of grank and compared it with dyngo  <cit>  using kegg and pfam benchmarks.
in summary, the recall and precision values for the two benchmarking datasets showed that grank outperforms dyngo.
the experiments showed that grank does not perform well if all kcs in go graph are connected to other term nodes with only “is-a” relations.
we will investigate techniques in a future work that overcome this limitation.
endnote
athe same thing applies to the score s.
competing interests
the authors declare that they have no competing interests.
authors’ contributions
kt conceived, designed, and supervised the research.
kt drafted and revised this manuscript.
kt, ham, dm, and zam performed the implementation of the research project.
kt, ham, dm, and zam carried out the experiments and the analysis of the results.
all authors read and approved the final manuscript.

 biologists often need to know the set s′ of genes that are semantically related to a given set s of genes. determining the set s′ helps in understanding gene-disease interactions and advanced disease diagnosis. for instance, biologists in the uae are trying to determine the set of genes that are related to the genes involved in type diabetes. some works propose tools that return the set of genes that are semantically related to a given set of genes. for instance, dyngo “retrieves genes and gene products that are relatives of input genes based on similar go annotations, and displays the related genes and gene products in an association tree”. other works use the concept of gene clustering in order to identify semantically related genes. however, most of these methods determine the semantic similarities among the genes based solely on the proximity to each other of the go terms annotating the genes, while overlook the structural dependencies among these go terms, which may lead to low recall and precision of results. most similarity measure approaches can be classified into three: edge-based, node-based, and hybrid methods. edge-based measures rely on counting edges in the graph. in most of these measures, the shortest path length is used as a distance measure between two terms in a graph. node-based measures exploit the information content of two terms being compared and of their lca. if this lca has high information content, the two terms are considered to be semantically similar. hybrid methods combine edge-based and node-based methods. edge-based measures assume that: nodes and edges are uniformly distributed, and edges at the same level in a hierarchy correspond to the same semantic distance between terms. these assumptions are not always true in biological ontologies. as for node-based measures, their limitations are: they do not take into account the distance separating go terms from their lca, they use ic as the major factor for determining the semantic similarity of go terms, which is inappropriate, some of them rely only on the number of common ancestor terms, while overlooking their semantic contributions to the two terms under consideration, and many of these methods overlook the information contained in the structure of the ontology and concentrate only on the information content of a term derived from the corpus statistics. most of these algorithms determine the semantic similarities on term by term basis and therefore ignore the context of a gene which consists of multiple terms. thus, such method cannot be easily implemented to infer the functional similarities among different groups of genes. nagar et al. define the path length function between two go terms as the minimum path length in the go graph between the two terms. chagoyen and pazos relate the functional coherence of go terms goi and goj to the number of proteins in goj that are functionally associated with proteins in goi and use the cumulative hypergeometric distribution. methods in the framework of grank, the structure of go is described in terms of a graph, which we call go graph. in this graph, go terms are nodes and the relationships between the terms are edges. for example, figure  presents a fragment of a go graph showing the ontological relationships of go terms. grank accepts keyword-based queries with the form q, where gi denotes a gene keyword. user selects an input. grank would then map these genes to a set of go terms. let st denote these go terms. grank finds the meaningful lowest common ancestors and the meaningful top common descendants of the set st. a meaningful lca is a lca in go graph, on which the existence of st depends. a meaningful tcd is a tcd in go graph, whose existence depends on the set st. grank would then rank the meaningful lcas and tcds, which are then converted back to genes based on annotations and retrieved back to the user. the genes annotated to the meaningful lcas and the meaningful tcds are the most semantically related to the user’s input genes. figure  is an overview of our approach. it shows the sequential processing steps for answering a query. because there are many abbreviations of concepts in the paper, we summarize them in table  constructing a graph based on part-of relations notation keyword context: a kc is a go term annotated to a query gene product. for example, consider figures1and3and the query q. the term “organ morphogenesis” is a kc because the gene “jag1” is annotated to it. let skc be a set of kcs annotating the user’s input genes. to construct the answer for this query, grank needs to identify the meaningful lcas and the meaningful tcds of the set skc based on the concept of existence dependency. towards this, grank will need to check all “part-of” relations in go graph, because: “part of has a specific meaning in go and a part of relation would only be added between a and b if b is necessarily part of a: wherever b exists, it is as part of a, and the presence of the b implies the presence of a”. “part-of relation embodies some aspects of existence dependency. a part-of relation with existence dependent parts can simply be replaced by existence dependency: in case of existence dependent components, the existence dependency relation is identical to the part of relation”. since not all “part-of” relations are explicitly expressed in go graph, grank converts the go graph into a graph called part-of graph, which contains only the explicit and inferred “part-of” relations. the lcas/tcds of kcs will be determined from the pog and not from the go graph. a pog is a go graph after: removing all its relations except for the “part-of” ones, and adding the inferred “part-of” relations. the terms a and b are connected by a “part-of” relation in the pog, if the go graph either states this relation expressly or it can be inferred from the graph using the following two inference rules described in: if a “is-a” b and b is “part-of” c, a is “part-of” c, and if a is “part-of” b and b “is-a” c, a is “part-of” c. figure  shows a fragment of pog derived from the go graph in figure  for example, since in figure 1: the term multicellular organismal process “is-a” the term biological process, the term multicellular organismal development “is-a” the term multicellular organismal process, and the term system development is “part-of” the term multicellular organismal development, then in figure  the term system development is “part-of” the term biological process. in figure  each term node is accompanied with the genes annotated to it. determining the depths of terms we observe that in order for a lca/tcd of kcs to be meaningful, the terms located in each path from the lca/tcd to a kc in pog should have unique depths based on their “is-a” relations in go graph. “is-a” is a simple type-subtype relation between two go terms. consider that: a′ “is-a” a, a “is-a” c, b′ “is-a” b, and b “is-a” c. both of the terms a and b inherit the characteristics and properties of their supertype c. therefore, a and b share common characteristics. since a′ and b′ inherit from the characteristics and properties of terms that have the same depth, a′ and b′ share also common characteristics. that is, if two terms have the same “is-a” depth, they share common characteristics. on the other hand, consider that term a “part-of” term c and term b “part-of” term c. we may not be able to infer common characteristics between a and b. therefore, we use “is-a” relation and not “part-of” for computing the depth of terms, because the depth of a go term t based on its “is-a” relations influences the semantic relationships of t with the other terms that have no hierarchical relationships with t. thus, the depth of a term node is the number of “is-a” relations that connect it with the root term node. for example, recall figure  the root term biological process has its own depth. since both of the terms multicellular organismal process and developmental process inherit the same characteristics from their supertype go: they both have the same depth. alternatively, we can determine that these terms have the same depth, because they have the same distance to the root based on their is-a relations. as another example, the terms kidney development, system development, multicellular organismal development, and anatomical structure morphogenesis have the same “is-a” depth and also common characteristics. in the pog in figure  each set of terms that have the same depth are colored with the same color for easy reference. for example, the terms kidney development, system development, and anatomical structure morphogenesis are colored with the same color as an indicative that they have the same depth. we note that the depths computed may not reveal equal conceptual depths for terms located in different subtrees in go graph. for instance, in the example presented above, the terms kidney development and system development have the same depth even though the term kidney development is more specific than the term system development. this is because the two terms are located in two different subtrees in go graph. if a term has multiple “is-a” inheritances, only its longest “is-a” distance to the root is considered. we constructed an algorithm called assigndepth that determines the depths of go terms. it employs breadth-first search techniques. the input to the algorithm is go graph g =, where v is the set of term and e is the set of edges representing the relations between the terms. g is represented by its adjacency list. the algorithm assigns an alphabetical letter to each hierarchical level in the graph based on “is-a” relations to denote the depth of the terms in this level. it starts at the root s, which is at level in the first stage, it visits all the terms that are at the distance of one “is-a” edge away. then, it visits all the new terms that can be reached at the distance of two “is-a” edges away from root term s. this process continues until every term has been visited. to keep track of progress, the algorithm colors each node either white or gray. a node is discovered the first time it is encountered during the search, at which time it becomes gray. the color of each node u ∈v is stored in variable color. the algorithm uses a queue q to manage the set of gray nodes. in line function getrelation returns the relation between two input terms u and v. each term v is assigned an alphabetical letter that depicts its depth, which is stored in variable d. determining the meaningful lowest common ancestors and the meaningful top common descendants of kcs we observe that in order for a lowest common ancestor to be meaningful and in order for a top common descendant to be meaningful: the lca/tcd in pog should have a different depth than the kc, and the path from the lca/tcd to the kc in the pog should not include two or more terms with the same depth. for example, consider figure  and the query q. the kc annotating the gene “gga.4082” is nephron epithelium morphogenesis and the kcs annotating the gene “lhx1” are nephron development, and renal vesicle morphogenesis. one of the lcas of the two kcs go: and go: is the term nephron epithelium development. however, go: is not a meaningful lca for go:, because its depth is the same as that of go:. based on these observations, we now introduce proposition proposition 1: meaningful lca/tcd; a lca/tcd is considered meaningful, if: the depth of the lca/tcd is different than the depths of the kcs, and the path in the pog from the lca/tcd to each of the kcs does not include two or more terms with the same depth. notation dptx; dptxdenotes the depth of go term x. we prove observation/proposition heuristically as follows. first, we prove: if a lca/tcdsrkc, then dptlca/tcd≠ dptkc. that is, in order for a lca/tcd to be meaningful, its depth should be different than the depth of the kc. we are going to validate this observation by checking whether it conforms to the structural characteristics of existence dependency. the concept of existence dependency was first proposed for entity-relationship modelling. an object x is existence-dependent on an object y if the existence of x is dependent on the existence of y. the existence dependency concept and the srkc concept have correspondences: both denote that an object has a strong association with another object. srkc is a set of go terms, whose existence in pog is dependent on the existence of the kc. snoeck et al. argue that the existence dependency relation is a partial ordering of object types. the authors transform an oo schema into a graph consisting of the object types found in the schema and their relations. the object types in the graph are related only through associations that express existence dependency. the authors demonstrated through the graph that an object type is never existence-dependent on itself. that is, if the two objects oi and oj belong to the same type, oi cannot be dependent on oj and vice versa. this finding is in agreement with our proposed rule, when we view: a go term in go graph as an object, and the go term’s depth as the type of the object. thus, if a lca/tcd has the same depth as the kc, the lca/tcd can never be existence-dependent on the kc; therefore, this lca/tcd is meaningless and the genes annotated to it may not be semantically related to the genes annotated to the kcs. second, we prove: if a lca/tcd is semantically related to the kc, then dpttxdpttywhere txand tyare term nodes located between the lca/tcd and the kc in pog. we can verify this rule as follows. in order for lca/tcd ∈srkc, all term nodes located between the lca/tcd and the kc in the pog have to be related to the kc. let: term ty∈srkc, ty be a descendant of the kc, and term tx be a descendant of ty. in order for tx to be semantically related to the kc, intuitively tx has to be semantically related ty, because ty relates tx with the kc. if tx and ty have the same depth, then tx∉srty. therefore, in order for tx to be semantically related to the kc, dpttxdptty. example 1: consider figure  and the query q. as shown in figure 4: the kcs annotating the gene “lhx1” are nephron development and renal vesicle morphogenesis, and the kc annotating the gene “gga.4082” is nephron epithelium morphogenesis. as shown in figure  one of the lca of the two kcs is the term organ development. however, by applying proposition this lca is meaningless, because the path in the pog from the lca to the kc includes two terms with the same depth. also, as shown in figure  the term nephron epithelium development is a meaningless lca of the two kcs, because this lca and the kc have the same depth. therefore, the genes annotated to these two meaningless lcas will not be returned as the answer for the query q. by applying proposition the term metanephric renal vesicle morphogenesis is a meaningful tcd of the kcs. therefore, the gene annotated to go: will be returned to the user as the answer for the query. example 2: consider figure  and the query q. by applying proposition and as demonstrated by figure  the term organ development is a meaningful lca for the kcs nephron xdevelopment and nephron epithelium development. therefore, the genes annotated to go: are semantically related to both of the input genes “lhx1” and “jag1”. therefore, these genes will be returned as the answer for the query. by applying proposition the term metanephric renal vesicle morphogenesis is a meaningless tcd for the kcs, because the path from go: to the kc includes two terms with the same depth. therefore, the gene annotated to go: will not be returned to the user as an answer for the query. we constructed an algorithm called determinemlca that checks whether an input lca of kcs is meaningful. the input to the algorithm is a set of kcs and their lca. for each kc in the set, lines 4– examine recursively each term t′ located between the kc and the lca to check if its depth is different than the depth of the lca and also different than the depths of all terms located between t′ and the kc. if the depths of terms between each kc and the lca are distinct, line will report that the lca is a meaningful lca. we also constructed an algorithm called determinemtcd that checks whether an input tcd of kcs is meaningful. the algorithm is similar to algorithm determinemlca in figure  except that it examines the descendants of kcs rather than their ancestors. ranking meaningful lcas and meaningful tcds each gene keyword of a query can be annotated to more than one go term. therefore, there may be more than one meaningful lca/tcd for the query’s kcs. the degree of relativity of these lcas/tcds to the kcs may vary. accordingly, the relativity of the genes described by these lcas/tcds to the input genes may vary. therefore, we need a mechanism that ranks these lcas/tcds. we propose below techniques for ranking the lcas/tcds. ranking with respect to one input gene keyword let lcai denote that go term i is a lca for a query’s kcs; let rdenote the rank oflcai. let kc1denote the kc annotating input gene g intuitively, the rank of lcai ) with respect to kc is r scaled down appropriately to account for the specificity of lcai. we scale down the rank r by a factor decayj− for each hierarchical level located between kc and lcai in go graph. decay is a parameter that can be set to a value in the range to. “j” is the number of hierarchical levels between kc and lcai. let r denote the rank of lcai with respect to kc r is computed as follows: rlcai,kc1=rkc1×decayj− in the discussion above and in equation we implicitly assumed that there is only one go term annotating the gene g in case g is annotated to n go terms, we compute the rank of each term using equation let the computed ranks be r r …, rn. the combined rank is: r^lcai,kc1=fr r …,rn where f is some aggregation function. we set f = max by default, but other choices are also possible. overall ranking equations and show the rank of lcai with respect to only one gene keyword. in case there are m gene keywords in the query, the overall ranking is the rank of lcai with respect to the m kcs annotating these genes. that is, the overall ranking of lcai for query q is computed as shown in equation rlcai=∑1≤j≤mr^lcai,kcj×proxlcai,g g …,gm the overall ranking is the sum of the ranks with respect to each gene keyword in the query, multiplied by a measure of keyword proximity: prox). the keyword proximity function prox) can be any function that ranges from to. by default, we set our proximity function to be inversely proportional to the size of the smallest text window in lcai containing the occurrences of all the input gene keywords g g …, gm. the smallest text window is the rectangle in go graph that contains the relevant occurrences of all input gene keywords. the height of the window/rectangle is the number of hierarchical levels between the highest and lowest go terms annotating the input gene keywords. the width of the window/rectangle is the number of go terms between the right-most and left-most terms annotating the input gene keywords. computingr the algorithm for computing pagerank of html documents employs the following formula: pv=1−dnd+d×∑u,v∈hepunhu •p: the pagerank of a document v •nd: the total number of documents. •nh: the number of out-going hyperlinks from document v. •d is a parameter usually set to. •he: hyperlink edge. as the formula above shows, pagerank is a sum of two probabilities. the first is /nd, which is the probability of visiting document v at random. the second is the probability of visiting document v by navigating through other documents, which is calculated by the sum of the normalized pageranks of all documents that connect to v by hyperlinks, multiplied the probability of navigation d. we are going to adapt the pagerank formula to go graphs by mapping go terms to documents and hyperlink edges to edges connecting the go terms. as there is a tight coupling between each two web pages connected by a hyperlink, there is a tight coupling between each two go term nodes connected by a containment edge. if term node u is important, it is likely that its children and parents are important too. if the children and parents of u are important, it is likely that u is important too. by performing mapping, adaptation, and adjustments to the pagerank formula, we constructed the following formula for computing r: rkcj=1−p1−p2skcj+p1∑svniv+p2∑svniv sv=∑i=0k−1bia−bc−iac •v: the parent of kcj •p1: a discretionary parameter that denotes the probability of navigating from kcjthrough an edge to term v, because the gene the user is looking for is better described by v. in our experiments we set p to. •p2: a discretionary parameter that denotes the probability of navigating from term v through an edge to kcj, because the gene the user is looking for is better described by kcj. in our experiments we set p to. •ni: the number of edges entering node v. •s and s: the scores of terms v and kcj respectively, and are computed as follows. let: “a” be the set of genes in microarray, “b” be the set of genes annotated to term v, and “c” be the number of significant genes in microarray. the score s is the probability that the number of significant genes annotated to term v is exactly “k” out of the “c” significant genesa, and it is given by the following fisher’s exact test: to compute s, grank provides reference sets of microarrays. example provides an example illustrating the calculation of s. example 3: consider the microarray titled “genechip human genome u133a array”, which represents unique human genes and significant unique genes. let us compute the probability that the number of significant genes annotated to the term anatomical structure development is exactly out of the significant genes of the microarray. that is, we want to compute the score s. there are unique genes annotated to go: therefore, the probability is computed as shown in equation 7: sgo:0048856=∑i=029910153i14500−10153417−i145007=  we experimentally evaluated the quality of grank and compared it with dyngo. dyngo “retrieves genes and gene products that are relatives of input genes based on similar go annotations, and displays the related genes and gene products in an association tree”. dyngo “can support heavier computations and supports semantic retrieval of both similar terms and gene products”. we implemented grank in java, run on intel core duo cpu processor, with a cpu of ghz and gb of ram, under windows benchmarking datasets pathways are sets of genes shown to have high functional similarity and can be used to validate similarity measures. a fully described pathway represents the dynamics and dependencies among a set of gene/gene products. therefore, we used in our experiments pathways as a reference for evaluating and comparing the similarity measures/relationships of grank and of dyngo. given a set s of genes, the methods should return another set s′ of genes that are semantically related to s. in order for sets s and s′ to be related, s and s′ should be part of a same pathway. we used for the evaluation two different benchmarks: kegg and pfam benchmarks. we selected a set of human and yeast diverse kegg pathways; the genes were retrieved using the dbget database. we selected groups of highly related pfam entries from the sanger pfam database. the percentage of non-iea annotations is different in the yeast and human. it is about 70% for the yeast annotations compared to about 60% for the human annotations. that is, there is a higher contribution of non-iea annotation in yeast than in human. for each group, we retrieved the corresponding human and yeast gene identifiers from the uniprot database. assuming that genes belonging to the same kegg pathway are often related to a similar biological process, the similarity values calculated for this dataset should be related to the bp aspect. also, genes sharing common domains in a pfam clan often have a similar molecular function, the similarity values calculated for this second dataset should be related to the mf aspect. evaluating recall and precision we measured the recall and precision of grank and of dyngo. let: gp be all genes in a pathway and n be the number of these genes, and gm be the m genes retrieved by one of the methods as semantically related to the input gene keywords: recall=gm∩gp/n precision=gm∩gp/m figures  and show the overall average recall and precision respectively for dyngo and grank using the genes of the two benchmarks. figure  shows the recall and precision results obtained with the kegg pathways. figure  shows the recall and precision results obtained with the pfam clans. for each kegg and pfam pathway/clan, the recall and precision values are represented as histograms. as the figures show, recall and precision values vary based on: pathways, and the accuracy of each of the two methods to capture the semantic similarities and relationships among gene annotations within pathways. we can conclude that the recall and precision values for the two benchmarking datasets showed that grank significantly outperforms dyngo. the results reveal the robustness of the grank’s method and its ability to reflect the semantic relationships among gene annotations. table  shows the proportion of the meaningful lcas versus the meaningful tcds in the different sets of the benchmarks, where the significant answer genes are annotated to. to further analyze the behavior of the two methods, we classified go graphs into six criteria based on the relative position of a kc in the graph and on the type of relations that connect the kc with other term nodes. we analyzed the behavior of grank and of dyngo in terms of their recall and precision under each of the six criteria. we computed the average recall and precision of the two methods under each of the six criteria. the results are shown in table  as table  shows: grank outperforms dyngo under criteria 2– grank does not perform well under criterion more research work needs to be conducted to overcome the shortcoming of this criterion. grank achieved the same recall values and the same precision values under criteria and which is an indicative that the locations of kcs in go graph are irrelevant to the performance of grank and that its performance does not vary with the height of a go graph. grank performance under criteria 2– is due to: its consideration to the structural dependencies among annotation terms and to its term-depth consideration, and the fact that each of these criteria requires a method to account for the structural dependencies among annotation terms. the extent of the importance of the structural dependencies among annotation terms to a criterion differs from criterion to another: it is more important to criterion than to the other five criteria, which explains the substantial performance of grank over dyngo methods under criterion evaluating the impact of disregarding the ranking of meaningful lca and tcd we modified a copy of grank by removing its capability to rank meaningful lcas and tcds. our objective is to study the impact of overlooking the ranking of meaningful lcas and tcds on the search quality of grank. we aim at: measuring the decline in grank’s recall and precision as a result of disregarding ranking, and comparing the modified copy’s recall and precision with dyngo. if the modified copy outperforms the dyngo method, this performance would be attributed to only grank’s computation of meaningful lcas and tcds. figures and show the overall average recall and precision respectively of the modified copy using the genes of the two benchmarks. as figure  shows, the overall average recall has not changed, which is expected, since ranking does not have an impact on recall; rather, it has an impact on precision. as the figure  shows, the overall average precision of the modified copy is: less than that of the original copy by 26%. higher than that of dyngo. we can conclude that the concept of meaningful lca and tcd has significant impact on grank’s search quality, while ranking has important but not significant impact on grank’s search quality. evaluating an alternative approach to overcoming the shortcoming of criterion 1 as discussed previously that grank does not perform well under query criterion and that more research work needs to be done to overcome this limitation. however, our objective in this test is to evaluate a counter-technique, where a complete go graph is used instead of pog for computing meaningful lcas and tcds. therefore, terms that connect with other terms via only is-a relations will also be considered in the computation of meaningful lcas and tcds. towards this, we modified a copy of grank so that it processes go graph instead of pog for computing meaningful lcas and tcds. figures  and show the average recall and precision of the modified copy using the genes. as figure  shows, the average recall of the modified copy is less than that of the original version by 15%, but is still higher than that of dyngo. however, as figure  shows, the average precision of the modified copy is less than that of the original copy by 33%, and is slightly less than dyngo. we conclude that the concept of pog has a significant impact on grank’s search quality and it compensates for the shortcoming of criterion  in this paper, we proposed a search engine called grank that determines the semantic relationships among genes and gene products. grank overcomes the limitations of current gene similarity measures by using the concept of existence dependency to determine the semantic relationships among gene annotations. it determines the structural dependencies among the go terms annotating a given set s of genes in order to identify the set of other genes that are semantically related to the set s. towards this, the framework of grank refines the concept of lca and tcd by introducing the concept of meaningful lca and meaningful tcd. given a set of genes g g …gn, grank identifies the meaningful lca and the meaningful tcd of the terms annotating g g …gn. the genes annotated to the meaningful lca and the meaningful tcd have the closest semantic relationships with g g …gn. grank ranks the meaningful lcas and the meaningful tcds based on their semantic relationships with kcs. we experimentally evaluated the quality of grank and compared it with dyngo using kegg and pfam benchmarks. in summary, the recall and precision values for the two benchmarking datasets showed that grank outperforms dyngo. the experiments showed that grank does not perform well if all kcs in go graph are connected to other term nodes with only “is-a” relations. we will investigate techniques in a future work that overcome this limitation. endnote athe same thing applies to the score s. competing interests the authors declare that they have no competing interests. authors’ contributions kt conceived, designed, and supervised the research. kt drafted and revised this manuscript. kt, ham, dm, and zam performed the implementation of the research project. kt, ham, dm, and zam carried out the experiments and the analysis of the results. all authors read and approved the final manuscript. 
after determining the set of genes that are semantically related to input genes, grank would use microarray experiment to rank these genes based on their degree of relativity to the input genes. we evaluated grank experimentally and compared it with a comparable gene prediction tool called dyngo, which retrieves the genes and gene products that are relatives of input genes. we propose in this paper a search engine called grank, which overcomes the limitations of the current gene similarity measures outlined above as follows. the experimental results demonstrated that grank overcomes the limitations of current gene similarity measures. it employs the concept of existence dependency to determine the structural dependencies among the go terms annotating a given set of gene. we attribute this performance to grank’s use of existence dependency concept for determining the semantic relationships among gene annotations. the recall and precision values for two benchmarking datasets showed that grank outperforms dyngo tool, which does not employ the concept of existence dependency. most of these gene similarity measures determine the semantic similarities among the genes based solely on the proximity to each other of the go terms annotating the genes, while overlook the structural dependencies among these go terms, which may lead to low recall and precision of results.
 biologists may need to know the set of genes that are semantically related to a given set of genes. for instance, a biologist may need to know the set of genes related to another set of genes known to be involved in a specific disease. some works use the concept of gene clustering in order to identify semantically related genes. others propose tools that return the set of genes that are semantically related to a given set of genes. most of these gene similarity measures determine the semantic similarities among the genes based solely on the proximity to each other of the go terms annotating the genes, while overlook the structural dependencies among these go terms, which may lead to low recall and precision of results.  we propose in this paper a search engine called grank, which overcomes the limitations of the current gene similarity measures outlined above as follows. it employs the concept of existence dependency to determine the structural dependencies among the go terms annotating a given set of gene. after determining the set of genes that are semantically related to input genes, grank would use microarray experiment to rank these genes based on their degree of relativity to the input genes. we evaluated grank experimentally and compared it with a comparable gene prediction tool called dyngo, which retrieves the genes and gene products that are relatives of input genes. results showed marked improvement.  the experimental results demonstrated that grank overcomes the limitations of current gene similarity measures. we attribute this performance to grank’s use of existence dependency concept for determining the semantic relationships among gene annotations. the recall and precision values for two benchmarking datasets showed that grank outperforms dyngo tool, which does not employ the concept of existence dependency. the demo of grank using kegg yeast genes and a gene expression omnibus microarray file named “gsm pad” is available at: http://ecesrvr.kustar.ac.ae:8080/. 