Unsupervised Learning of Semantic Relations between Concepts of a Molecular Biology Ontology

1 Introduction

Bioinformatics is one of the most active fields for text mining applications because of the fast rate of growth of digital documents collections such as Medline and SwissProt. The ultimate goal of text mining in bioinformatics is knowledge discovery by means of natural language processing (NLP) and machine learning. To achieve this objective it is necessary to access the information contained "inside" the documents, i.e. their content. One possible strategy to get to the content is through information extraction. One starts with a conceptualization of the domain; i.e., a domain ontology, which specifies relevant concepts as well as semantic relations, such as is-a, part-of, and more complex relations encoding important interactions between concepts. Then it is necessary to apply extraction techniques to recognize where, in the documents, concepts are instantiated by specific entities, and where important interactions are expressed by linguistic structures.

Several ontologies which define concepts and structural semantic relations, e.g., is-a, are available. Instead there is a need for ontologies that specify relevant arbitrary semantic relations between concepts; for example, that "Cell expressthe-receptor-for Protein" or that "Virus replicate-in Cell". In this paper we investigate the problem of enriching an existing ontology with arbitrary semantic relations which are strongly associated with ordered pairs of concepts. We design an unsupervised system that combines an array of off-the-shelf NLP techniques such as syntactic parsing, collocation extraction and selectional restriction learning. We apply our system to a corpus of molecular biology literature, the GENIA corpus [Ohta et al., 2002], and generate a list of labeled binary relations between pairs of GENIA ontology concepts. An indepth analysis of the learned templates shows that the model, characterized by a very simple architecture, has good potentials for text mining and ontology building applications.

∗We would like to thank our colleagues in the Laboratory for Applied Ontology (LOA-CNR), and the Klaus Tschira Foundation for their financial support.

In the next section we describe the problem of learning relations from text and related work. In Section 3 we describe our system and the data used in our study in detail. In Section 4 we discuss the evaluation of the system's output.

2 Problem statement and related work

The GENIA ontology contains concepts related to gene expression and its regulation, including cell signaling reactions, proteins, DNA, and RNA. Much work in bioinformatics has focused on named-entity recognition (NER), or information extraction (IE), where the task is the identification of sequences of words that are instances of a set of concepts. As an example one would like to recognize that "NS-Meg cells", "mRNA" and "EPO receptor" are, respectively, instances of the GENIA classes "Cell line", "RNA family or group" and "Protein molecule" in the following text (Example 1):

A natural extension of NER is the extraction of relations between entities. NER and relation extraction could provide a better support for mining systems; e.g., patterns of entities and relations could be compared across document collections to discover new informative pieces of information (as in [Swanson and Smalheiser, 1997] for example). Currently most of the work on relation extraction applies hand-built rule-based extraction patterns; e.g., Friedman et al. [2001] on identifying molecular pathways and ˇSari´c et al. [2004b] on finding information on protein interactions which use a manually-built ontology similar to that described in [Ratsch et al., 2003]. One problem with rule-based IE is that systems tend to have good precision but low recall. Machine learning oriented work has focused on extracting manuallycompiled lists of target relations; e.g., Rosario and Hearst [2004] address the relation extraction problem as an extension of NER and use sequence learning methods to recognize instances of a set of 6 predefined relations about "Diseases" and "Treatments". These systems yield good precision and recall but still need that sets of relations between classes be defined first. Yet another problem which deals with semantic relations is that addressed by Craven and Kumlien [1999] who present a model for finding extraction patterns for 5 binary relations involving proteins. A similar work is that of Pustejovsky et al. [Pustejovsky et al., 2002] on automatically extracting "inhibit" relations. Semantic relations have been used as templates, or guiding principles, for the generation of database schemata [Rojas et al., 2002]. Another application of ontological relations is that of consistency checking of data in molecular biology databases to individuate errors in the knowledge base (e.g., by checking the consistency of the arguments) or to align different databases.

Biological text mining systems that involve relations require predefined sets of relations that have to be manually encoded, a job which is complex, expensive and tedious, and that as such can only guarantee narrow coverage - typically a handful of relations and one pair of classes. Our aim is to automatically generate all relevant relations found in a corpus between all ontological concepts defined in an ontology. This work is also valuable to ontologists since ontology building and evaluation are becoming more and more automatized activities and most of the corpus-based work has focused only on structural relations such as is-a and part-of [Pantel and Ravichandran, 2004; Berland and Charniak, 1999].

3 Learning relations from text

