Cross-ontology concept subsumption relationships facilitate the integration of ontologies by explicitly defining the generalization of a concept over other concepts in different ontologies. However, existing methods for discovering these relationships show poor performances and one of the problems is the lack of instance data in ontologies that can be used to identify cross-ontology subsumptions reliably. To address the problem, we present a novel method, SURD (SUbsumption Relation Discovery), which uses annotations on biomedical text corpora for populating ontologies with instances. Subsumption relationships between pairs of concepts are then determined based on their shared instances. SURD shows good performance when applied to biomedical ontologies, achieving precision values of 0:786 and 0:729 for cross-ontology subsumptions between the ontology pairs GRO-UMLS Metathesaurus and GENIAUMLS Metathesaurus respectively. As a practical application, we used SURD's subsumptions for automated ontological corpus annotation and achieved F-measures of 0:693 and 0:783 on the GRO and GENIA corpora respectively. These results are superior to the results of using subsumption relations inferred from equivalence relations (F-measures of 0:569 and 0:645) and subsumption relations identified with Hearst patterns (F-measures of 0:002 and 0:096).
Ontologies are continually being developed to model sub-domains
of the biomedical sciences. While the proliferation of ontologies
brings about greater expressivity in knowledge representation, it
also creates a new problem in knowledge sharing. Applications
using different ontologies face inter-operability issues when
relationships (e.g. equivalence, subsumption) between concepts
in different ontologies are not explicitly stated. The process of
discovering relationships between concepts in different ontologies
is known as Ontology Alignment
For example, consider the integration of two populated ontologies, O1 and O2, and a query of listing all instances of Ci in the integrated ontology where Ci is originally a concept in O1. The answers of the query consist of the instances of Ci and its descendants in O1, as well as the instances of O2 concepts which are semantic equivalences and descendants of Ci. We can find some of the O2 instances by using equivalence relations between O1 and O2 concepts. For example, if there is an ancestor concept of Cj , Cja, which is equivalent to Ci or one of its descendant concepts, Cid, we can infer through description logics that Cj v Ci:
Cj v Cja ´ Cid v Ci However, it is not always possible to find equivalent concepts Cid and Cja that act as bridges for inferring meaningful subsumption relations. For example, if two ontologies are orthogonal, it is most likely that only a few top-level concepts (e.g. Thing) are shared by the two ontologies, and the subsumption relations of such generic concepts are not very useful for knowledge sharing. We will show that there are many subsumption relations between biomedical ontologies that cannot be deduced from equivalence relations and that they are highly useful for inter-operability between ontologies.
We propose an instance-based technique, SURD (short
for SUbsumption Relations Discovery) to find cross-ontology
subsumption relations directly. This technique determines whether
a subsumption relationship exists between a pair of concepts based
on the common instances they share. However, many existing
ontologies are schema ontologies with no instances
The outline of the paper is as follows: Related work is presented in Section 2. Section 3 describes the SURD technique that finds subsumption relations between different ontologies while in Section 4, we describe the experiments we carried out and present the results. We show applications of our technique in Section 5, before finally concluding the paper in Section 6. to determine if a subsumption relationship exists between them. We give an outline of SURD in Figure 1.
used in populating
Ontology
Oi Annotator
Ai Text Corpus,
P Annotator
Aj produces produces uses Ontology annotated Corpus,
Pi Ontology annotated Corpus,
Pj uses 2
The discovery of relationships between concepts in different
ontologies has been extensively researched and previous works
have been surveyed in
Instance-based methods
Given a pair of ontologies Oi and Oj , we want to find all triplets < Ci; R; Cj > where Ci 2 Oi, Cj 2 Oj and R 2 f´ ; @; A; ?g. Ci ´ Cj means that Ci and Cj are equivalent concepts. Ci @ Cj indicates that Ci is a sub concept of Cj , while Ci A Cj means the inverse subsumption relation. Ci ? Cj means Ci and Cj have no subsumption or equivalence relationship. SURD discovers equivalence and subsumption relationships by populating the ontologies with instances from textual annotations and using heuristics based on the shared instances of two concepts Fig. 1. Overview of the Subsumption Relations Discovery (SURD) technique 3.1
Using Annotations as Instances
We propose to populate ontologies with annotated phrases of
text from publicly available biomedical literature. Two types
of resources can be used: 1) Corpora manually annotated with
ontology concepts (e.g. GENIA Corpus
Given a pair of ontologies Oi and Oj , a corpus P consisting of n documents, and two annotators Ai and Aj which annotate the documents using Oi and Oj , respectively, we annotate the documents in P using Ai and Aj to get two annotated corpora Pi and Pj . Each phrase (or mention) m® in document d¯ of P annotated with a concept C° 2 Oi(j) is then made an instance of C° . Essentially, our objective is to compare two sets of annotations on the same set of documents to find out which pairs of concepts are frequently used to annotate the same mentions as subsumption relationships potentially exist between these pairs.
The first step of our method is to locate mentions annotated by both annotators. This is not always straightforward because different annotators have different guidelines for annotation, particularly with regards to mention boundary. For example, given the sentence “spiB, like spi-1, was found to be expressed in various murine and human hematopoietic cell lines...”, annotator A1 might annotate the mention hematopoietic cell lines with the concept Cell while annotator A2 might annotate the mention cell lines with the concept Cell Line. In this example, cell lines and hematopoietic cell lines refer to the same semantic entity and thus, the concepts Cell and Match mentions produces
Equivalent mentions
Find subsumptions based on shared
instances used in populating OntOoljogy
Legend
Process Data Ontology Input (to process) Cell Line share the same mention and form a candidate pair for subsumption. We consider two mentions to be matches if they have the same head noun. 3.2
Finding Subsumptions based on Shared Instances We use an indicator known as the Co-Annotation Ratio (CAR) to determine subsumption relationships. The Co-Annotation Ratio between two concepts Cp 2 Op and Cq 2 Oq, CARpq, computes the ratio of mentions annotated with both Cp and Cq to the number of mentions annotated with Cp, and is expressed by the following equation:
CARpq = jfmpjmp : Cp; mq : Cq; mp ´ mqgj
jfmpjmp : Cpgj where the notation m : C, defines m to be an instance of concept C and mp ´ mq is true if mp and mq are matched in the mentionmatching step. CAR is asymmetric and we compare CARij and CARji in order to determine the relationship between Ci and Cj . We propose the following heuristics using the two indicators to determine the concept relation: 1. If CARij is high and CARji is low, then Ci @ Cj 2. If CARij is low and CARji is high, then Ci A Cj 3. If CARij is high and CARji is high, then Ci ´ Cj 4. If CARij is low and CARji is low, then Ci ? Cj
The first rule states that, if a large proportion of the instances (or mentions) belonging to Ci also belongs to Cj but only a small proportion of the instances belonging to Cj belong to Ci, then Ci is highly possible to be a subsumee of Cj . In fact, this is a relaxation to the definition of a subsumption relation which depicts that C® @ C¯ if and only if all instances of C® are also instances of C¯ . We introduce the relaxed heuristic in order to enhance the sensitivity of subsumption relation identification. The second rule represents the converse of the first. The third rule states that if a large proportion of the instances belonging to Ci also belong to Cj and vice versa, we consider the two concepts to be equivalent. This method of statistical analysis allows us to identify both equivalence and subsumption relations at the same time. Lastly, if both Ci and Cj have large proportions of instances which are not common, Ci and Cj are most likely disjoint. In SURD, we consider a CAR ¸ 0:5 to be high and a CAR < 0:5 to be low. 4
Experiments were performed on two pairs of ontologies using
two different corpora. The first is the GRO corpus with 200
PubMed abstracts and the second is the 2008 version of the GENIA
corpus consisting of 1000 PubMed abstracts. The two corpora
were manually annotated by human experts with concepts of
biological entities from two ontologies, namely the Gene Regulation
Ontology
The three ontologies were chosen because they have different granularities. The GENIA ontology is a coarse-grained ontology with leaf concepts which are general like Protein Molecule and Carbohydrate. On the other hand, the Metathesaurus has a wide coverage and its leaf concepts are mostly fine-grained and very specific (e.g. p56 and Glucose). Therefore, we can expect to find many subsumption relations between the two ontologies. GRO is relatively coarse-grained, as compared to the Metathesaurus, but has very specific concepts regarding the domain of gene regulation. We show that SURD works well with the domain-specific ontology GRO as well as with the generic GENIA ontology.
The output of SURD is a set of triplets ASURD(Oi; Oj ) =
f< Ci; R; Cj >g. We evaluated this output ASURD(Oi; Oj )
by measuring the precision of a randomly chosen subset
ASRURD(Oi; Oj ) through manual validation by a biologist. We
were not able to measure the recall as we do not have a complete
reference set of subsumption relations between GRO-UMLS and
GENIA-UMLS. Since subsumption relations can be inferred from
equivalence relations, we also mark the triplets in ASURD(Oi; Oj )
which are inferrable from equivalence relations. This allows us to
find the discovered subsumption relations which are not redundant
and truly useful. The steps taken in our evaluation are as follows:
1. Finding relations in ASURD(Oi; Oj ) that are inferrable from
equivalence relations
a. We use BOAT
R = Rm. d. Precision = Number of correct triplets in ASRURD(Oi; Oj ) n
We make use of the subsumption and equivalence relations discovered by SURD for automatic ontological corpus annotation. This application is dependent upon UMLS, which is a well-known lexical resource in the biomedical domain. By using MetaMap, which automatically recognizes UMLS terms in text, we can locate the instances of the UMLS Metathesaurus concepts and then link them to the corresponding concepts of GENIA ontology and GRO through the subsumption and equivalence relations. Note that we can infer generalizations, but not specificities. In other words, we can use CGRO w CUMLS relations, but not CUMLS A CGRO relations. For example, we can infer that a mention NF kappa B annotated with the concept Transcription Factor is also a Protein if Transcription Factor @ Protein is true. However, we cannot infer anything about the same mention from the subsumption SOX9 @ Transcription Factor. The automatic annotation of text with GRO concepts is a three-step process, as shown in Figure 2. Sentences are first automatically annotated with UMLS Metathesaurus concepts using MetaMap. Next, GRO concepts which are equivalent to or more general than the UMLS concepts are retrieved from the correspondences found by SURD. Lastly, the retrieved GRO concepts are used to annotate the mentions which their corresponding UMLS concepts were used to annotate.
The upstream region of the human homeobox gene HOX3D is a target for regulation by retinoic acid and HOX homeoproteins.
1) Annotate sentence with MetaMap The upstream region of the human homeobox gene [UMLS: C1415679 (HOX3D)] HOX3D is a target for regulation by [UMLS: C0040845 (Retinoic Acid)] retinoic acid and [UMLS: C0242617 (Homeoproteins)] HOX homeoproteins.
2) Look up subsumptions between UMLS and GRO
concepts UMLS: C1415679 (HOX3D) UMLS: C0040845 (Retinoic Acid) UMLS: C0242617 (Homeoproteins) < < <
GRO: Homeobox GRO: Retinoic Acid
GRO: Protein 3) Convert MetaMap annotations to GRO annotations
using subsumptions The upstream region of the human homeobox gene [GRO: Homeobox] HOX3D is a target for regulation by [GRO: Organic Chemical] retinoic acid and [GRO: Protein] HOX homeoproteins.
To evaluate the performance, we use a cross-validation approach where Precision, Recall and F-Measure are used as performance measures. The following steps were carried out to evaluate SURD when used for the automatic annotation of GRO Corpus with GRO concepts by using MetaMap. The process was repeated for the annotation of GENIA corpus with GENIA ontology concepts by using MetaMap and any reference to GRO can be replaced with GENIA for the second experiment.
1. Split the document sets, PUMLS and PGRO (i.e. the GRO corpus annotated with UMLS and GRO concepts, respectively), into 10 folds: F0; F1; : : : F9. 2. For each iteration t from 0 to 9, find the set of t triplets ASURD(GRO; U M LS) using SURD, based on the annotations in the documents in all folds but Ft.
t 3. Filter ASURD(GRO; U M LS) to keep only those triplets <
CGRO; R; CUMLS > where R 2 f´; Ag 4. For each mention mi of fold Ft annotated with CUMLSi by MetaMap in PUMLS , we annotate mi with each concept CGROi® where < CGROi®; w; CUMLSi >2 t
ASURD(GRO; U M LS). 5. Consequently, a mention mi in fold Ft of PUMLS is annotated with zero or more GRO concepts, which forms a set Xi = fCGROi®jCUMLSi v CGROi®g. We use the reference concept CG0ROi to determine if mi is cross-annotated correctly, where CG0ROi is the concept used to manually annotate m0i, the matching mention of mi in PGRO. We find the average Precision, Recall and F-Measure over all folds for a corpus containing k mentions using: ² Precision = §ikjfCGROi®2XijCGROi®wCG0ROigj
§ikjXij ² Recall = §ikjfCG0ROij9CGROi®2Xi;CGROi®wCG0ROigj §ikjfCG0ROigj ² F-Measure = 2£P recision£Recall
P recision+Recall
Automatic annotation was also performed using the subsumption relations found by BOAT (as described in 4) as well as those found using Hearst patterns. We were not able to compare with CSR as the tool is not publicly available. After manually validating all the Hearst patterns in the two corpora, we were able to find only 3 subsumption relations for GRO-UMLS and 14 for GENIA-UMLS.
Table 3 shows the performance of automatic ontology annotation using subsumption relations from the three techniques. Though the annotations made using BOAT’s inferred relations have the highest recall for the GRO Corpus, it is achieved at the cost of precision. Similarly, the high precision of the Hearst method on the GENIA Corpus is achieved at the expense of recall. SURD has the highest precision for the GRO Corpus, the highest recall for the GENIA Corpus, and the highest F-measures for both corpora. The last row of Table 3 shows the average distance between reference annotation CG0RO and its closest match CGRO identified using automatic annotation, for all CG0ROs that have matches. An average distance close to 0 means that the automatic annotations are mostly identical to the manual annotations, while a large average distance means that mentions are often matched to more general concepts than those of manual annotations. SURD has very small average distances for both corpora. This shows that in addition to having higher coverage, automatic annotations using SURD are almost identical to the manual annotations.
GRO UMLS GENIA UMLS
SURD BOAT Hearst SURD BOAT Hearst Precision 0.866 0.491 0.8 0.839 0.843 0.896
Recall 0.577 0.664 0.001 0.735 0.539 0.050 F-Measure 0.693 0.565 0.002 0.783 0.658 0.096 Avg. Dist 0.038 1.4 0 0 3.1 1.0
Table 3. Automatic ontological corpus annotation results
We have presented a novel technique for discovering cross-ontology subsumption relations which uses ontological annotations on biomedical text corpora to determine subsumption relations between concepts that share mentions. The relations discovered are highly precise and have wide coverage and can thus be used for integrating a pair of ontologies with minimal expert curation. We also showed that they can be effectively used for automated cross-ontology annotations on biomedical corpora. For future work, we plan to apply SURD to other biomedical ontologies and also complement the equivalence relations found by BOAT with the subsumption relations found by SURD for the integration of ontologies populated with annotations so as to effectively perform semantic querying on biomedical literature.
The authors would like to thank Xu Han for helping to validate the subsumption relations.