Enumerating consistent sub-graphs of directed acyclic graphs: an insight into biomedical ontologies

Area of Science:

• Computational Biology
• Bioinformatics
• Graph Theory

Background:

• Concept annotation links objects to textual descriptors, often organized in ontologies represented as directed acyclic graphs (DAGs).
• Consistent annotation requires objects to be associated with all generalizing concepts within an ontology.
• Enumerating these annotation spaces has been computationally challenging.

Purpose of the Study:

• To propose and validate a practical algorithm for enumerating consistent sub-graphs of DAGs.
• To provide insights into the complexity of concept annotation spaces.
• To assess the influence of annotation spaces on ontological annotation predictability.

Main Methods:

• A recursive partitioning algorithm that simplifies DAGs into rooted trees for efficient computation.
• Combining results from recursively solved subproblems to derive the final count.
• Validation on random graphs and application to major biomedical ontologies.

Main Results:

• A correct and efficient algorithm for enumerating consistent sub-graphs of DAGs.
• Demonstrated practical accelerations for the algorithm.
• Characterization of annotation spaces in four major biomedical ontologies.

Conclusions:

• The developed algorithm offers a valuable tool for analyzing concept annotation spaces.
• Provides insights into the computational complexity of ontological annotations.
• Potential impact on improving the predictability of ontological annotation.