Exact score distribution computation for ontological similarity searches

Area of Science:

• Bioinformatics
• Computational Biology
• Ontology Research

Background:

• Semantic similarity searches in ontologies are crucial for bioinformatic algorithms, aiding in tasks like identifying functionally related proteins (Gene Ontology) and phenotypically similar diseases (Human Phenotype Ontology - HPO).
• Previous work demonstrated improved search performance by ranking results based on the probability of obtaining a score randomly, rather than the scores themselves.
• A key limitation has been the absence of algorithms for computing exact semantic similarity score distributions, which are necessary for precise P-value determination.

Purpose of the Study:

• To address the need for exact P-value calculation in ontology similarity searches.
• To introduce a novel algorithm for the efficient computation of score distributions.
• To enhance the statistical significance assessment of similarity scores in biological ontologies.

Main Methods:

• The study focuses on similarity measures derived from Resnik's definition of ontological similarity.
• A new algorithm is proposed that accelerates score distribution computation by collapsing subgraphs within the ontology graph.
• The algorithm's efficiency is demonstrated through score distribution computations for similarity searches in the Human Phenotype Ontology (HPO).

Main Results:

• The developed algorithm achieves a speed improvement of several orders of magnitude compared to naive approaches for computing score distributions.
• Exact P-value calculation using the new method demonstrably improves clinical diagnosis accuracy when utilizing the Human Phenotype Ontology (HPO).
• The results show that exact P-value computation offers advantages over sampling-based methods for assessing similarity scores.

Conclusions:

• The novel algorithm facilitates the first-ever exact P-value calculation for ontology similarity searches through precise score distribution computation.
• This approach is broadly applicable to any ontology adhering to the annotation-propagation rule and can enhance existing bioinformatic tools.
• The algorithm, implemented in Java, supports ontologies in OBO format and is available for academic and non-commercial use.