{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:25:07Z","timestamp":1773275107664,"version":"3.50.1"},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,5,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Several measures have been recently proposed for quantifying the functional similarity between gene products according to well-structured controlled vocabularies where biological terms are organized in a tree or in a directed acyclic graph (DAG) structure. However, existing semantic similarity measures ignore two important facts. First, when calculating the similarity between two terms, they disregard the descendants of these terms. While this makes no difference when the ontology is a tree, we shall show that it has important consequences when the ontology is a DAG\u2014this is the case, for example, with the Gene Ontology (GO). Second, existing similarity measures do not model the inherent uncertainty which comes from the fact that our current knowledge of the gene annotation and of the ontology structure is incomplete. Here, we propose a novel approach based on downward random walks that can be used to improve any of the existing similarity measures to exhibit these two properties. The approach is computationally efficient\u2014random walks do not need to be simulated as we provide formulas to calculate their stationary distributions.<\/jats:p>\n               <jats:p>Results: To show that our approach can potentially improve any semantic similarity measure, we test it on six different semantic similarity measures: three commonly used measures by Resnik (1999), Lin (1998), and Jiang and Conrath (1997); and three recently proposed measures: simUI, simGIC by Pesquita et al. (2008); GraSM by Couto et al. (2007); and Couto and Silva (2011). We applied these improved measures to the GO annotations of the yeast Saccharomyces cerevisiae, and tested how they correlate with sequence similarity, mRNA co-expression and protein\u2013protein interaction data. Our results consistently show that the use of downward random walks leads to more reliable similarity measures.<\/jats:p>\n               <jats:p>Availability: We have developed a suite of tools that implement existing semantic similarity measures and our improved measures based on random walks. The tools are implemented in Matlab and are freely available from: http:\/\/www.paccanarolab.org\/papers\/GOsim\/<\/jats:p>\n               <jats:p>Contact: \u00a0alberto@cs.rhul.ac.uk<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts129","type":"journal-article","created":{"date-parts":[[2012,4,21]],"date-time":"2012-04-21T01:24:27Z","timestamp":1334971467000},"page":"1383-1389","source":"Crossref","is-referenced-by-count":72,"title":["Improving GO semantic similarity measures by exploring the ontology beneath the terms and modelling uncertainty"],"prefix":"10.1093","volume":"28","author":[{"given":"Haixuan","family":"Yang","sequence":"first","affiliation":[{"name":"Department of Computer Science and Centre for Systems and Synthetic Biology, Royal Holloway, University of London, Egham, TW20 0EX, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tam\u00e1s","family":"Nepusz","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Centre for Systems and Synthetic Biology, Royal Holloway, University of London, Egham, TW20 0EX, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alberto","family":"Paccanaro","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Centre for Systems and Synthetic Biology, Royal Holloway, University of London, Egham, TW20 0EX, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2012,4,19]]},"reference":[{"key":"2023012512303008400_B1","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1038\/75556","article-title":"Gene ontology: tool for the unification of biology","volume":"25","author":"Ashburner","year":"2000","journal-title":"Nat. Genet."},{"key":"2023012512303008400_B2","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1074\/mcp.M600381-MCP200","article-title":"Toward a comprehensive atlas of the physical interactome of Saccharomyces cerevisiae","volume":"6","author":"Collins","year":"2007","journal-title":"Mol. Cell Proteomics"},{"key":"2023012512303008400_B3","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1186\/2041-1480-2-5","article-title":"Disjunctive shared information between ontology concepts: application to gene ontology","volume":"2","author":"Couto","year":"2011","journal-title":"J. Biomed. Semantics"},{"key":"2023012512303008400_B4","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.datak.2006.05.003","article-title":"Measuring semantic similarity between gene ontology terms","volume":"61","author":"Couto","year":"2007","journal-title":"Data Knowl. Eng."},{"key":"2023012512303008400_B5","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1145\/1099554.1099658","article-title":"Semantic similarity over the Gene Ontology: family correlation and selecting disjunctive ancestors","volume-title":"Proceedings of the 14th ACM International Conference on Information and Knowledge Management.","author":"Couto","year":"2005"},{"key":"2023012512303008400_B6","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1093\/bioinformatics\/btl042","article-title":"Assessing semantic similarity measures for the characterization of human regulatory pathways","volume":"22","author":"Guo","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012512303008400_B7","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1186\/1471-2105-11-562","article-title":"An improved method for scoring protein\u2013protein interactions using semantic similarity within the gene ontology","volume":"11","author":"Jain","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023012512303008400_B8","first-page":"9008","article-title":"Semantic similarity based on corpus statistics and lexical taxonomy","volume-title":"International Conference Research on Computational Linguistics (ROCLING X)","author":"Jiang","year":"1997"},{"key":"2023012512303008400_B9","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1038\/nature04670","article-title":"Global landscape of protein complexes in the yeast Saccharomyces cerevisiae","volume":"440","author":"Krogan","year":"2006","journal-title":"Nature"},{"key":"2023012512303008400_B10","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1109\/TKDE.2003.1209005","article-title":"An approach for measuring semantic similarity between words using multiple information sources","volume":"15","author":"Li","year":"2003","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"2023012512303008400_B11","first-page":"296","article-title":"An information-theoretic definition of similarity","volume-title":"Proceedings of the 15th International Conference on Machine Learning.","author":"Lin","year":"1998"},{"key":"2023012512303008400_B12","doi-asserted-by":"crossref","first-page":"1275","DOI":"10.1093\/bioinformatics\/btg153","article-title":"Investigating semantic similarity measures across the Gene Ontology: the relationship between sequence and annotation","volume":"19","author":"Lord","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012512303008400_B13","doi-asserted-by":"crossref","first-page":"D169","DOI":"10.1093\/nar\/gkj148","article-title":"MIPS: analysis and annotation of proteins from whole genomes in 2005","volume":"34","author":"Mewes","year":"2006","journal-title":"Nucl. Acids Res."},{"key":"2023012512303008400_B14","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.jbi.2007.05.010","article-title":"A genetic similarity algorithm for searching the Gene Ontology terms and annotating anonymous protein sequences","volume":"41","author":"Othman","year":"2008","journal-title":"J. Biomed. Inform."},{"issue":"Suppl. 5","key":"2023012512303008400_B15","doi-asserted-by":"crossref","first-page":"S4","DOI":"10.1186\/1471-2105-9-S5-S4","article-title":"Metrics for GO based protein semantic similarity: a systematic evaluation","volume":"9","author":"Pesquita","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023012512303008400_B16","doi-asserted-by":"crossref","first-page":"e1000443+","DOI":"10.1371\/journal.pcbi.1000443","article-title":"Semantic similarity in biomedical ontologies","volume":"5","author":"Pesquita","year":"2009","journal-title":"PLoS Comput. Biol."},{"key":"2023012512303008400_B17","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1109\/21.24528","article-title":"Development and application of a metric on semantic nets","volume":"19","author":"Rada","year":"1989","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"2023012512303008400_B18","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1613\/jair.514","article-title":"Semantic similarity in a taxonomy: an information-based measure and its application to problems of ambiguity in natural language","volume":"11","author":"Resnik","year":"1999","journal-title":"J. Artif. Intell. Res."},{"key":"2023012512303008400_B19","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1093\/nar\/24.1.40","article-title":"Genes and proteins of Escherichia coli (GenProtEc)","volume":"24","author":"Riley","year":"1996","journal-title":"Nucl. Acids Res."},{"key":"2023012512303008400_B20","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1186\/1471-2105-7-302","article-title":"A new measure for functional similarity of gene products based on Gene Ontology","volume":"7","author":"Schlicker","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023012512303008400_B21","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1109\/TCBB.2005.50","article-title":"Correlation between gene expression and GO semantic similarity","volume":"2","author":"Sevilla","year":"2005","journal-title":"IEEE ACM Trans. Comput. Biol. Bioinformatics"},{"key":"2023012512303008400_B22","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","article-title":"Identification of common molecular subsequences","volume":"147","author":"Smith","year":"1981","journal-title":"J. Mol. Biol."},{"key":"2023012512303008400_B23","doi-asserted-by":"crossref","first-page":"3273","DOI":"10.1091\/mbc.9.12.3273","article-title":"Comprehensive identification of cell cycle-regulated genes of the yeast Saccharomyces cerevisiae by microarray hybridization","volume":"9","author":"Spellman","year":"1998","journal-title":"Mol. Biol. Cell"},{"key":"2023012512303008400_B24","first-page":"25","article-title":"Gene expression correlation and gene ontology-based similarity: an assessment of quantitative relationships","volume-title":"Proceedings of the 2004 IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology","author":"Wang","year":"2004"},{"key":"2023012512303008400_B25","doi-asserted-by":"crossref","first-page":"2163","DOI":"10.1093\/bioinformatics\/btm291","article-title":"Total ancestry measure: quantifying the similarity in tree-like classification, with genomic applications","volume":"23","author":"Yu","year":"2007","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/10\/1383\/48865170\/bioinformatics_28_10_1383.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/10\/1383\/48865170\/bioinformatics_28_10_1383.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T15:56:13Z","timestamp":1674662173000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/28\/10\/1383\/211540"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4,19]]},"references-count":25,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2012,5,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts129","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2012,5,15]]},"published":{"date-parts":[[2012,4,19]]}}}