NON-LEXICAL APPROACHES TO IDENTIFYING ASSOCIATIVE RELATIONS IN THE GENE ONTOLOGY

3.1. Similarity in the vector space model

Vector space models (VSMs) are frequently used in information retrieval for computing the similarity between documents described as vectors of keywords ⁷. A collection of gene products annotated with the controlled vocabulary provided by GO is in fact analogous to a collection of scientific articles indexed with the MeSH controlled vocabulary. Although the primary use of a collection of indexing terms for documents (or annotation terms for gene products) is to compute the similarity among documents (or gene products), our interest here is to compute the similarity among terms. Therefore, we have to transpose the matrix of gene products by GO terms in order to obtain a matrix of GO terms by gene products. As usual in the VSM paradigm, the similarity between two vectors is represented by the angle between these vectors, measured by the dot product of the two (normalized) vectors.

As illustrated in Figure 1, the original matrix (gene products by GO terms) consists of binary values indicating the presence (1) or absence (0) of an association between a gene product and a GO term in a given annotation database. One such matrix is created for each model organism. The matrix is then transposed. Not represented in the figure is the weighting step. A weight is applied to each binary association in order to lower the importance of an association between a GO term and a gene product when a given gene product is associated with many GO terms^§. This weighting scheme, shown in Eq. (1), is known as inverse document frequency (idf) in information retrieval. Here, the weight of each association between a GO term and gene product j is inversely proportional to the ratio of the number of annotations for this gene product (n_j) to the total number of distinct gene products in the corresponding annotation database (N). Then, each vector is normalized in order to compensate for differences in the number of genes associated with GO terms. Once the vectors are normalized, their dot product varies between 0 and 1 and measures the similarity between them (see Figure 1). A value of 0 corresponds to no similarity, while 1 indicates complete similarity. Term-term similarity is computed pairwise for all GO terms present, resulting in a half-matrix for each model organism database. We use an arbitrary threshold of .5 for the dot product in order to select the pairs of terms exhibiting a high drgree of similarity.

3.2. Co-occurrence in annotation databases

In probability theory, two events E₁ and E₂ are independent when the probability of occurrence of the two events simultaneously, P(E₁ ∩ E₂), is not greater than the product of the probabilities of occurrence for each event, P(E₁) . P(E₂). Conversely, when P(E₁ ∩ E₂) > P(E₁) . P(E₂), E₁ and E₂ are not independent. What we are interested in identifying here are pairs of “non-independent” GO terms, whose frequency of co-occurrence (i.e., simultaneous presence in the annotation of a gene product) is higher than would be expected if the two terms had been used independently by the curators. For a given pair of GO terms (A,B), information about their association in gene product annotations can be summarized in a two-way contingency table and analyzed statistically ⁸:

• n_AB, the number of gene products annotated with both term A and term B

• n_Ab, the number of gene products annotated with term A but not term B

• n_aB, the number of gene products annotated with term B but not term A

• n_ab, the number of gene products annotated with neither term A or term B

The chi-square test of independence (or Pearson’s chi-square) is often used to test independence between two categorical variables (here, the presence or absence of a given term in the annotations of genes). The chi-square (χ²) statistic relies on the difference between observed frequencies (n_ij) for the four events listed above and the frequencies expected under the hypothesis of independence. The χ² statistic has a chi-square distribution, specified by its degrees of freedom. There is one degree of freedom in the case of two-way contingency tables for binary variables. A large value of the χ² statistic indicates a deviation from the expected frequencies. In this case, i.e., when the corresponding P-value is lower than the usual .05 threshold, the hypothesis of statistical independence is rejected and the association is considered statistically significant. One limitation of the chi-square test is that all expected frequencies are required to be 5 or more. In practice, this condition cannot be met if the frequency of the terms is small.

An alternative to the Pearson’s chi-square test is the likelihood ratio test (also called G-test or G-square test). The G² statistic compares the maximum of the likelihood function under two circumstances: 1) under the hypothesis of independence and 2) under the general, observed conditions. Like the χ² statistic, the G² statistic has a chi-square distribution (also with one degree of freedom in our setting). Interestingly, the G² statistic does not have the minimum expected frequency requirements imposed by the χ². However, for the G² statistic to be computed, all observed frequencies must be greater than 0.

In practice, for each pair of terms, we first attempt to compute a G² statistic. A χ² statistic is used instead when the requirements are not met for G². Finally, the association is ignored if it fails to meet both G² and χ² requirements. Because of the low frequency of co-occurrence of the terms in this case, identifying their association is of little interest anyway.

While both χ² and G² indicate the existence of an association between two variables, neither one describes the strength of the association. Several similarity coefficients have been developed for this purpose ⁹, which could be used to select the pairs of terms exhibiting a strong association. In this study, however, we simply included all pairs of terms for which the test indicated a statistically significant association, regardless of the strength of the association.

3.3. Association rule mining

Association rules capture the association between two sets of events of arbitrary size and are expressed in the form: A ⇒ B, where B is the set of events that can be predicted from A ¹⁰. Historically, the identification of association rules was applied to analyzing grocery buying patterns, with rules such as {bread, milk} ⇒ {sugar} expressing that customers buying bread and milk also often buy sugar. By applying association rule mining techniques to annotation databases, we expect to discover that genes annotated with the GO term T₁ are also frequently annotated with T₂. The set of GO terms annotating a gene product is called a transaction in association rule mining parlance.

