An efficient, large-scale, non-lattice-detection algorithm for exhaustive structural auditing of biomedical...

Area of Science:

• Bioinformatics
• Computational Biology
• Ontology Engineering

Background:

• Structural analysis of biomedical ontologies is crucial for quality assurance.
• Exhaustive sub-graph analysis presents significant computational challenges.
• Existing methods for computing lowest common ancestors (LCA) are computationally expensive.

Purpose of the Study:

• To introduce ANT-LCA, an efficient algorithm for computing non-trivial lowest common ancestors (LCA) in biomedical ontologies.
• To address the computational cost barrier in structural ontology analysis.
• To enable advanced ontology quality assurance methods.

Main Methods:

• Developed the ANT-LCA algorithm for computing non-trivial LCAs.
• Combined topological ordering and dynamic programming to optimize LCA computation.
• Focused on pairs with at least one common ancestor to reduce computational load.

Main Results:

• ANT-LCA significantly reduces computational time for large ontologies like SNOMED CT and Gene Ontology (GO).
• Achieved average computation times of 30 sec (SNOMED CT) and 3 sec (GO) per version.
• Demonstrated a speed improvement of approximately two orders of magnitude compared to existing methods.

Conclusions:

• ANT-LCA overcomes a fundamental computational barrier in structural analysis of large ontologies.
• Enables new structural auditing methods for identifying and fixing issues in ontologies.
• Facilitates the development of more effective ontology quality assurance tools.