Reasoning the FMA Ontologies with TrOWL

Abstract

In this paper, we brie y introduce the TrOWL ontology reasoning infrastructure and share our experience of using TrOWL to reason with various versions of the Foundational Model of Anatomy Ontology (FMA), which are among the most challenging ontologies for Description Logic reasoners. { OWL2-DL, the most expressive decidable language in the OWL2 family, and { three tractable sub-languages of OWL2-DL, i.e. OWL2-EL, OWL2-QL and OWL2-RL.

TrOWL

TrOWL1 is a tractable reasoning infrastructure for the second version of the Web Ontology Language, or simply OWL22, which comes with a family of ontology languages, including:

There are at least three approaches to reasoning in OWL2:

TrOWL supports OWL2 by using the approaches 2 and 3 mentioned above. On the tractable language level, TrOWL contains an OWL2-EL reasoner (REL) and an OWL2-QL reasoner (Quill). The approach of TrOWL is to o er tractable support for all the expressive power of OWL2 by using quality guaranteed (in terms of soundness and/or completeness) approximate reasoning. TrOWL contains an OWL2 pro le checker to detect which pro le an ontology may t into.

The semantic approximation from OWL2 to OWL-QL is based on the work described in Pan and Thomas [ 11 ]. Semantic approximation applies the knowledge compilation [ 18 ] to precompute the entailment of an arbitrary ontology into a DL-Lite ontology. In general, this approach is soundness preserving and could be incomplete. Furthermore, a conditional completeness condition is identi ed: if input queries are database style queries, i.e. the variables only bound to named individuals, the approach is also complete. In other words, database style queries are not expressive enough to tell the di erence between the original OWL2-DL ontology and its approximation. A drawback for this approach is that reasoners are required to compute the semantic approximation; therefore, the construction of the approximation is usually done o -line.

The syntactic approximation from OWL2 to OWL2-EL is based on the soundness preserving approximate reasoning approach presented in Ren et al. [ 14 ]. The construction of the approximation is on the syntax and hence can be done e ciently just before applying approximate reasoning. The idea is not to throw away the axioms that are beyond OWL2-EL; otherwise, we might su er from low recall | for example, if we naively remove from the Cyc ontology all the axioms that are beyond OWL2-EL, the recall is only 1% for classi cation. Therefore, in this approach, we introduce some fresh named classes to represent non-OWL2-EL class expressions. In order to recover the hidden semantics within these fresh named classes, some relation between such named classes and existing classes are maintained and some extra completion rules (beyond those in OWL2-EL) are introduced, with the extended set of completion rules still being tractable. In [ 14 ], we reported that the recall of such approximate reasoning is very high for TBox classi cation, 100% for most existing benchmark ontologies except the Wine Ontology (99.4%). A further investigation indicates that it is due to the syntax sensitivity nature of our approach. After adding a further normalisation step into TrOWL, the recall for the Wine Ontology is also 100%.

TrOWL supports both OWL and Jena APIs. It has a plug-in for the Protege ontology editor v4.3. 2

FMA Ontologies

The Foundational Model of Anatomy Ontology (FMA) [ 16 ] is an evolving computer-based knowledge source for biomedical informatics, mainly developed by the University of Washington since 1994. The importance of this ontology resides in the fundamental underlining of anatomy in all elds of medicine. Proper interpretation of these data relies on an implicit understanding of anatomy. The inferences entailed in such reasoning call upon cognitive or computational processing of abstractions about physical entities of the body, making use of relationships that exist among anatomical concepts. Relevance and impact of the File Source File size Cls Props Inds Expressivity FMA-DLR4 bioontology.org 147.6 Mb 78989 110 139374 ALU IN (D) FMA-FullR4 bioontology.org 37.7 Mb 23597 77 82935 ALCOF (D) FMA-Constitutional [ 5 ] 42.1 Mb 41647 148 85 ALCOIF (D) FMA-OWL2G noMTC [ 4 ] 261.7 Mb 85005 140 74698 SROIQ(D) FMA-DLR M15 this paper 140Kb 26 133 26 ALCOIF (D) FMA-DLR M26 this paper 225Kb 56 133 56 ALCOIF (D) FMA ontology on its eld can now be compared to other well-known medical ontologies such as SNOMED [ 12 ] or GALEN [ 6 ].

Nowadays, the FMA can be viewed as a complex, highly connected network in which nearly 70,000 anatomical concepts, from over 170,000 frames, are interrelated by over 570,000 relationship instances. There have been a number of approaches [ 5, 10, 4 ] to translating the knowledge encapsulated by the FMA ontology into the OWL ontology language. Golbreich et al. [ 4 ] developed the FMA-OWLizer tool, which can be applied to automatically obtain a translation of the FMA ontology into OWL 2.

Given the size and complexity of the FMA ontology, reasoning under OWL has proven to be a real challenge. Table 1 provides a list of FMA ontologies written in OWL that we used in our evaluation. 3

FMA with Metamodeling

The FMA features a complex structure of superclasses and subclasses that requires the support of metamodeling. For example, \Physical anatomical entity" is an instance of \Anatomical entity template", and a subclass of both \Anatomical entity template" and \Anatomical entity" [ 1 ]. In OWL, a class is interpreted as a set of objects. Similarly, a metaclass is interpreted as a set of sets in metamodeling extensions of OWL, such as OWL-FA [ 7 ]. For example, the metaclass Vertebra can be interpreted as a set of di erent types of vertebrae, such as cervical, thoracic, lumbar, which in turn can be interpreted as subsets of other sets, e.g., rst, ..., fth lumbar vertebra.

There have been several attempts in dealing with metamodeling in FMA. Dameron et al. [ 1 ] converted the frame-based FMA ontology into an OWL1DL version and an OWL1-Full version, with metaclasses included in the latter one. Golbreich et al. [ 5 ] tried to capture (some of) the knowledge encoded at metaclasses di erently in OWL1-DL directly (cf. the FMA-Constitutional ontology in Table 1). The idea is to replace instance-of links between a class and its metaclasses with subClassOf links. The structure of their instances, property 4 http://www.bioontology.org/wiki/index.php/FMAInOwl 5 http://homepages.abdn.ac.uk/je .z.pan/pages/onto/fma-dlr-m1.owl 6 http://homepages.abdn.ac.uk/je .z.pan/pages/onto/fma-dlr-m2.owl restrictions of metaclasses are interpreted as closure axioms and approximated by universal restrictions while restrictions of classes are translated into existential restriction. Later on, Golbreich et al. further encoded the FMA ontology in OWL2-DL, producing two ontologies, one with metaclasses and one without them. The idea is to use the OWL 2 metamodeling capability, i.e., punning, to represent metaclasses, using the same URI to refer to a class and an individual at the same time in FMA-OWL2G MT. For example, the name Heart can be used both for the metaclass Heart and for the class Heart, instance of Organ with cavitated organ parts.

The drawback of the punning approach is that, although a class and an individual can share the same name, say C, they are treated as di erent entities. For example, even if the class C is entailed to be equivalent to a class D, the individuals C and D can still be di erent. This has been regarded as non-intuitive due to the lack of expected entailments (e.g., the individuals C and D should be the same). To deal with this problem, we apply the class-based approach from Glimm et al. [ 3 ] to enrich some small (but already challenging for DL reasoners) subsets of FMA-DLR ontology and accommodate metaclasses (cf. the last two ontologies in Table 1) with the Typing and MatSubClass functions proposed in [ 3 ].

Ontology FMA-DLR FMA-FullR FMA-Constitutional FMA-OWL2G noMTC FMA-DLR M1 FMA-DLR M2

RT FaCT++ HermiT TrOWL MORe Recall

C 32.425 s 46.94 s 32.596 s 47.794 s 100% C 121.041 s 1064.947 s 4.45 s 4.571 s 100% C t/o 3043.61 s 155.808 s t/o 100% C o/m t/o 967.59 s t/o N/A M 932.5 s 26.39 s 0.819 s N/A 100%

M t/o 737.43 s 2.863 s N/A 100%

Table 2 lists the classi cation (for the rst four ontologies) and materialisation (for the last two ontologies) time (reasoning time + retrieving time) from some of the state of the art DL reasoners (including FaCT++ v1.6.2, HermiT v1.3.8, TrOWL v1.3 and MORe v0.1.3 [ 15 ]) over the FMA ontologies in Table 1. The machine used for the experiment is a MacBook, with CPU 2.26 core 2 duo, Ram 8 GB and 6 GB allocated to JVM. The last column of Table 2 reports the recall (on the number of subsumptions among named classes) of TrOWL with respect to results of HermiT. Note that FaCT++ had a datatype error for the FMA-DLR ontology, so we did not import the FMA-DLR ontology into the FMA-FullR ontology when testing FMA-FullR. Moreover, as MORe does not support ABox reasoning, its time with the FMA-DLR M1 and FMA-DLR M2 ontologies is not reported.

Dealing with Unsatis able Concepts in FMA

Constitutional

An ontology is called incoherent [ 17 ] if it contains unsatis able concepts, which are equivalent to the bottom concept ? and can not have any instance. Unsatisable named concepts (except the bottom concept ?) in a constructed ontology usually indicates possible design aws. For example, 33,433 out of 41,648 concepts are unsatis able in the FMA-Constitutional ontology. This was apparently not intended since the current version of FMA has already eliminated all these unsatis abilities.

Understanding ontology incoherence is not trivial. Incoherence can usually be explained and resolved by computing justi cations [ 8 ], i.e., minimal entailmentpreserving sub-ontologies. However, computing justi cations with a black-box algorithm requires a large number of entailment checking, which can be expensive given the complexity of reasoning and size of the ontology. Also, looking into 33,433 justi cations to debug the ontology will be very time consuming.

We notice that some of the concepts are unsatis able due to other unsatisable concepts. For example in FMA-Constitutional we can infer N euron v ? and Central neuron v N euron, hence we also have Central neuron v ?. In this case, Central neuron is unsatis able due to the unsatis ability of N euron. Such a phenomena has been formally characterised by Kalyanpur et al. [ 9 ] as root and derived unsatis able concepts. Particularly, A is a derived unsatis able concept if there is a justi cation for A v ? that contains a justi cation for B v ?, where B is another unsatis able concept, and B is called the parent of A. Otherwise, A is a root unsatis able concept.

The REL reasoner in TrOWL is using a forward-chaining completion-based algorithm, in which each rule infers a set of consequence axioms from a set of antecedence axioms. Such an algorithm can be easily extended to compute justi cations on the y by incorporating a truth-maintenance system (TMS) [ 13 ]. However naively applying such a solution has the following limitations: 1. For big and complex ontologies, maintaining the entire in TMS is a big overhead on reasoning. In fact, we are only interested in justi cations for unsatis ability but not the others so a fully- edged TMS is unnecessary. 2. Repairing all the root unsatis abilities cannot always repair all the derived unsatis abilities because a derived unsatis ability may have another justication that depends on no other unsatis ability. In this case, one need to iteratively reclassify, debug and repair. For di cult ontologies such as FMA Constitutional, we would like to minimise the number of such iterations.

In order to improve e ciency, we introduce Type I and Type II unsatis able concepts as approximations to the root and derived unsatis able concepts with the following procedure in REL: 1. When a rule infers A v ?, if the antecedences contain B v ?, where both A and B are named concepts in the original ontology, we label A as a Type II unsatis able concept. Otherwise, we label A as a Type I unsatis able concept. 2. We continue reasoning on Type II concepts regardless their unsatis ability, and label them with Type I if possible. They will not be treated immediately as sub-concept of all concepts.

The above point 2 is important to explore alternative derivation of unsatis ability for Type II concepts. If such a derivation does not depend on other unsatisability, the concept will be labeled Type I as well. It is possible for a derived unsatis able concept to be labeled earlier than its parent, making it mistakenly labeled as a Type I. For example, considering the following axiom: A v B; B v C; B v :C; (1) (2) (3) if we infer A v C from (1) and (2), then A v :C from (1) and (3), and then A v ?, then we have A as a Type I unsatis able concept. To avoid such situations as much as possible, we apply a depth- rst classi cation strategy, always classifying super-concepts before classifying sub-concepts.

Using the above mechanism we are able to distinguish the di erent types of unsatis able concepts in the FMA-Constitutional. Results show that only 145 concepts belong to Type I, which is only 0:43% of all the unsatis able concepts. By examining their justi cations, we realise that they are due to similar reasons. Particularly, there is a boolean-valued functional datatype property has mass in the ontology. With the axioms in FMA Constitutional, it is possible to infer both A v 9has mass:ftrueg and A v 9has mass:ff alseg for concept A, making A unsatis able. Another boolean-valued functional datatype property has inherent 3-D shape has a similar problem. There are in total only 6 concept axioms with these two properties. Debugging these 6 axioms is apparently much easier than debugging all the 122,136 logical axioms, or the justi cations of all the 33,433 unsatis able concepts. 5

Conclusion and Outlook

This paper brie y introduces the TrOWL ontology reasoning infrastructure. Our evaluations with the FMA ontologies indicate that approximate reasoners can be useful for reasoning and debugging complex ontologies. The tested FMA ontologies are only some of the existing ones. We will further test more FMA ontologies, in particular those related to metamodeling.

References

1. O. Dameron , D. L. Rubin , and M. A. Musen . Challenges in converting frame-based ontology into OWL: the Foundational Model of Anatomy case-study . In the Proc. of the AMIA Annual Symposium , 2005 .

2. Birte Glimm , Ian Horrocks, and Boris Motik . Optimized description logic reasoning via core blocking . In IJCAR , pages 457 { 471 , 2010 .

3. Birte Glimm , Sebastian Rudolph , and Johanna Volker. Integrated metamodeling and diagnosis in owl 2 . In Proceedings of the 9th International Semantic Web Conference , volume 6496 of LNCS , pages 257 { 272 . Springer, November 2010 .

4. C. Golbreich , J. Grosjean , and S. J. Darmoni . The fma in owl 2 . In Proceedings of the 13th conference on Arti cial intelligence in medicine , AIME'11 , pages 204 { 214 , Berlin, Heidelberg, 2011 . Springer-Verlag.

5. Christine Golbreich , Songmao Zhang, and Olivier Bodenreider . The foundational model of anatomy in owl: Experience and perspectives . J. Web Sem ., 4 ( 3 ): 181 { 195 , 2006 .

6. Rogers JE , Roberts A , Solomon WD , van der Haring E , Wroe CJ , Zanstra PE , and AL. Rector . Galen ten years on: Tasks and supporting tools . In Proceedings of the MEDINFO2001 , pages 256 { 260 . IOS Press, 2001 .

7. Nophadol Jekjantuk , Je Z. Pan , and Gerd Grner . Verifying and Validating MultiLayered Models with OWL FA Toolkit . In the Proc. of the Extended Semantic Web Conference (ESWC2010) , 2008 .

8. Aditya Kalyanpur , Bijan Parsia, Matthew Horridge, and Evren Sirin . Finding all justi cations of owl dl entailments . In ISWC/ASWC 2007 , pages 267 { 280 , 2007 .

9. Aditya Kalyanpur , Bijan Parsia, Evren Sirin, and James Hendler . Debugging unsatis able classes in owl ontologies . Web Semantics: Science, Services and Agents on the World Wide Web , 3 ( 4 ): 268 { 293 , 2005 .

10. Natalya Fridman Noy and Daniel L. Rubin. Translating the foundational model of anatomy into owl . J. Web Sem ., 6 ( 2 ): 133 { 136 , 2008 .

11. Je Z. Pan and Edward Thomas. Approximating OWL-DL Ontologies . In the Proc. of the 22nd National Conference on Arti cial Intelligence (AAAI-07) , pages 1434 { 1439 , 2007 .

12. Stearns M. Q. , Price C. , Spackman K. A. , and Wang A. Y. Snomed clinical terms: overview of the development process and project status . In Proceedings of the AMIA Symposium , American Medical Informatics Association, pages 662 { 666 , 2001 .

13. Yuan Ren and Je Z Pan . Optimising ontology stream reasoning with truth maintenance system . In Proceedings of the 20th ACM international conference on Information and knowledge management , pages 831 { 836 . ACM, 2011 .

14. Yuan Ren , Je Z. Pan , and Yuting Zhao . Soundness Preserving Approximation for TBox Reasoning . In the Proc. of the 25th AAAI Conference Conference (AAAI2010) , 2010 .

15. Ana Armas Romero, Bernardo Cuenca Grau, and Ian Horrocks . More: Modular combination of owl reasoners for ontology classi cation . In Proceedings of the 11th International Semantic Web Conference (ISWC 2012 ), LNCS. Springer, 2012 .

16. Cornelius Rosse and Jose L. V. Mejino Jr. A reference ontology for biomedical informatics: the foundational model of anatomy . Journal of Biomedical Informatics , 36 ( 6 ): 478 { 500 , 2003 .

17. Stefan Schlobach and Ronald Cornet . Non-standard reasoning services for the debugging of description logic terminologies . In IJCAI , pages 355 { 362 . Morgan Kaufmann, 2003 .

18. Bart Selman and Henry Kautz . Knowledge compilation and theory approximation . J. ACM , 43 ( 2 ): 193 { 224 , March 1996 .