title: GS2: an efficiently computable measure of GO-based similarity of gene sets.
abstract: BACKGROUND
  The growing availability of genome-scale datasets has attracted increasing attention to the development of computational methods for automated inference of functional similarities among genes and their products. One class of such methods measures the functional similarity of genes based on their distance in the Gene Ontology (GO). To measure the functional relatedness of a gene set, these measures consider every pair of genes in the set, and the average of all pairwise distances is calculated. However, as more data becomes available and gene sets used for analysis become larger, such pair-based calculation becomes prohibitive.
  
  
  RESULTS
  In this article, we propose GS(2) (GO-based similarity of gene sets), a novel GO-based measure of gene set similarity that is computable in linear time in the size of the gene set. The measure quantifies the similarity of the GO annotations among a set of genes by averaging the contribution of each gene's GO terms and their ancestor terms with respect to the GO vocabulary graph. To study the performance of our method, we compared our measure with an established pair-based measure when run on gene sets with varying degrees of functional similarities. In addition to a significant speed improvement, our method produced comparable similarity scores to the established method. Our method is available as a web-based tool and an open-source Python library.
  
  
  BACKGROUND
  The web-based tools and Python code are available at: http://bioserver.cs.rice.edu/gs2.
authors.affiliation: Department of Computer Science, Rice University, 6100 Main Street, MS 132, Houston, TX, USA. troy.ruths@rice.edu
authors.forename: Troy
authors.initials: T
authors.lastname: Ruths
authors.forename: Derek
authors.initials: D
authors.lastname: Ruths
authors.forename: Luay
authors.initials: L
authors.lastname: Nakhleh
mesh_terms: D000465:Algorithms; D030541:Databases, Genetic; D020869:Gene Expression Profiling / Q000379:methods; D005796:Genes; D023281:Genomics; D020407:Internet; D012984:Software; D018875:Vocabulary, Controlled