We used Christian Borgelt’s implementation of the apriori algorithm^** to mine association rules. Since our objective is to identify pairs of related GO terms, we restricted the size of the sets under investigation to two. The two major parameters in the algorithm are support and confidence. Support for the rule T₁ ⇒ T₂ represents the proportion of genes annotated with both T₁ and T₂. Confidence for the same rule represents the proportion of genes annotated with both T₁ and T₂ among those annotated with T₁. In order to restrict rules to almost systematic associations, we required confidence to be at least 90%. The minimum support was set to a low value (.05%) simply to eliminate “accidental” associations. We use the product of support by confidence to describe the strength of the association.

3.4. Evaluation

The first step of the evaluation consists in comparing the results of the three approaches. Associations identified independently by several approaches simultaneously are expected to be stronger and therefore more important. Finally, the presence of the association in the annotation databases of several organisms suggests that this association is stronger than isolated associations. What is evaluated here is essentially the statistical significance of the associations. Evaluating the ontological and biological significance of these associations is beyond the scope of this study.

Additionally, we compared the results of our three approaches to lexical associations and to associations present in the UMLS Metathesaurus.

4.1. Associations identified

Examples of association identified specifically by each method are presented in Table 3. The first three are the methods under investigation: VSM (vector space model), COC (co-occurrence in annotation databases), and ARM (association rule mining). The others are the methods used in the evaluation: LEX (lexical relations), REL (associative relations in UMLS), and MDL (co-occurrence in MEDLINE). Quantitative results are presented in Table 4 where the number of associations identified by each method is broken down by category of association.

4.2. Overlap

A total of 13,398 associations were identified by at least one method, 7,665 by at least one of the three major methods (VSM, COC, and ARM) and 5,963 by at least one of the evaluation methods (LEX, REL, and MDL). Of these, only 230 associations were identified by both major and evaluation methods. Examples of associations identified independently but simultaneously by several methods are presented in Table 5. As illustrated in Figure 2, 12% of the associations identified by the three major methods were identified by more than one method. In contrast, only a few lexical associations are also present in the UMLS.

Out of the 7,665 associations identified by at least one method, 5,950 (78%) came from only one annotation database. In 1,116 cases (16%), the association was simultaneously identified in two annotation databases, 6% in three, and 2% in two. Only 41 associations (less than 1%) were present in all five databases. Pairwise, after normalizing by the number of annotations in each database, the highest rates of overlap are between MGD and GOA-Human and MGD and WormBase, the lowest between SGD and GOA-Human and SGD and MGD.

Applications

The major application of our methods is of course to help enrich GO with associative relations across ontologies. Ontology creation and extension is a daunting task. However, by automatically extracting candidate relations from annotation databases, the approaches investigated in this study can significantly reduce the human effort required. We recommend that the associations identified in this study serve as the starting point for adding associative relations across hierarchies to GO. The associations we identified could also be used for quality assurance purposes, i.e., to assess the consistency and completeness of annotation databases. Analogously, knowledge of frequently associated terms could be presented to curators in annotation environments.

Advantages and limitations

Many associations identified by our approaches cannot be found by lexical methods. The performance of lexical methods could be improved by factoring in term variation (inflection, derivation) and using more rigorous parsing of the terms; it would, however, remain poor due to the limited number of synonyms available in GO for each term. By imposing constraints such as minimum frequency and statistical significance of co-occurrence and minimum confidence for association rules, our approaches are more selective than the unrestricted methods used in GOAT. Limitations – not specific to our approaches – include the fact that what is identified is the presence of associations between GO terms, not their nature. Moreover, the manual curation of the associations identified remains necessary in order to assess their biological significance.

Evaluation

The limited overlap between associations identified by our major methods and the evaluation methods was somewhat unexpected. The lexical relation between, for example, transport and transport vesicle is ontologically valid but never present in annotations. Although the biomedical literature plays a role in both approaches, the limited overlap between annotation databases and MEDLINE co-occurrences may have the following explanations. Many annotations are derived from sources other than the literature (e.g., inferred from sequence or structural similarity) and MEDLINE co-occurrences are not guaranteed to relate to the same gene when several genes are discussed in an article.

Generalization

As shown in earlier studies ^{4, 5}, dependence relations can be found both within and across the three GO ontologies. Although this study is purposely restricted to the identification of associative relations across GO ontologies, our methods actually identified almost as many dependence relations within ontologies (not reported on here). The lexical method captures five times as many associations within ontologies than across, including a majority of direct parent-child associations. Because curators are unlikely to use both a parent term and its child in the annotation of a gene, the associations within ontologies captured by our methods are essentially between distinct subtrees of GO hierarchies (e.g., between metallopeptidase activity [catalytic activity subtree] and zinc ion binding [binding subtree]). Finally, our approaches could be applied to other domains (e.g., for identifying relations among terms of a clinical terminology using clinical databases indexed with this terminology).

Future directions

Many interesting aspects of the association between GO terms are beyond the scope of this paper. Those issues, which we expect to address in the near future, include the redundancy of associations across species and applications to the functional interpretation of experimental results.