SGFSC: speeding the gene functional similarity calculation based on hash tables

Chunyu Wang, Zhen Tian, Chunyu Wang 0002, Maozu Guo, Xiaoyan Liu, Zhixia TengBMC Bioinformatics 2016 · DOI

Abstract

Measuring gene functional similarity is a cornerstone of genomics, yet traditional graph-traversal methods are computationally expensive. We present SGFSC (Speeding Gene Functional Similarity Calculation), a tool that utilizes a two-step hash table strategy to eliminate redundant calculations. By decoupling static semantic data from the similarity logic, SGFSC reduces processing times from days to hours for whole-genome analyses while maintaining a minimal memory footprint of approximately 5 MB.

The Computational Bottleneck in Functional Genomics

In functional genomics, measuring the similarity between two genes based on their biological roles is essential for predicting protein interactions and prioritizing disease-associated genes. These roles are defined using Gene Ontology (GO), where terms are organized in a complex hierarchy known as a Directed Acyclic Graph (DAG).

The primary challenge is computational efficiency. Traditional algorithms must traverse these complex graphs repeatedly to find the "Lowest Common Ancestor" (LCA) or calculate "Information Content" (IC) for every pair of genes. As the GO database grows and researchers attempt to analyze entire genomes involving millions or billions of gene pairs, this graph-traversal approach becomes a massive bottleneck, often taking days to complete on standard hardware.

Methods: The Two-Step Hashing Strategy

SGFSC addresses this bottleneck by introducing a novel two-step computing strategy that replaces expensive graph traversals with near-instantaneous table lookups.

The two-step strategy of SGFSC: preprocessing to establish hash tables followed by similarity measurement.
  1. Establish Hash Tables (Preprocessing): Instead of traversing the graph during the calculation, the system first analyzes the specific mathematical requirements of a similarity measure (e.g., the Resnik or Wang methods). It extracts "essential information"—such as the IC values of all ancestors or specific semantic contribution values—and stores them in a hash table.
  2. Measure Similarity (Calculation): When comparing genes, the algorithm simply queries the hash table. This replaces graph-based searches with O(1) or O(k) complexity lookups.
An example of a GO graph (a) and its corresponding hash table structure (b), illustrating how semantic values are pre-stored.

The researchers implemented this strategy into the SGFSC tool, which supports seven widely used similarity measures (Resnik, Lin, Jiang, Pekar, Wang, simUI, and simGIC). They also developed a specific algorithm, EHT, to efficiently generate these hash tables from raw GO data.

Performance and Key Results

The study evaluated SGFSC using the August 2015 GO release (over 41,000 terms) and annotation data for five model organisms: Human, Arabidopsis, Yeast, Rat, and Rice. The performance gains were dramatic compared to existing tools like GFSAT and GOSemSim:

  • Term Pair Speedup: For $10^6$ term pairs, SGFSC finished in ~9.4 seconds, whereas competitive tools took over 12 hours.
  • Gene Pair Speedup: For $10^4$ gene pairs, SGFSC took 29 seconds, while GFSAT required approximately 10 hours.
  • Whole Genome Scale: SGFSC computed functional similarity for the entire human genome (roughly $7.74 \times 10^8$ gene pairs) in approximately 10-11 hours. Without this hash table strategy, such a calculation is practically unfeasible for most researchers.
  • Low Resource Footprint: Despite the speed, the memory required to store the hash tables is only about 5 MB, making the tool highly efficient for standard laptops.

Discussion and Limitations

The "aha moment" of SGFSC is the realization that the essential information needed for similarity equations is static for any given version of the GO graph. By pre-calculating this data once, researchers trade a negligible amount of memory for orders-of-magnitude gains in speed.

However, there are minor trade-offs. SGFSC has an initial loading overhead of a few seconds to read the hash table into memory, meaning it may not be faster for very small batches (e.g., comparing just two genes). Additionally, the hash tables must be re-generated whenever the Gene Ontology database is updated. While the EHT algorithm makes this fast (taking only a few minutes), it remains a necessary maintenance step. Future work may see this hashing strategy applied to other hierarchical taxonomies, such as WordNet in Natural Language Processing.

Summary updated

BibTeX
@article{wang2016sgfsc,
  author = {Chunyu Wang and Zhen Tian and Chunyu Wang and Maozu Guo and Xiaoyan Liu and Zhixia Teng},
  title = {{SGFSC: speeding the gene functional similarity calculation based on hash tables}},
  journal = {BMC Bioinformatics},
  year = {2016},
  doi = {10.1186/s12859-016-1294-0},
}
Figure