The representation of biomedical structure - from cellular components to organisms - in biomedical ontologies is of pivotal importance, as the internal structure of complex structured objects needs to be referenced in the de nition of processes, disorders, phenotypes and many other entities. Yet, most of the existing biomedical ontologies do not contain logical axiomatizations for accurately representing the internal structure. We have identi ed the high importance of mereotopology (parthood, connectedness) for accurate representation in this domain, but the representation of mereotopological structure can provide challenges for reasoners. To evaluate the scalability of accurate representation of biomedical structure, we have identi ed design patterns for (i) parthood, both one-sided, two-sided and cardinality restricted, (ii) class disjointness, and (iii) spatial disconnectedness. In order to evaluate the DL reasoning performance for these patterns, we have created a T-Box Generator to programmatically generate small and large experimental T-Boxes with different reasoning complexities resulting from the relative proportions of the patterns (i) to (iii). Classi cation times have been measured for di erent reasoners in their most common application settings. We found that, as expected, reasoning times increased dramatically with the size and complexity of the generated ontology, and furthermore, even small numbers of cardinality restrictions were a major performance killer.
It has been repeatedly emphasized that the representation of biomedical structure - encompassing a broad range from the material constitution of cells and cell organelles to anatomies of animals and plants, even hospital buildings and their departments, is of fundamental importance in biomedical ontology. There is hardly any biomedical ontology or terminology which does not refer to structural material entities, as they are the location of physiological, pathological, ? To whom correspondence should be addressed: martin.boeker@uniklinik-freiburg.de and clinical processes, therapeutic or experimental interventions, as well as the bearers of functions, dispositions, and qualities.
Most OWL-based ontologies currently represent structural entities in a
double hierarchy, viz. a taxonomic order paralleled by a partonomy. We nd
examples for this in the Foundational Model of Anatomy (FMA) [
There are basically two kinds of assertions found in these parallel hierarchies: { Taxonomic parents: A subclassOf B, e.g. Heart subclassOf Cavitated
Organ { Part implies whole: All members of the class P are parts of some W . P subclassOf properPartOf some W , e.g. Heart properPartOf some CardiovascularSystem
Such simple representations are not su cient for properly expressing axioms such as the following: { Mutual disjointness: There are no entities which are both members of class A and members of class B; e.g. there are no entities which are both nerve cells and blood cells. { Spatial disjointness: No member of class A spatially overlaps with any member of class B, or stricter; no member of A has a part which is also part of any B. Examples: Nothing is totally located in any liver and any kidney ; nothing which is part of some right arm can be part of some left arm. { Whole implies part: All members of the class W have some member of P as part, e.g. all cell membranes have some lipids as part. Note that P being a mandatory part of W does not mean that W is a mandatory whole for P . { Counts of parts: Class W has exactly n distinct members of class P as parts, e.g. all hands have exactly ve ngers as parts.
The contributions of this paper are two-fold. Firstly, we de ne patterns for the representation of these aspects of biomedical structure in OWL. Secondly, we provide an ontology performance evaluation tool, in the form of a TBox generator for di erent sizes and complexities of ontologies accommodating these patterns. We use this tool to investigate the scalability of reasoning over these patterns through generating ontologies of di erent sizes and complexities. The advantage of this approach is that ontology developers can pre-test an ontology in the design phase, before implementation, based on the expected complexity and size. 2
Patterns for the representation of biomedical structure The following real world examples from the GO, Mouse Anatomy and FMA illustrate ontology content patterns for partonomy representation: { The textual de nition of Gastrointestinal tract in the FMA is as follows: Hollinshead's 97:528 - From the foregut will di erentiate the esophagus, the stomach, and the proximal half of the duodenum. Two buds appear on the caudal portion: a ventral diverticulum gives rise to the liver, gallbladder, and a portion of the pancreas; a dorsal diverticulum grows into the dorsal mesentery and gives rise to the remaining and major part of the pancreas. From the midgut are derived the second half of the duodenum, the jejunum, ileum, cecum and appendix; ascending colon, and most of the transverse colon. From the hindgut are derived the terminal portion of the transverse colon, the descending and sigmoid colon, and the rectum.
This textual de nition shows some good examples of spatial connection, partonomy with cardinality, and spatial disjointness, which are not captured in the formalization of the FMA in OWL. { The Adult Mouse Gross Anatomy ontology has many examples of partonomies, e.g., nervous system has part central nervous system (CNS) and other parts, while the CNS in turn has part white matter, grey matter and other parts. It includes no explicit disjoints or spatial disjoints in its representation. { The GO Cellular Component ontology has divisions at a high level between classes (X) and classes for parts (Xpart), examples of which are cell/cell part ; extracellular region/ extracellular region part ; virion/ virion part. In other words, the ontology exactly follows the taxonomy/ partonomy distinction but without explicit disjoints asserted. As is the case with the FMA, the textual de nitions give much more information than is encoded in the formal axioms. For example, sperm individualization complex is de ned as follows:
A macromolecular complex that cytoskeletal components and part of the cell membrane, forms at the nuclear end of a male germline syncytium, or cyst, and translocates the over the length of the syncytium in the course of sperm individualization. Each complex contains an array of 64 investment cones, one per nucleus, that move synchronously along the spermatogenic cyst.
We express mutual disjointness by the OWL2 DisjointClasses predicate, which corresponds to the set of axioms:
DisjointClasses (C1; C2; : : : ; Cn) =def fC1 subclassOf not C2; : : : ; C1 subclassOf not Cn; C2 subclassOf not Cn; : : :g (1)
Spatial disjointness requires a more complex axiomatization, and there is no OWL predicate for this: It requires the expression of the condition that nothing located in any instance of Class1 (e.g. UpperLobe) is located in any instance of Class2 (e.g. LowerLobe) and vice versa:
(2) with locusOf being the inverse of the transitive and re exive relation hasLocus, as the most general spatial inclusion relation. Additionally,
(4) In our framework the transitive and irre exive mereological relations properPartOf and hasProperPart are subrelations of hasLocus and locusOf, respectively.
Whole implies part (see example above) shows that partonomies are more complex compared to taxonomies. It is not su cient to say that C1 and C2 are in a partonomic order, as the following cases need to be distinguished: { Class1 subClassOf properPartOf some Class2 (\part implies whole") { Class2 subClassOf hasProperPart some Class1 (\whole implies part") and the combination of both of the above (two-sided parthood). 3
The T-Box Generator: automatically creating ontologies of di erent sizes and complexities We developed a T-Box Generator to generate ontologies resembling real world ontologies di ering in a variety of parameters. The generator was programmed in the object functional language Scala4. The script can be downloaded from http://www.imbi.uni-freiburg.de/ontology/t-box-generator.zip. The generation of di erent versions of ontologies can be controlled by command line parameters which enable the batch generation of groups of ontologies.
The T-Box Generator allows the following parameters to be controlled: { The number of levels in the is a hierarchy. { The number of subclasses of each superclass. E.g., with three levels of is a hierarchy and 10 subclasses a total of 103 = 1000 classes will be generated. { The number of mutually disjoint classes in each group of subclasses. The mutually disjoint classes are also the target of the hasPart relation of the partonomy when generated and are the source of partOf relations. { The number of mutually spatially disjoint classes characterized by the spatially disjoint pattern. { The creation of a partonomy in the ontology. If the partonomy is created the rst class in each subclass group is the source of hasPart relations to all mutually disjoint classes in the same group of subclasses as de ned above and is the target for partOf relations from these classes. The relations of the partonomy can further be controlled. { The partonomy can either be created as subclasses axiom or equivalent classes axioms for the hasPart relation outgoing from the rst class in each group of subclasses. 4 http://www.scala-lang.org/ { The quanti cation for the hasPart relation outgoing from the rst class in each group of subclasses can be either set to existential or to an exact cardinality. When it is set to an exact cardinality the transitivity switch (below) is overriden so that the partonomic relations have no transitivity property. { The pairs of relations hasLocus { locusOf and hasPart { partOf can be set as inverse relations. { The transitivity property for the relations hasPart, partOf, hasLocus and locusOf can be set on or o . { The lename under which an ontology is saved can be set.
This set of parameters allows the generation of a variety of ontologies with typical features of biomedical ontologies to test for performance issues with the given set of ontology tools comprised by the ontology editor Protege and the DL reasoners Pellet, HermiT and Fact++. The advantage of this approach is that ontology developers are able to pre-test an anticipated ontology for performance issues before they actually run into them.
A generated ontology with ve levels of is a hierarchy and six subclasses for each superclass is illustrated in Figure 1. 4
We tested three of the most common reasoners that integrate with Protege
and are under an open source license i.e., Fact++ (version 1.5.2) [
We measured reasoning speed with the default settings for the Protege 4 reasoner con guration tab, as we assume that many ontology developers in the biomedical domain will use these defaults. These are: all switches for class inferences, all switches for object property inferences, no switches for datatype property inferences and no switches for individual inferences set to active. The measurement was performed on a computer with a 1.6GHz Intel(R) Core(TM) i7 CPU Q720 with 4GB RAM under Windows 7 64-Bit and Java 64-Bit (Version 1.6.25). The Protege installation was version 4.1 RC2 build 228.
Protege was started with the Java command line switch -Xmx3000m resulting in an e ective memory allocation of 2796MB. For each reasoner and each ontology three consecutive measurements were performed. After each series of measurements Protege was closed and Java unloaded from memory to avoid any unwanted e ects of Java's automatic memory management on the reasoning performance. The results are illustrated in Table 1. For a graphical representation of the results see Fig. 2. 5 http://code.google.com/p/cb-reasoner/ 6 http://lat.inf.tu-dresden.de/systems/cel/ 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
complexity 6^5 classes Graphs by reasoner 20^3 classes 90^2 classes Many of the current biomedical ontologies modeling aspects of biological structure provide underconstrained logical axioms for the parthood and connectedness of the structured objects they contain. This is re ected by a disconnection between the information content of the textual de nitions, which can be quite detailed, and the logical axioms, which tend to re ect a simplistic partonomy and taxonomy, without further axiomatization. Our rst contribution is the identi cation of patterns for representing the missing structural complexity in bio-ontologies.
The patterns we have identi ed fall short of what is needed to fully
represent the domain of mereotopology, since they do not allow the representation
of complex structural interrelationships between parts of a whole, in particular
where such interrelationships can form cycles. An anatomical example of such a
structured object is the human heart, which can be simplistically described in
terms of a left and right atrium and a left and right ventricle, each of which is
connected to each other. For reasons described in [
Certain recent OWL extensions allow the representation of arbitrarily
structured objects, such as rules [
Furthermore, we have hypothesized that large-scale migration to more axiomatic representation of biomedical structure might be accompanied by a prohibitively large performance decrease on the side of the DL-based reasoners commonly used in ontology development. Should this be the case, it stands as an obstacle for the migration of existing large-scale ontologies towards greater semantic complexity. To evaluate the performance consequences on reasoners for the di erent complexity patterns we implemented a T-Box generator that automatically creates test ontologies according to the patterns.
Although the idea of ontology generators in general is not new (see, for
example, [
The reasoning time acceptable for a particular ontology engineering e ort is dependent on the time available during the ontology life cycle and the phase in which reasoning is applied. Examples of reasoning tasks might be to apply a consistency check before ontology release, or after any change at development time, or even a consistency check used as part of the ontology public user interface in which reasoning forms part of an application use case.
At development time, the time allowed for reasoning is dependent on the frequency at which reasoning is to be carried out, which is a function of the number of people performing changes on the ontology over time and on their expertise level. Having only one knowledgeable developer might require fewer reasoning checks as when three novices are actively changing the ontology. The acceptance of reasoning time is proportional to the ratio of the development session time to reasoning time, e.g. for a one hour editing session 30 minutes reasoning time is certainly not acceptable, whereas for an 8 hour session it might seem reasonable.
As regards our performance results, we found an expected decrease in reasoner performance with increase in ontology complexity, and in particular a dramatic decrease in performance with the use of cardinality constraints. In order to still be able to make the best out of the available resources, we suggest structural simpli cations of the desired semantic complexity i.e. the transformation from a complex representation to a less complex and more performant representation. 7 http://knowledgeweb.semanticweb.org/benchmarking interoperability/
OWLDLGenerator/
For the modeling in the biomedical domain mereotopology (i.e. parthood and connectedness) is of high importance for accurate representation. Together with the considerable size of ontologies in the biomedical domain this can provide challenges for reasoners.
To evaluate and predict the reasoning performance of di erent reasoners we developed a T-Box generator which allows for the parameterized creation of ontologies. As expected, reasoning time increases with growing complexity and size of the ontology. Further research will include other reasoners and a larger set of ontology patterns.
Acknowledgments This work was partly supported by the Deutsche Forschungsgemeinschaft (DFG) grant JA 1904/2-1, SCHU 2515/1-1 GoodOD (Good Ontology Design).