Our model takes as input a corpus of texts in which namedentities, corresponding to ontology concepts, have been identified. Here we use the GENIA corpus, for which the tagging has been carried out manually, but the corpus data can be also generated automatically using an appropriate NER system. The model outputs a set of templates that involve pairs of GENIA ontology classes and a semantic relation. For example, a template might be "Virus infect Cell".

3.1 Data

The GENIA ontology was built to model cell-signaling reactions in humans with the goal of supporting information extraction systems. It consists of a taxonomy of 46 nominal concepts with underspecified taxonomic relations, see Figure 1. The ontology was used to semantically annotate biological entities in the GENIA corpus. We used the G3.02 version consisting of 2,000 articles, 18,546 sentences, roughly half a million word tokens, and 36 types of labels. This corpus has complex annotations for disjunctive/conjunctive entities, for cases such as "erythroid, myeloid and lymphoid cell types". We excluded sentences that contained only instances of complex embedded conjunctions/disjunctions and also excessively long sentences (more than 100 words). The final number of sentences was 18,333 (484,005 word tokens, 91,387 tags). Many tags have nested structures; e.g. "[Other name [DNA IL-2 gene] expression]". Here we only considered the innermost labels, although the external labels contain useful information and should eventually be used.

One potential drawback of the GENIA ontology is the relatively small number of biological concepts and their coarse granularity which causes groups of similar but distinct entities to be assigned to the same class. Some relations fit very well to subsets of the entities of the related concepts, whereas they don't fit well for other entities of the same concept. For example, the concept "DNA domain or region" contains sequences with given start and end positions, as well as promoters, genes, enhancers, and the like. Even if promoters, genes, and enhancers are pieces of sequences too (with start and end positions), they also are functional descriptions of sequences. Therefore, different statements can be made about such kinds of DNA domains or regions and (pure) sequences. The relation "DNA domain or region encodes Protein molecule" makes sense for genes, but not for enhancers, and may make sense or not for (pure) sequences, depending on their (unknown) function. On the other hand any NLP oriented resource cannot have many fine-grained concepts defined, otherwise IE wouldn't be accurate. In this respect the GENIA corpus is unique in that it provides extensive namedentity annotations which can be used to train appropriate NER systems (cf. [Kazama et al., 2002].

3.2 Relations as dependency paths

The 18,333 sentences were parsed with a statistical parser [Charniak, 2000]. 1 Since we are interested in relations that connect entities as chunks we want to avoid that the parser analyzes an entity that is split among different phrases. This can happen because entity names can be fairly long, complex and contain words that are unknown to the parser. To avoid this problemwe substituted the entity tags for the actual named-entities; the result can be seen in Figure 2 which shows the substitution and the relative parse tree for the sentence of Example 1. Trees obtained in this way are simpler and don't split entities across phrases. For each tree we generated a dependency graph: each word 2 is associated with one governor, defined as the syntactic head 3 of the phrase closest to the word that differs from the word itself. For example, in Figure 2 "Cell line" is governed by "express", while "Protein molecule" is governed by the preposition "for".

1 Which takes roughly three hours on a Pentium 4 machine.

2 Morphologically simplified with the "morph" function from the WordNet library, plus morphological simplifications fromUMLS.

3 The word whose syntactic category determines the syntactic category of the phrase; e.g., a verb for a verb phrase (VP), a noun for a noun phrase (NP), etc.

In this way it is possible to formalize the notion of semantic relation between two entities. A related application of dependency relations concerns the recognition of paraphrase sentences [Lin and Pantel, 2001]. A relation r between two entities ci and cj in a tree is the shortest path between ci and cj following the dependency relations. For example, in Figure 2 the path between "Cell line" and "Protein molecule" is "←express→for→". There is a path for every pair of entities in the tree. Paths can be considered from both directions since the reverse of a path from A to B is a path from B to A. A large number of different patterns can be extracted, overall we found 172,446 paths in the data. For the sake of interpretability, by inspection, of the outcome of the model in this paper we focused on a subset of these patterns. We selected paths from ci to cj where j > i and the pivotal element, the word with no incoming arrows, is a verb v. In addition we imposed the following constraints: ci is governed by v under an S phrase (i.e., is v's surface subject, SUBJ), e.g., "Cell line" in Figure 2; and one of the following six constraints holds:

1. cj is governed by v under a VP (i.e., is v's direct object, DIR OBJ), e.g., "RNA family or group" in Figure 2;
2. cj is governedby v under a PP (i.e., is v's indirect object, IND OBJ), e.g. "Protein molecule" in Figure 2;
3. cj is governed by v's direct object noun (i.e., is a modifier of the direct object, DIR OBJ MOD), e.g. "Virus" in "... influenced Virus replication";
4. cj is governed by v's indirect object noun (i.e., is the indirect object's modifier, IND OBJ MOD), e.g., "Protein molecule" in "..was induced by Protein molecule stimulation";
5. cj is governed by a PP which modifies the direct object (DIR OBJ MOD PP); e.g., "Protein molecule" in ".. induce overproduction of Protein molecule";
6. cj is governed by a PP which modifies the indirect object (IND OBJ MOD PP); e.g., "Lipid" in "..transcribed upon activation with Lipid".

For the sentence in Figure 2 we identify two good patterns: "SUBJ←express→DIR OBJ" between "Cell line" and "RNA family or group", and

"SUBJ←express→for→IND OBJ", between "Cell line" and "Protein molecule". Overall we found 7,189 instances of such relations distributed as follows:

The data contained 485 types of entity pairs, 3,573 types of patterns and 5,606 entity pair-pattern types.

3.3 Learning relations (Stage 1)

Let us take A to be an ordered pair of GENIA classes; e.g. A = (Protein domain,DNA domain or region), and B to be a pattern; e.g., B = SUBJ←bind→DIR OBJ. Our goal is to find relations strongly associated with ordered pairs of classes, i.e., bi-grams AB. This problem is similar to finding collocations; e.g., multi-word expressions such as "real estate", which form idiomatic phrases. Accordingly the simplest method would be to select the most frequent bi-grams. However many bigrams are frequent because either A or B, or both, are frequent; e.g., SUBJ←induce→DIR OBJ is among the most frequent pattern for 37 different pairs. Since high frequency can be accidental and, additionally, the method doesn't provide a natural way for distinguishing relevant from irrelevant bi-grams, we use instead a simple statistical method.

As with collocations a better approach is to estimate if A and B occur together more often than at chance. One formulates a null hypothesis H0 that A and B do not occur together more frequently than expected at chance. Using corpus statistics the probability of P(AB), under H0, is computed and H0 is rejected if P(AB) is beneath the significance level. We use a chi-square test for this purpose. For each observed bi-gram we create a contingency table of the frequencies AB, ¬AB, A¬B, and ¬A¬B; e.g., for A = Protein molecule-DNA domain or region and B = SUBJ←bind→DIR OBJ the table computed from the corpus would contain respectively the values 6, 161, 24 and 6,998. The chi-square test compares the observed frequencies vs. the frequencies expected under H0. Together with the test we use the log-likelihood chi-squared statistic: 4

where i and j range over the rows and columns of the contingency table, and the expected frequencies are computed off the marginal frequencies in the table. In the previous example G2 is equal to 16.43, which is above the critical value 7.88 for α = 0.005, hence B is accepted as a relevant pattern for A. The following table shows the three highest ranked class pairs for pattern B. There is strong evidence that entities of the protein type tend to bind DNA locations, which is a reasonable conclusion:

In this study we used α = 0.005. In general, α is an adjustable parameter which might be set on held-out data in order to maximize an objective function. We also ignored bi-grams occurring less than 2 times and pairs A, patterns B, occurring less than 4 times. Overall there are 487 suitable AB pairs, 287 (58.6%) have a value for G2 higher than α.

3.4 Generalization of relations (Stage 2)

Relations can share similar arguments as in "bind" above where, in both significant cases, the direct object is "DNA domain or region" while the subject is some kind of protein. This can be evidence that, in fact, we are facing a more general template holding between superordinates of the arguments found in the first stage. It is desirable, when possible, to learn more general relations such as "Protein SUBJ←bind→DIR OBJ DNA", because the learned ontology is more compact and has greater generalization power, i.e., relations apply to more entities. Finding such generalizations is similar to learning selectional restrictions of predicates, that is, the preferences that predicates place on the semantic category of their arguments; e.g., that "eat" prefers objects that are "foods". Several methods have been proposed for learning such restrictions. We use here the method proposed in [Clark and Weir, 2002] which is accurate and simple. We use the taxonomy defined in the GENIA ontology, see Figure 1, to generalize arguments of the learned patterns. 5

4 Dunning [1993] argues that G2 is more appropriate than Pearson's X2 with sparse data; here they produce similar rankings.

Clark and Weir define an algorithm, top(c, r, s), which (adjusting the terminology to our case) takes as input a relation r, a class c and a syntactic slot s, and returns a class c′ which is c itself or one of its ancestors, whichever provides the best generalization for p(r|c, s). The method uses the chi-squared test to check if the probability p(r|c, s) is significantly different from p(r|c′ , s), where c′ is the parent of c. If this is false then p(r|c′ , s) is supposed to provide a good approximation for p(r|c, s), which is interpreted as evidence that (r, s) holds for c′ as well. The procedure is iteratively applied until a significant difference is found. The last class considered is the output of the procedure, the concept that best summarizes the class that r "selects" in syntactic slot s. We computed the frequencies of patterns involving superordinate classes summing over the frequencies, from the GENIA corpus, of all descendants of that class for that pattern.

For each relation r, slot s and class c, learned in stage 1, we used Clark and Weir's method to map c to top(c, r, s). We again used the G2 statistic and the same α value of 0.005. Using these maps we generalized, when possible, the original 287 patterns learned. The outcome of this process is a set of 240 templates 153 of which have generalized arguments. As an example, the templates above "Protein domain binds DNA domain or region" and "Protein family or groupbinds DNA domain or region" are mapped to the generalized template "Protein binds DNA". Figure 3 depicts the set of labeled relations the concept Virus is involved in, and the respective paired concepts, after stage 1 and 2.

4 Evaluation

We discuss now an evaluation of the model carried out by a biologist and an ontologist, both familiar with GENIA. The biological evaluation focuses mainly on the precision of the system; namely, the percentage of all relations selected by the model that, according to the biologist, express correct biological interactions between the arguments of the relation. From the ontological perspective we analyze semantic aspects of the relations, mainly the consistency with the GENIA classes.

4.1 Biological evaluation

The output of stage 1 is a set of 287 patterns, composed of an ordered pair of classes and a semantic relation. 91 of these patterns, involving in one or both arguments the class "Other name", were impossible to evaluate and excluded altogether. This GENIA class is a placeholder, for very different sorts of things, which needs partitioning and structuring. Relations involving "Other name" (e.g., "treat") might prove correct for a subset of the entities tagged with this label (e.g., "inflammation") but false for a different subset (e.g., "gene expression"). Of the remaining 196 patterns 76.5% (150) are correct, i.e., express valid biological facts such as "Protein molecule induce-phosphorylation-of Protein molecule", while 23.5% (43) are incorrect, e.g. "Protein inhibit-expression-of Lipid". Evaluation involved the exhaustive inspection of the original sentences to verify the intended meaning of the pattern and spot recurring types of errors. Half of the mistakes (22) depend on how we handle coordination, which causes part of the coordinated structure to be included in the relation. For example, the first two DNA entities in the noun phrase "DNA, DNA, and DNA" are governed by the head DNA rather than by, say, the main verb. Thus wrong relations such as "Protein bind-DNA DNA" are generated in addition to good ones such as "Protein bind DNA". Fixing this problem involves simply the specification of a better dependency structure for coordinations. Finally, 5 errors involved the class "Other name" embedded somewhere within the relation, suggesting again generalizations that cannot be judged with enough confidence. The remaining errors are probably due to sparse data problems. In this respect we plan to implement an NER system to produce more data and consequently more reliable distributional information. Finally, we notice that, although the GENIA ontology was intended to be a model of cell signaling reactions, it lacks important concepts such as signaling pathway. This leads to some errors as in the following case: "An intact TCR signaling pathway is required for p95vav to function.". In this case we derive the relation: "Protein molecule is-requiredfor Protein molecule" since only "TCR" is annotated as "Protein molecule" neglecting signaling pathway.

5 Four of the 36 GENIA corpus class labels, namely, "DNA substructure", "DNA N/A", "RNA substructure" and "RNA N/A", have no entries in the GENIA ontology, we used them as subordinates of " DNA" and "RNA", consistently with "Protein N/A" and "Protein substructure" which in the ontology are subordinates of "Protein".

To the best of our knowledge we can compare these results with one other study. Reinberger et al. [2004] evaluate (also by means of experts) 165 subject-verb-object relations, extracted from data similar to ours 6 but with a different approach. They report an accuracy of 42% correct relations. Their method differs from ours in three respects: relations are extracted between nouns rather than entities (i.e., NER is not considered), a shallow parser is used instead of a full parser, and relations are selected by frequency rather than by hypothesis testing. A direct comparison of the methods is not feasible. However, if the difference in accuracy reflects the better quality of our method this is likely to depend on any, or on a combination, of those three factors.

As far as stage 2 is concerned we first removed all relations involving "Other name" (40 out of 153), which does not have superordinates nor subordinates, and evaluated if the remaining 113 generalized patterns were correct. Of these, 60 (53.1%) provided valid generalizations; e.g., "Protein molecule induce-phosphorylationof Amino acid monomer" is mapped to "Protein inducephosphorylation-of Amino acid monomer". Excluding mistakes caused by the fact that the original relation is incorrect, over-generalization is mainly due to the fact that the taxonomy of the GENIA ontology is not a is-a hierarchy; e.g., "DNA substructure" is not a kind of "DNA", and "Protein"

6 The SwissProt corpus, 13 million words of Medline abstracts related to genes and proteins.

is not a kind of "Amino acid". Generalizations such as selectional restrictions instead seem to hold mainly between classes that share a relation of inclusion. In order to support this kind of inference the structural relations between GENIA classes would need to be clarified.

4.2 Ontological assessment

The 150 patterns validated by the expert are potential new components of the ontology. We compiled GENIA, including the newly learned relations, in OWL (Ontology Web Language [McGuinness and van Harmelen, 2004]) to assess its properties with ontology engineering tools. Ignoring "Other name", the GENIA taxonomy branches from two root classes: "Source" and "Substance". GENIA classes, by design, tend to be mutually exclusive, meaning that they should be logically disjoint. Our main objective is to verify the degree to which the new relations adhere to this principle.

To analyze the relations we align, i.e., map, "Source" and "Substance" to equivalent classes of another more general ontology. Ideally, the alignment should involve an ontology of the same domain such as TAMBIS [Stevens et al., 2000]. Unfortunately TAMBIS scatters the subordinates of "Source" (organisms, cells, etc.) across different branches, while "Substance" in TAMBIS does not cover protein and nucleic acidrelated subordinates of "Substance" in GENIA. 7 In GENIA substances are classified according to their chemical features rather than biological role, while sources are biological locations where substances are found and their reactions take place. This distinction assumes a stacking of ontology layers within the physical domain where the biological is superimposed to the chemical level. This feature of GENIA makes it suitable for alignment with DOLCE-Lite-Plus (DLP, http://dolce.semanticweb.org), a simplified translation of the DOLCE foundational ontology [Gangemi et al., 2003]. DLP specify a suitable distinction between "chemical" and "biological" objects. It features about 200 classes, 150 relations and 500 axioms and has been used in various domains including biomedicine [Saric et al., 2004a].

We aligned "Source" and "Substance" to the biological and chemical classes in DLP. There are 78 types of relations out of 150, 58% of them (45) occur only with one pair of classes, i.e., are monosemous, while 33 have multiple domains or ranges, i.e., are polysemous. Since the root classes of GENIA are disjoint we checked if there are polysemous relations whose domain or range mix up subclasses of "Source" with subclasses of "Substance". Such relations might not imply logical inconsistency but raise doubts because they suggest the possibility that a class of entities emerged from the data, which is the union of two classes that by definition should be disjoint. Interestingly, there are only 4 such relations out of 78 (5.1%); e.g., "encode", whose subject can be either "Virus" or "DNA". In biology, DNA encodes a protein, but biologists sometimes use the verb "metonymically". By saying that a virus encodes a protein, they actually mean that a virus' genome contains DNA that encodes a protein. The small number of such cases suggests that relations emerging from corpus data are consistent with the most general classes defined in GENIA.

7 Notice that we are not questioning the quality of TAMBIS, but only its fitness for aligning GENIA.

At a finer semantic level relations are composed as follows: 54 (68%) are eventive, they encode a conceptualization of chemical reactions as events taking place in biological sources; 81% of the relations between biological and chemical classes are eventive, supporting the claim made in GENIA that biologically relevant chemical reactions involve both a biological and chemical object. Non-eventive relations have either a structural (e.g. "Consist-of"), locative ("Locatedin"), or epistemological meaning ("identified-as").

5 Conclusion and future work

We presented a study on learning semantic relations from text in the domain of molecular biology. We investigated an unsupervised approach using the GENIA ontology and its corpus. Our model is based on a representation of relations as syntactic dependency paths between an ordered pair of namedentities. To select "good" relations, class pairs and dependency paths can be interpreted as bi-grams, and scored with statistical measures of correlation. We showed that it is also possible to generalize over the arguments of the relation using a taxonomy and algorithms for selectional restrictions learning. The results of a biological and ontological analysis of the acquired relations are positive and promising.

Other aspects need to be addressed beyond precision, in particular we are interested in evaluating the recall, i.e., the coverage, of the system, 8 the precision of alternative selection criteria, and the usefulness of automatically learned relations in information extraction tasks. The latter will imply the identification of synonymic relations; e.g., in the context of Protein-Protein interaction "positively-regulate" is equivalent to "activate", "up-regulate", "derepress", "stimulate" etc. Representing relations as dependency paths one can frame this problem straightforwardly as that of finding paraphrases (e.g. as in [Lin and Pantel, 2001]).