  Modern problems of concept annotation associate an object of interest (gene,
individual, text document) with a set of interrelated textual descriptors
(functions, diseases, topics), often organized in concept hierarchies or
ontologies. Most ontologies can be seen as directed acyclic graphs, where nodes
represent concepts and edges represent relational ties between these concepts.
Given an ontology graph, each object can only be annotated by a consistent
subgraph; that is, a subgraph such that if an object is annotated by a
particular concept, it must also be annotated by all other concepts that
generalize it. Ontologies therefore provide a compact representation of a large
space of possible consistent subgraphs; however, until now we have not been
aware of a practical algorithm that can enumerate such annotation spaces for a
given ontology. In this work we propose an algorithm for enumerating consistent
subgraphs of directed acyclic graphs. The algorithm recursively partitions the
graph into strictly smaller graphs until the resulting graph becomes a rooted
tree (forest), for which a linear-time solution is computed. It then combines
the tallies from graphs created in the recursion to obtain the final count. We
prove the correctness of this algorithm and then apply it to characterize four
major biomedical ontologies. We believe this work provides valuable insights
into concept annotation spaces and predictability of ontological annotation.
