Mappings between related ontologies are increasingly used to support data integration and analysis tasks. Changes in the ontologies also require the adaptation of ontology mappings. So far the evolution of ontology mappings has received little attention albeit ontologies change continuously especially in the life sciences. We therefore analyze how mappings between popular life science ontologies evolve for di erent match algorithms. We also evaluate which semantic ontology changes primarily a ect the mappings. Our results can be valuable for users working with ontology mappings, e.g., one can learn from past ontology/mapping changes and their correlation to estimate possible mapping changes if new ontology versions become available.
Ontologies are heavily used, e.g., to uniformly annotate and categorize objects.
Di erent ontologies of the same domain often contain overlapping and related
information. For instance, information about mammalian anatomy can be found in
NCI Thesaurus [
Mappings between related ontologies are useful in many ways, in
particular for data integration and enhanced analysis. For instance, such mappings are
needed to merge ontologies to create an integrated ontology such as the
crossspecies Uber anatomy ontology [
Ontologies underly continuous modi cations so that new ontology versions
are released periodically [
The evolution of ontology mappings has received very little attention so far, especially for the life science domain. For example it is unknown to what degree and how mappings between popular life science ontologies change and how ontology changes a ect ontology mappings. There are many ways to compute mappings and it is not clear to what degree di erent match methods result in di erently stable ontology mappings. Such information is expected to be useful for deciding about whether a previous ontology mapping is still reliable and upto-date or whether one has to perform an expensive adaptation of the mapping.
To address these questions and issues we make the following contributions: { We introduce a general versioning scheme which allows for studying the evolution of both, ontologies and mappings. (Sec. 2) { We propose a generic change model to measure and compare the degree of change for ontologies and mappings. The model supports analyzing the impact of ontology evolution on mapping evolution, e.g., what ontology changes lead to the addition or deletion of correspondences in the mapping. (Sec. 3) { We apply our model to three life science scenarios and evaluate how mappings between popular life science ontologies evolve. We also investigate mapping evolution for di erent match techniques. (Sec. 4) In Sec. 5 we describe related work and conclude in Sec. 6.
2.1
Prelimiaries In general an ontology O = (C; R; A) consists of concepts C which are interrelated by directed relationships R. Each concept has an unambiguous identi er such as an accession number. A concept typically has further attributes a 2 A to describe the concept, e.g., name, synonyms, or de nition. A relationship r 2 R forms a directed connection between two concepts and has a speci c type, e.g., is a or part of. An ontology mapping (ontology alignment) MO1;O2 is a set of correspondences (c1; c2) whereby each correspondence interconnects two concepts c1 2 O1 and c2 2 O2 of the two ontologies. The mapping semantics depends on the intended use case but we assume that all correspondences of a mapping express the same semantic type, e.g., same-as or is-related-to. 1 As of 2012, the current reference ontology mapping has been created in 2007. diff(O11,O12) diff(O1k-1,O1k) O12 ...
O1k-1 O1k mdiff(M1,M2)
diff(O21,O22) MO12,O22 = M2
...
MO1k-1,O2k-1 = Mk-1
mdiff(Mk-1,Mk) MO1k,O2k = Mk O22 ...
O2k-1 O2k diff(O2k-1,O2k)
Current version k Since a purely manual creation of ontology mappings is a tedious and laborintensive task such mappings are usually determined by semi-automatic ontology matching techniques (see Sec. 5 for Related Work). Most matching approaches are metadata-based, i.e., they use the ontology representations themselves to nd related concepts, in particular the names of concepts and contextual information like the names of the parent or child concepts within the ontologies. In our evaluation, we will analyze mapping changes for three typical metadata-based matchers (Sec. 4). We de ne an ontology version Ov = (Cv; Rv; Av) as a snapshot of an ontology O released at a speci c point in time. For simplicity we enumerate the versions with ascending numbers v = 1; 2; : : : rather than using the actual release dates.
Ontology changes a ect previously determined ontology mappings so that these mappings should be continuously adapted. Fig. 1 illustrates the general versioning scheme we adopt in this paper. There is a series of versions (v = 1 : : : k) for a pair of ontologies O1 and O2 that are connected by an ontology mapping MO1;O2. For simplicity we determine ontology mappings only between ontologies of the same version number, i.e., we create mappings Mv only between ontology versions O1v and O2v referring to the same speci c point in time.
The di erence between two ontology and mapping versions is denoted by dif f (Ov; Ov+1) and mdif f (Mv; Mv+1), respectively. The next section explains dif f and mdif f in more detail. 3
We rst describe our change model for ontologies and mappings and categorize
the changes into di erent groups. We also propose simple change ratio
indicators to assess the evolution intensity between successive ontology and mapping
Change operation
versions. We then propose indicators to assess the impact of ontology changes
on ontology mappings.
We start by de ning what changes can occur between successive ontology
versions Ov and Ov+1. Our model is based on the COntoDi algorithm described
in [
Table 1 lists all considered change operations and additionally categorizes them into one of three groups. The rst group contains information extending operations that add information in Ov such as new concepts, relationships or attribute values. The second group, information reduction, includes change operations that remove information from Ov. All other operations including split and merge changes belong to the revise group.
For a quantitative change analysis we assign concepts both from Ov and Ov+1 based on their change operations to one of the following sets: { Extension set: Ext(Ov7!v+1) = set of concepts in Ov [ Ov+1 where all concept-related change operations are information extending. { Reduction set: Red(Ov7!v+1) = set of concepts in Ov [ Ov+1 where all concept-related change operations are information reducing. { Revision set: Rev(Ov7!v+1) = set of concepts in Ov [Ov+1 that are involved in at least one change operation but belong neither to Ext nor to Red. Each concept is thus related to a revise operation or is related to both extending and reducing operations.
All other concepts remain unchanged, i.e., they are not a ected by any change operation. Fig. 2 illustrates an evolution example for two ontologies O1 and O2. For example, the evolution from O21 to O22 might contain three change operations: insertion of concept f2, deletion of concept d2, and an attribute value change for concept e2. The three concepts are thus assigned to Ext, Red, and Rev, respectively, i.e., Ext(O217!2) = ff2g, Red(O217!2) = fd2g, and Rev(O217!2) = fe2g. All other concepts of Fig. 2 are not a ected by the change operations.
The size of the three concept sets Ext, Red, and Rev quantitatively characterizes the degree of change during the evolution from Ov to Ov+1. We therefore de ne the ontology change ratio as follows:
OCR(Ov7!v+1) = jExt(Ov7!v+1) [ Red(Ov7!v+1) [ Rev(Ov7!v+1)j jOv [ Ov+1j
The ontology change ratio for O2 of our running example (Fig. 2) is thus OCR(O217!2) = jff2; d2; e2gj=jfa2; b2; c2; d2; e2; f2gj = 0:5. 3.2
Mapping Changes For ontology mapping evolution we employ a simple model that distinguishes between the addition and deletion of correspondences. Thus, between two consecutive mapping versions Mv and Mv+1 we consider whether a new correspondence has been added (Add) or a previous one has been removed (Del). We group changed correspondences into the following sets: { Addition set: Add(Mv7!v+1) = Mv+1nMv { Deletion set: Del(Mv7!v+1) = MvnMv+1
All other correspondences appear in both mapping versions and are thus unchanged. Based on the introduced sets we de ne the mapping change ratio as follows:
In the example of Fig. 2 there are two new correspondences, i.e., Add(M17!2) = f(b1; b2); (f1; f2)g. and two deleted correspondences, (b1; c2) and (d1; d2). Since there is one unchanged correspondence (a1; a2), the mapping change ratio M CR(M17!2) equals 4=5. 3.3 Impact of Ontology on Mapping Changes To determine how ontology changes in uence or trigger mapping changes it is useful to interrelate the di erent kinds of ontology changes and mapping changes. For this purpose, we interrelate the three sets of changed concepts (Ext, Red, Rev) with the two sets of changed correspondences (Add, Del). We will de ne six corresponding indicators and use them for both analyzing mapping evolution (see Sec. 4).
The impact ratio is the share of changed concepts that actually had an impact on the correspondences. For any set of ontology changes OCh (Ext, Red, or Rev) and mapping changes MCh (Add or Del) it is de ned as follows: IR(OCh; MCh) = jfc 2 OChj9c0 : (c; c0) 2 MCh _ (c0; c) 2 MChgj jOChj
For example, to determine which fraction of additive ontology changes led to new correspondences we determine the impact ratio for OCh = Ext(O117!2) [ Ext(O217!2) and MCh = Add(M17!2). For the example in Fig. 2, two (f1 and f2) out of the three Ext-concepts appear in the set of added correspondences, i.e., the changes in these two concepts had an impact on the mapping. Therefore IR(Ext; Add) equals 23 .
One would expect that Ext concepts mostly lead to correspondence additions whereas Red concepts usually account for correspondence deletions. However, as we will see in our evaluation (see Sec. 4), Ext concepts may also trigger correspondence deletions and Red concepts may lead to new correspondences depending on the match technique.
After introducing the experimental setup, we analyze ontology and mapping evolution for di erent life science scenarios. We then compare mapping evolution for di erent match strategies and evaluate the impact of ontology changes on mapping changes. 4.1
Setup
We consider three mapping scenarios:
{ Anatomy : map Adult Mouse Anatomy Ontology (MA) to the anatomy part
of NCI Thesaurus (NCITa)
{ Molecular Biology : map the two Gene Ontology[
Functions (MF) and Biological Processes (BP)
{ Chemistry : map Chemical Entities of Biological Interest (ChEBI) [
Thesaurus (NCIT) For each input ontology we map 10 versions on a half year basis between 2006-06 and 2010-12 with each other. We use the following meta-data based matchers to compute the con dence (similarity) for any concept pair of two ontologies: { Name: String (trigram) similarity of concept names { NameSyn: Maximal string (trigram) similarity of names and synonyms { Context : String (trigram) similarity of the concatenated parent, concept, and children names
In this study we focus on the evolution of ontology mappings and do not
evaluate the quality of matching. The choice of match strategies is based on
previous studies where matching on concept names and synonyms achieved high
quality especially for anatomy ontologies [
Ontology and Mapping Evolution Fig. 3 gives an overview about the ontology and mapping sizes as well as their growth between June 2006 and Dec. 2010. For Anatomy, the combined size of concepts in domain and range ontology (jCj) grew only slightly by a factor 1.1 to almost 10,000 concepts. By contrast, jCj increased by 60 - 70 % to 30,000 and 120,000 concepts for Molecular Biology and Chemistry. In two of the three scenarios (Anatomy and Molecular Biology ), the mappings grow similarly strong as the ontologies while the Chemistry mappings grew by up to a factor 6. The especially high mapping growth for the Context matcher seems in uenced by its Anatomy Molecular Biology Chemistry
ontologies Name 0.6 NameSyn 0.6 NameSyn 0.8 Context 0.6 |C2006-06| growth |M2006-06| growth |M2006-06| growth |M2006-06| growth |M2006-06| growth 8,806 1.1 1,496 1.1 1,636 1.1 1,264 1.1 1,272 1.0 18,974 1.6 852 1.1 1,531 1.7 251 1.6 465 1.6 69,005 1.7 1,353 3.9 3,242 3.2 1,930 3.7 277 6.1 very small mapping size which in turn is caused by its need to nd similar names not only for the concepts but also for their parent and child concepts. Comparing the results for NameSyn with two di erent thresholds, we nd that a higher threshold produces smaller mappings and achieves only a relatively small coverage, especially for Molecular Biology. For Molecular Biology, the Name matcher proved to determine the most stable mappings.
Fig. 4(a) shows ontology change factors (see Sec.3.3) between succeeding versions for the three domains during the 5-year observation period. For Anatomy there were only few changes compared to the other two domains. Molecular Biology shows high change rates until 2007 (nearly 40%). From 2008 on, change rates are comparable to those of Chemistry (around 20%). Fig. 4(b) illustrates more detailed mapping evolution results for NameSyn 0.6 in Molecular Biology. In general, correspondence additions dominate leading to a nal mapping size of more than 2,500 correspondences. But there has also been a considerable number of deletions. In 2007-12 nearly 500 correspondences were removed from the mapping. This shows that there can be very heavy mapping changes. 4.3
Comparison of Match Strategies To analyze the mapping stability for di erent match strategies in more detail, we examine a possible correlation between ontology and mapping changes over time. We therefore compute ontology and mapping change factors for all three aAddddC(oMrrv→v+1) dDeleCl(oMrrv→v+1) |C|Morvr+|1| 3,000 221,,,055000000 iizsegpn 1,000 a
p 500 m 0 1.0 0.8 0.6 R C O0.4 0.2 0.0 (a)
OCR aAddddC(oMrr ) dDeleCl(oMrr ) |C|Morr| | Fig. 5. Ontology and mapping change factors for three life science domain examples (a) Anatomy, (b) Molecular Biology, (c) Chemistry match scenarios and the four match strategies (Fig. 5 a-c). For Anatomy, ontologies and mappings only slightly changed (see y-axis range), while the other two scenarios experience a surprisingly high degree of mapping changes between 10 and 80 %. Except for Chemistry we observe a strong correlation between the ontology change factor (black continuous line) and the mapping change factors of the di erent match strategies(colored dashed lines). The Name matcher was relatively stable in general while the Context matcher was most heavily in uenced by ontology evolution. This especially holds for Chemistry where 80% of the Context mappings changed in 2008. The reason for the relative instability of Context is mainly in its use of more ontological information that can change, i.e., changes on both parent and child concepts have an in uence. For instance, moving a concept from one parent concept to another might completely change a concept's context. For Molecular Biology the mappings, (especially NameSyn), changed heavily in 2007-12, although the maximum ontology evolution already occurred in 2007-06. This results from successive modi cation of GO-BP and GO-MF in 2007. The combined changes in both sub-ontologies seem to have led to numerous mapping changes in 2007-12. 4.4
Impact of Ontology on Mapping Changes
Anatomy Molecular Biology
Chemistry
IR Ext |Ext| →Add →Del 95 18.7% 0.1% 2,359 4.6% 0.7% 8,377 11.7% 1.2% |Red | by relating the concept to another one than before. Thus, a synonym deletion can lead to a correspondence deletion and addition in one evolution step. Finally, revised concepts (Rev ) trigger both, Add and Del. This is intuitive since revised concepts might have been extended and reduced in one evolution step (e.g., attribute addition and deletion). In general, ontology revisions account for a high share of mapping changes while deletions play only a minor role. We evaluated ontology and mapping evolution for three real-world life science domains (Anatomy, Molecular Biology and Chemistry ) and took four matchstrategies into account. The analysis results show that especially Molecular Biology and Chemistry underlie heavy ontology extensions and revisions whereas Anatomy is relatively stable. Since existing knowledge is mainly extended or revised, we nd only few ontology reducing changes for all domains. Ontology evolution heavily in uenced mappings computed by di erent metadata-based match strategies. Especially, the structural matcher Context produced rather unstable results whereas mappings based on the Name matcher are relatively stable. As expected, ontology extensions primarily lead to correspondence additions and information reducing ontology changes primarily lead to the removal of correspondences. Ontology revisions play an important role and result in both the addition and deletion of correspondences. 5
In the last decade, ontology matching to semi-automatically create ontology
mappings has become an active research eld (see [
Previous work on ontology evolution (see [
The evolution of ontology mappings has received only little attention so far.
In our previous work [
In contrast to previous work this study focuses on the impact of ontology
on mapping changes, i.e., we investigate (1) how ontology mappings change and
(2) study how ontology changes correlate with mapping changes for di erent
matchers. In our evaluation we use real-world data sets from several life science
domains. The mapping versions under investigation were created with
previously evaluated matchers such as name or name/synonym using the GOMMA
system [
We studied the evolution of ontology mappings and analyzed the ontology changes triggering mapping changes as well as the in uence of di erent match techniques. Our analysis covered three life science mappings and three match strategies. Except for anatomy ontologies, we observed that ontology mappings based on common match strategies using name and synonym information often experience heavy changes. The results indicate a signi cant correlation between ontology and mapping changes depending on the utilized match strategy and mapping coverage.
In future work, we plan to investigate how known ontology changes can be used to semi-automatically adapt ontology mappings without a completely new mapping determination.