Ontologies and their associated mappings in life sciences play a central role in several semantic-enabled tasks. However, the continuous evolution of these ontologies requires updating existing concept alignments. Whereas mapping maintenance techniques have mostly handled revision and removal type of ontology changes, the addition of concepts demands further studies. This article proposes a technique to re ne a set of established mappings based on the evolution of biomedical ontologies. We investigate ways of suggesting correspondences with the new version of the ontology without applying a matching operation to the whole set of ontology entities. Obtained results explore the neighbourhood of concepts in the alignment process to update mapping sets. Our experimental evaluation with several versions of aligned biomedical ontologies shows the e ectiveness in considering the context of new concepts.
Over the last decade the biomedical domain has exploited ontologies and their
capabilities for various purposes ranging from information retrieval to data
management and sharing. However, the size of this domain often requires the use of
several ontologies whose elements are linked through mappings. Mappings are
the materialization of semantic relations between elements of interrelated
ontologies [
Creating mappings between ontologies is a complex task especially due to the
increasing size of biomedical ontologies. Several automatic ontology alignment
techniques have been proposed [
Ontologies in life sciences evolve over time to keep them up-to-date
according to the domain knowledge. Ontology changes may a ect mappings already
established or can be a source for treating mapping re nement. In this context,
in order to avoid the costly ontology re-alignment process, it is crucial to have
adequate mapping techniques to keep mappings semantically valid over time [
Coping with the mapping reconciliation problem in a semi-automatic way
entails many research challenges. First, it is di cult to evaluate the real
impact of the ontology evolution on mappings. For instance, changing an attribute
value may lead to invalidate a mapping in some cases. In these situations, the
challenging issue is to identify and classify the di erent cases. Second, several
types of ontology changes can be applied to an ontology, but it is unknown how
these di erent types of operations should be duly taken into consideration for
mapping reconciliation [
The design of techniques for mapping adaptation according to the di erent
types of ontology changes has been coped within existing approaches. Previous
work presented a mapping adaptation strategy for two out of three categories
of ontology evolution: removal of knowledge and revision of knowledge [
In this paper, we propose a mapping re nement methodology to update mapping sets taking ontology changes into account (based on new concepts added in ontology evolution). We study the use of conceptual information related to neighbour concepts for enhancing the mapping completeness. For this purpose, we investigate a technique to reuse already established mappings and to explore the role of neighbour concepts to derive new mappings. Our proposal allows suggesting new correspondences without applying a matching operation with the whole set of ontology entities.
Our experimental evaluation explored real-world biomedical ontologies and mappings established between them. We examine the quality of the automaticallysuggested enriched set of mappings with respect to the set of new correspondences observed in the o cial updated release of mappings via standard evaluation metrics. The achieved results show innovative ndings regarding the way mappings can be re ned based on new concepts added. We demonstrate that the local matching considering neighbour concepts is competitive with a matching operation with the whole target ontology.
The remainder of this article is organized as follows: Section 2 presents the related work; Section 3 presents the formal de nitions and problem statement. Section 4 reports on our approach to re ne ontology mappings under ontology evolution. Section 5 shows the used materials and the results obtained. Section 6 discusses the ndings whereas Section 7 draws conclusions and future work.
Previous studies have investigated semi-automatic approaches to adapting
ontology mappings when at least one of the mapped ontologies evolves [
Some techniques have used external resources aiming to improve and increase
the number and precision of established mappings. Stoutenburg [
The TaxoMap matching tool [
Other approaches have combined lexical-based and semantic-based algorithms,
mostly using resources available in the Uni ed Medical Language System (UMLS)1
for generating mappings. The use of UMLS as an external resource can be
interesting in various aspects: (1) favors an increase in the number of mapping, (2)
provides di erent synonyms terms for a given concept, and (3) de nes relations
between concepts in a semantic network. Zhang and Bodenreider [
Sekhavat and Parsons [
Pruski et al. [
Noy et al. [
In this investigation, we explore ontology change operations to leverage renement, in particular, concept addition. We contribute with a methodology to consider newly added concepts and investigate the context of candidate target concepts of existing mappings for re nement over time. We further evaluate the proposed algorithms by measuring the e ectiveness of our mapping re nement approach on real-world biomedical ontologies. 3
Ontology. An ontology O speci es a conceptualization of a domain in terms of
concepts, attributes and relationships [
Context of a concept. We de ne the context of a particular concept ci 2 CO as a set of super concepts, sub concepts and sibling concepts of ci, as following:
CT (ci; ) = sup(ci; ) [ sub(ci; ) [ sib(ci; ) where sup(ci; ) =fcj jcj 2 CO; r(ci; cj ) = \ @ " ^ length(ci; cj ) ^ ci 6= cj g sub(ci; ) =fcj jcj 2 CO; r(cj ; ci) = \ @ " ^ length(ci; cj ) ^ ci 6= cj g sib(ci; ) =fcj jcj 2 CO; ((sup(cj ) \ sup(ci)) _ (sub(cj ) \ sub(ci)))
^length(ci; cj ) ^ ci 6= cj g where is the level of the context. It represents the maximum value for the length between two concepts (in terms of their shortest relationship distance in the hierarchy of concepts) and the \@" symbol indicates that \ci is a sub concept of cj ". This de nition of CT (ci; ) is specially designed as the relevant concepts to be taken into account in the settings of this investigation on mapping re nement.
Similarity between concepts. Given two particular concepts ci and cj , the similarity between them can be de ned as the maximum similarity between each couple of attributes from ci and cj . Formally: (1) (2) sim(ci; cj ) = arg max sim(aix; ajy) (3) where sim(aix; ajy) is the similarity between two attributes aix and ajy denoting concepts ci and cj , respectively.
Mapping. Given two concepts cs and ct from two di erent ontologies, a
mapping mst can be de ned as:
mst = (cs; ct; semT ype; conf )
(4)
where semT ype is the semantic relation connecting cs and ct. In this article,
we di erentiate relation from relationship, where the former belongs to a
mapping and the later to an ontology. The following types of semantic relation
are considered: unmappable [?], equivalent [ ], narrow-to-broad [ ],
broad-tonarrow [ ] and overlapped [ ]. For example, concepts can be equivalent (e.g.,
\head" \head"), one concept can be less or more general than the other (e.g.,
\thumb" \ nger") or concepts can be somehow semantically related ( ). The
conf is the similarity between cs and ct indicating the con dence of their
relaj
tion [
Ontology change operations (OCO). An ontology change operation (OCO) is de ned to represent a change in an attribute, in a set of one or more concepts or in a relationship between concepts. OCOs are classi ed into two main categories: atomic and complex changes. Each OCO in the former cannot be divided into smaller operations while each one of the latter is composed of more than one atomic operation. In this paper, we pay further attention to the operations of concept addition which is an atomic operation.
Problem statement. Consider two versions of the same source ontology OSj at time j and OS j
j+1 at time j + 1, a target ontology OT , and an initial set of mappings MST between OSj and OTj at time j. Suppose that the frequency of new j releases of OS and OT is di erent and at time j + 1 only OS evolves. Since this j j evolution is likely to impact the mappings MST , it is necessary to re ne MST to guarantee the quality and completeness of MjS+T1. The quality is related to the consistency of mappings and it can be measured using precision. For instance, mappings cannot be established between removed concepts. The completeness refers to the recall of aligned concepts in MjS+T1. In this investigation, we study j how MST can be re ned (e.g., new mappings derived) based on ontology changes related to addition of knowledge. We address the following research questions: How to exploit existing mappings for mapping re nement based on new concepts added? Is it possible to reach mapping re nement for alignment of new concepts without applying a matching operation in the whole target ontology? What is the impact of using the context of concepts CT (ci; ) in both source and target ontologies on the mapping re nement e ectiveness? We consider that OT has not evolved (thus OTj and OT j+1 are the same version of the ontology OT ). OSj and OS j+1 are two distinct versions of the same ontology j+1 and we attempt to OS. At time j + 1, newly added concepts appear in OS re ne the original mapping set MSjT to provide a set of valid mappings MSj+T1. 4
Mapping Re nement under Concept Addition Changes
Our goal is to propose adequate correspondences for each newly added concept
at time j + 1. In the rst step, our approach identi es all newly added concepts
using the Conto-Di tool [
Figure 2 A illustrates a situation where there are two ontologies that have an alignment in time j. Each circle represents a concept of an ontology. Light blue circles represent concepts of source ontology. Yellow circles represent concepts of target ontology. Continuous lines represent mappings between concepts from source ontology and target ontology.
Figure 2 B illustrates a situation where source ontology evolve and change to time j + 1. The algorithm nd newly added concepts and explore the context of each newly added concepts. In this case, we are exploring the context of the right concept using source level 1. Purple circles represent newly added concepts. Dark blue circles represent concepts of a context with a certain source level; the number inside the circle represents the source level needed to access this concept.
After nding some concepts inside the newly added concepts' context that have an alignment in previous time, the concepts from target ontologies that have an alignment in previous time are added as candidate concepts. The context of each candidate concepts is explored and added as candidate concepts. Figure 3 illustrate this situation using target level 1. Red circles represent candidate concepts for a new concept from source ontology; the number inside the circles represent the target level needed to access this concept. Dashed lines represent a possible alignment between a new concept (in OSj+1) and candidate concepts (in OTj ).
Algorithm 1 computes the di between two given versions of the source ontology (line 1). For each newly added concept c1, the algorithm considers a i candidate concept namely ct0 in the target ontology by exploiting already existing mappings related to CT (ci1; ) (lines 4-8). Note that we recover the before evolution version (c0k) of the concept c1k found in the context of ci1.
For each ct0, the algorithm obtains a set of concepts from CT (ct0; ) (line 11). We determine a new re ned mapping by calculating the similarity between a new j+1 and a candidate cn 2 Ct. If the maximum similarity (among concept ci1 of OS the concept attributes) is greater than or equal to a threshold , the algorithm establishes a mapping between the newly added concept and the candidate target A. Initial situation
B. Finding source context concept. Algorithm 1 searches for the candidate ct that yields the maximum similarity value.
In order to compare with the results obtained by our approach (cf. Section5), we propose another algorithm that ignores new concepts' context to calculate similarity. It means that the algorithm computes the similarity between each newly added concepts with all concepts in the target ontology. More speci cally, these algorithm computes the di between two given versions of the source ontology. For each newly added concepts, it calculates similarity between all concepts with the target ontology. If there are any similarity greater than a threshold, Algorithm 1 Contextual approach to mapping re nement Require: OSj; OSj+1; OTj ; OTj+1; MjST ; ; ; 2 R Ensure: MA = fm1; m2; :::; mN g 1: Cadd dif fadd(OSj; OSj+1) fnewly added conceptsg 2: Ct ; finitialize target concepts of candidate mappingsg
1 3: for all ci 2 Cadd do 4: for all c1k 2 CT (ci1; ) do 5: if 9ct0 2 COT0 ; 9m(c0k; ct0) 2 M0ST then 6: Ct S fct0g 7: 8: 9: 10: 11: 12:
Ct end if end for mit ; for all ct 2 Ct do for all cn 2 CT (ct; ) do mcand argmax sim(ci1; cn) fCreate a mapping between concepts ci1 and cng if max(sim(ci1; cn)) then mit mcand
max(sim(ci1; cn)) 13: 14: 15: 16: 17: 18: 19: MA 20: end for 21: return MA
end if end for end for
MA S fmitg the algorithm creates a new mapping between the newly added concept and a target ontology's concept with the greatest similarity.
In our algorithms, source concept's attributes are compared with all target
concept's attributes to obtain similarity value between concepts. The value of
similarity between two concepts is the maximum value of similarity from their
attributes. The method used to calculate similarity a ects the precision and
recall. In this work, we explored Bi-gram Dice to calculate similarity. Bi-gram is
a sequence of two adjacent letters of a word. Dice's coe cient is de ned as twice
the number of common elements divided by sum of each elements. Formula 5
shows the application of Bi-gram Dice to strings X and Y. The n-gram's strength
is in the fact it has context sensitivity, but it not have good resolution when gram
size is increased [
Similarity = 2
(Bi Bi
gram(X) \ Bi gram(X) + Bi
gram(Y ) gram(Y )
(5)
We aim to validate the quality of the re ned set of mappings as the outcome
of our approach. Data used in this evaluation come from ve biomedical
ontologies: SNOMED-CT (SCT), MeSH, ICD-9-CM, ICD10-CM and NCI
Thesaurus. SNOMED-CT (Systematized Nomenclature of MedicineClinical Terms)
is an ontology which objective is to create a taxonomy of terms referring to
the medical environment and a framework of rules guaranteeing that each term
is used with exactly one meaning [
The mappings obtained by the proposed Algorithm 1 are compared with the o cial mappings (their new o cial release). Mappings between SNOMEDCT and ICD9CM is o ered by the International Health Terminology Standards Development Organisation (IHTSDO)4 . Mappings between MeSH and ICD-10-CM were o ered by the Catalogue et Indexation des Sites Mdicaux de langue Franaise (CISMeF)5. Table 2 shows the quantity of each mapping set between the ontologies used in this experiment.
To analyze results obtained experimentally, it was necessary to compare our obtained mappings with mappings created only for newly added concepts in the new version of the considered ontologies. Table 3 shows the quantity of mappings really considered in the metrics. 2 http://www.who.int/classi cations/icd/en/ 3 https://ncit.nci.nih.gov/ncitbrowser/ 4 ttps://www.nlm.nih.gov/research/umls/mapping projects/icd9cm to snomedct.html 5 http://www.chu- rouen.fr/cismef SCT-ICD9 #Mappings SCT-NCI #Mappings MeSH-ICD10CM #Mappings 2010-2009 84,519 2009-2009 19,971 2012-2011 4,631 2012-2011 86,638 2012-2012 22,732 2013-2011 5,378
The experiments were performed for the three datasets (SCT-NCI, SCTICD9 and MeSH-ICD10) considering SCT and MeSH as source ontologies. As assessed con gurations, we considered three source levels, three threshold values (0.5, 0.75 and 0.9), and four target levels. For each dataset, we xed source level and threshold to verify the results for each target level. After examining all target levels, we changed the threshold and repeated for each target level. After examining all threshold values, we changed source level and repeated the whole procedure for all thresholds and target levels.
We used three metrics to evaluate the results: Precision, Recall and FMeasure. These metrics were used comparing results obtained by our approach and expected results from the o cial mappings.
Precision is de ned as the relation between correctly identi ed mappings and identi ed mapping (Formula 6).
#Identif edAndCorrectM appings P recision = (6)
#Identif iedM appings
Recall is de ned as the relation between correctly identi ed mappings and those expected new o cial release of mappings (Formula 7).
Recall = #Identif edAndCorrectM appings #CorrectM appings (7) F-measure is the harmonic mean of precision and recall (Formula 8).
2 P recision Recall F M easure = (8)
P recision + Recall
Tables 4 (SNOMED-CT and NCI Thesaurus), 5 (SNOMED-CT and ICD-9) and 6 (MeSH and ICD-10) show the obtained results in terms of precision, recall and f-measure in applying our Algorithm 1 for the studied datasets.
Results in Table 4 reveal a decrease in precision and f-Measure for threshold set as 0.5 when it increases source level. The results increases in terms of precision, recall and F-measure for other thresholds. We found that the best results are obtained when increasing the level of the context in the source concept.
Results presented in Table 5 (concerning the mapping between SNOMEDCT and ICD-9) are di erent from those of SNOMED-CT and NCI. We observe an increase in recall when it increases source level, but it has lower precision. Table 5 presents the best results for the rst level in the source concept and with lower thresholds. We could not observe huge di erences in the results when increasing the context level of the target concept.
Table 6 presents the results for the re nement for MeSH and ICD-10. We observed an overall improvement of results when increasing the level of the source concept.
We evaluated our proposal in considering the neighbourhood for the derivation of new mappings associated to new concepts (Algorithm 1) with the approach in applying the matching with the whole target ontology. To this end, we applied the non-context approach in the datasets considering the threshold yielding the best results in Algorithm 1 obtained for each dataset. Table 7 shows the results concerning precision, recall and f-measure obtained for each dataset using the matching with all concepts in the target ontology. The comparison of results reveals that for the dataset SCT-NCI the results using all target concept as candidates were better. For the dataset SCT-ICD9, our context-approach is better; concerning the dataset MeSH-ICD10, the approaches obtained similar results. However, we need to consider that applying mapping candidates with the whole target ontology have a worst run-time complexity than our contextual approach. 6
This investigation aimed to create mappings to update ontology alignments based on new concepts added in novel ontology releases. Our approach have three variables a ecting mapping quality: threshold, target level and source level. Threshold increases precision, but decreases recall. It is caused by the fact that high threshold can remove false positive mappings, but as an e ect removes correct mappings. For two datasets (SCT-NCI and MeSH-ICD10) the increasing in precision compensated decreasing in recall. However, we observed for one dataset (SCT-ICD9) that a high threshold implied bad e ects.
Target level increases candidate concepts for mapping by increasing the context in the target ontology. It means that each new added concept has more options to compare. The increasing in candidate concepts means more chances to nd a correct mappings, but it can cause nding a wrong mapping when a wrong concept have a better results in terms of similarity value than the expected concept. For two datasets (SCT-NCI and MeSH-ICD10), precision increased between target level 0 and 1 and recall improved when target level increases. For one dataset (SCT-ICD9), precision decreased between target level 0 and 1 and recall had only minor e ects caused by changes in target level. We found that the results were very dependent on the characteristics of the datasets.
Source level increases source context to nd candidate concepts from the target ontology. Our approach depends if in the neighbourhood of a new concept there are concepts presenting a mapping in prior version. If the source level is low, new concepts have less chances to nd concepts mapped in prior version. In the worst case, if there is no concept mapped in a prior version, the new concepts are not analyzed to nd new mappings. Therefore, in our approach, the derivation of mappings related to new concepts depends directly on the source level. We found better results in improving the level of the source concept.
The analysis of results obtained by all concepts approach indicates that SCTNCI got better results using such approach. Whereas precision presents very similar results, the recall is very low using contextual approach. SCT-ICD9 presented better results using contextual approach. In this case, precision had good values using contextual approach, but f-measure su ered with low recall. Findings on the dataset MeSH-ICD10 presented similar results for both approaches. In summary, contextual approach implies in a better precision, but all concepts approach obtains a better recall.
This research found that is possible to exploit existing mappings for mapping re nement based on new concepts added. Our ndings indicated the possibility of reaching mapping re nement for alignment of new concepts in ontology evolution without applying a matching operation in the whole target ontology. We found further impact in considering the level of the source concept than in the target ontology for the e ectiveness of the ontology alignment re nement. 7
Ontology mappings play a central role for semantic data integration in the life sciences. However, domain knowledge update leads to new concepts in ontology versions. This requires to maintain mapping sets up-to-date according to the knowledge dynamics. We proposed a technique to re ne ontology alignments based on evolving ontologies. Our constructed algorithm considered the context of concepts in both ontologies as a way to nd the matching between concepts. Experimental evaluation with aligned ontologies in the life sciences demonstrated the e ectiveness of our approach. Future work involves further investigating heuristics to update the type of semantic relation in the re nement procedure.
This work was nancially supported by the S~ao Paulo Research Foundation (FAPESP) (grant #2017/02325-5)6. We also thank the Scienti c Initiation Program (PIBIC) from UNICAMP for the scholarship grant. 6 The opinions expressed in here are not necessarily shared by the nancial support agency.