Annotating protein function through lexical analysis

Rajesh Nair ^{1,4, *} & Burkhard Rost ^{1, 2, 3, *}

This article is published in (AI Magazine, issue, 2003 and pages) © copyright American Association for Artificial Intelligence (AAAI) Press (2003). AAAI Press is the only authorised source. All copying of this article including placing on another website requires the written permission of the copyright owner.

Abstract

We now know the entire genomes for over 100 organisms. The experimental characterisation of the newly sequenced proteins is deemed to lack behind this explosion of raw sequences (sequence-function gap). The rate at which expert annotators add experimental information into more or less controlled vocabularies of databases snails along at even slower pace. Most methods that annotate protein function exploit sequence similarity by transferring experimental information for homologues. A crucial development aiding such homology-based information transfer are large-scale, work- and management-intensive projects venturing to develop a comprehensive ontology for protein function, like the Gene Ontology project. In parallel, fully- or semi-automatic methods have successfully begun to mine the existing data through lexical analysis. Some of these tools target parsing controlled vocabularies from databases; others dare mining free texts from MEDLINE abstracts or full scientific papers. Automated text analysis has become a rapidly expanding discipline in bioinformatics. A few of these text-based tools have already been embedded into research projects.

Key words: text mining, protein function, sub-cellular localization, text analysis, MEDLINE abstracts.

Abbreviations used

Introduction

Proteins are the machinery of life. The information for life is stored in a four-letter alphabet in the genome (DNA) [1, 2] . This four-letter DNA alphabet is translated first into another four-letter alphabet of biochemically less stable RNA nucleotides and from these into a 20-letter amino acid alphabet constituting the basic language for proteins, the machinery of life. Proteins are assembled by joining amino acids through peptide bonds; they differ greatly in the number of amino acids joined (from 30 to over 30,000) and in the arrangement and types of amino acids used (dubbed residues, when joined in proteins). The complete set of all proteins in one particular organism is referred to as its proteome. Proteins are the macromolecules that perform most important tasks in organisms ˆ, such as catalysis of biochemical reactions, transport of nutrients, recognition and transmission of signals. The plethora of aspects of the role of any particular protein is referred to as its 'function'. Although this is an intuitive statement, protein function is not a well-defined term. Instead, function is a complex phenomenon that is associated with many mutually overlapping levels: chemical, biochemical, cellular, organism mediated, developmental, and physiological. These levels are related in complex ways, for example, protein kinases can be related to different cellular functions (such as cell cycle), and to a chemical function (transferase) plus a complex control mechanism by interaction with other proteins; the same kinase may also be the culprit that leads to mis-function, or disease. Thus, identifying protein function is a step toward understanding diseases and toward identifying drug targets.

Gap between protein sequences and function. The first entire genome (DNA) sequence of a free living organism, Haemophilus influenzae, was published in 1995 [3] . Currently, we know the full genomes for over 100 organisms; for over 60 of these the data is publicly available and contributes about 250K protein sequences, i.e. about one fourth of all currently known protein sequences [4, 5, 6, 7] . The number of entirely sequenced genomes is expected to continue growing exponentially for at least the next few years. This explosion of sequence information has widened the gap between the number of protein sequences deposited in public databases and the experimental characterisation of the corresponding proteins [8, 9, 10, 11] . Bioinformatics plays a central role in bridging the sequence-function gap through the development of tools for faster and more effective prediction of protein function [12, 13, 14, 15, 16, 17] .

Here, we briefly review a few attempts at annotating function through homology transfer and automatic text analysis. The most widely used methods that allow guessing protein function rely on the ability to correctly mine the information deposited in public databases and in scientific journals. While we continue to need a more comprehensive ontology for protein function, developers have begun to successfully explore the marvels of an ever-increasing body of research in biology and medicine. There are two major types of methods attempting automatic lexical analysis: (1) parsing of controlled vocabulary from databases, and (2) mining unstructured text as available from scientific publications. We could not cover all the promising approaches that have mushroomed over the last 5-10 years. Therefore, we focus in detail on a few success-stories.

Annotations and annotation transfer of protein function

Molecular biology databases with functional information. Information about proteins is stored in public databases like SWISS-PROT and TrEMBL ( Table 1 ). SWISS-PROT [18, 19] is an expert-curated database that also contains annotations about function ( Fig. 1 ). These annotations are added by a team of expert annotators who extract this information primarily from journal publications [20] . TrEMBL [18] consists of entries that are derived from the translation of all coding sequences in the EMBL nucleotide sequence database that are not in SWISS-PROT. Unlike SWISS-PROT records, those in TrEMBL are awaiting manual annotation. SWISS-PROT currently contains 'only' 122,564 (release 41) sequence entries while the TrEMBL database contains over 821,014 (release 72) sequence entries [21] .

Fig. 1. : Protein entry in SWISS-PROT. The SWISS-PROT identifier for the protein MYOD_HUMAN is found under the header ÔIDÕ. The type of protein and its source organism are found under the ÔDEÕ and ÔOSÕ headers respectively. Detailed functional information regarding the protein is found under the header ÔCCÕ. This information is written in plain English and is not suitable for computer analysis. Following the ÔKWÕ header are keywords describing the function of the protein. The keywords use a restricted vocabulary and are ideal for tools designed for text analysis. Sequence information is found at the very end following the ÔSQÕ header.

Annotations of function mostly through homology transfer. Experimentally determining protein function continues to be a laborious task that may take enormous resources, for example, more than a decade after the discovery, we still do not know the precise and entire functional role of the prion protein [22] . The automatic elucidation of protein function is therefore an appealing challenge [23, 24, 25] . The bioinformatics means to struggle toward this end typically explore the fact that two proteins with similar sequence often have similar function. The basic idea to exploit this fact involves the following steps: (1) extract the experimental information from the literature into a controlled vocabulary of annotated databases. (2) Establish thresholds T for pairwise sequence similarity that imply similarity in function. (3) For a protein U of unknown function: search the database for proteins {K} that have a sequence similarity to U: SIM(K,U) > T. (4) Finally, if any such protein K is found, transfer its annotation to U. Albeit this concept appears straightforward, in practice, there are many hurdles to overcome: (i) it is very difficult to create controlled vocabularies [26, 18] , and (ii) one single number may not capture all the functional roles [26, 27] . (iii) To add to the complication, it seems that the precise values for thresholds of significant sequence similarity (T) are actually specific to particular function, i.e. become T(F), and have to be re-established for any given task [28, 29, 30, 31, 32, 27, 33, 34, 35, 36] . In general, the inference of function is reliable only for very high levels of sequence similarity [37, 33, 34] . For example, to reliably (>90% accuracy) infer the sub-cellular localization by homology transfer over 80% pairwise sequence identity is required. Below this threshold the accuracy of annotation transfer rapidly decreases [33] . Several pitfalls in transferring annotations of function have been reported, e.g. inadequate knowledge of thresholds for 'significant sequence similarity', using only the best database hit, or ignoring the domain organisation of proteins [38, 39, 40, 37] . Despite all these problems: the majority of annotations about function in public databases result from homology transfer [10, 37, 15] . Few databases provide unambiguous pointers for the origin of the information. One problem arising from this is that it may be difficult to distinguish speculations from experimentally supported annotations.

Problem 1: Multiple levels of description. The function of a protein depends on the context. Database annotations of protein function are often confusing due to the variety of functional roles [41] . We need computer-readable hierarchical descriptions of function [42, 12] . Several groups and associations have ventured to introduce numerical schemata to define function. The first attempt was the introduction of Enzyme Classification numbers (EC, [43] ); this classification uses four digits to classify enzymatic activity. The first EC digit distinguishes the general types of enzymes; the second EC digit specifies the substrate (oxireductases), the group transferred (transferases), the type of bond (hydrolases, lyases, ligases), or the type of reorganisation (isomerases). The third and fourth digits provide more detail (for an excellent survey of structural aspects of enzymatic function see Todd, Orengo & Thornton [27] ). MIPS attempts to extend this idea to a wider perspective of more proteins and more roles through their classification catalogue [44] . Arguably, the most impressive Gargantuan effort at defining an ontology for protein function originates from the Gene Ontology (GO) consortium [26] . GO distinguishes three levels of protein function. (1) Molecular function: at the molecular level, the protein can, for example, catalyse a metabolic reaction, recognize or transmit a signal. (2) Biological process: a set of many co-operating proteins is responsible for achieving broad biological goals, for example, mitosis or purine metabolism, or signal transduction cascades (3) Cellular component: this category includes the structure of sub-cellular compartments, the localization of proteins, and macromolecular complexes. Examples include nucleus, telomere, and origin recognition complex. The sub-cellular localization of a protein is an essential attribute for this level. The totality of the physiological sub-systems and their interplay with various environmental stimuli determines properties of the phenotype, the morphology and physiology of the organism and its behaviour. GO is not complete. Nevertheless, GO constitutes the best set of definitions available today.

Problem 2: Functional information not machine-readable. Nearly all databases present the protein sequence in formats that are more or less straightforward to parse by computers. However, annotations are mostly written in plain text using a rich biological vocabulary that often varies in different areas of research ( Fig. 1 >

Automatic lexical analysis of controlled vocabularies

From details to summaries. Protein databases, like SWISS-PROT, usually contain functional annotations at a very detailed level of biochemical function, e.g. a given sequence is annotated as a cdc2 kinase, but not as being involved in intra-cellular communication [47, 19] . A number of text analysis tools have been implemented that infer various aspects of cellular function from database annotations of molecular function. Many methods explore the functional annotations in SWISS-PROT, especially the keyword annotations [47, 45, 13, 48] . SWISS-PROT currently contains over 800 keywords describing function. Semantic analysis of the keywords is used to categorise proteins into classes of cellular function [49, 50, 51, 52, 53, 54] . There are two types of methods: (1) fully-automated and (2) semi-automated methods.

(1) Fully-automated methods. The problem of automatically extracting rules from keywords has parallels to the problem of 'Text Categorization' (TC), i.e. the problem of assigning predefined categories to free text documents. Many statistical learning methods have been applied to this problem. These include, nearest neighbour classifiers [55] , multivariate regression models [56, 57] , probabilistic Bayesian models [58] , symbolic rule learning [59] , M-ary (multiple category) classifiers like the k-Nearest Neighbour [60] and the Linear Least-squares Fit (LLSF) have been intensively studied and are among the most accurate for text categorisation [61] . The majority of the tools for annotating function are based on one of the above methods. Some of the major methods in this category are LOCkey [48] , Spearmint [62, 63] and the SVM-based approach of Stapley et al. [64] ( Table 2 ).

(2) Semi-automated methods. These methods are based on building dictionaries of rules. Keywords characteristic of each of the functional classes are first extracted from a set of classified example proteins. Using these keywords a library of rules is created associating a certain pattern of occurrence of keywords to a functional class. The major methods in this category are EUCLID [47] , Meta_A [45] and RuleBase [13] . Below we review the LOCkey and EUCLID systems as examples of the two main approaches.

LOCkey: information theory based classifier. The LOCkey system [48] is a novel M-ary classifier which predicts the sub-cellular localization of a protein based on SWISS-PROT keywords. The algorithm can be divided into two steps ( Fig. 2 ): (1) Building data sets of trusted vectors for known proteins, and (2) classifying unknown proteins. Firstly, a list of keywords is extracted from SWISS-PROT for all proteins with known sub-cellular localization. Most proteins have 2-5 keywords, on average. A data set of binary vectors [65] is generated for each protein by representing the presence of a certain keyword in the protein by 1 and absence by 0. Secondly, to infer sub-cellular localization of an unknown protein U all keywords for U are read from SWISS-PROT. These keywords are translated into a binary keyword vector. From this original keyword vector, LOCkey generates a set of all possible combinations of alternative vectors by flipping vector components of value 1 (presence of keyword) to 0 in all possible combinations. For example, for a protein with three keywords, there are 2³-1 = 7 possible sub-vectors: 111, 110, 101, 011, 100, 010 and 001. These sub-vectors constitute all possible keyword combinations for protein U. The keyword combination, i.e. sub-vector, that yields the best classification of U into one of ten classes of sub-cellular localizations is found. This is done by retrieving all exact matches of each of the sub-vectors to any of the proteins in the trusted set, i.e. by finding all proteins in the trusted set that contain all the keywords present in the sub-vector. By construction, the proteins retrieved in this way may also contain keywords not found in U. The next task is to estimate the 'surprise value' of the given assignment. Toward this end, LOCkey simply compiles the number of proteins belonging to each type of sub-cellular localization. This procedure is repeated in turn for each of the sub-vectors and localization is finally assigned to a protein by minimising an entropy-based objective function. The system accurately solves the classification problem when the number of data points (proteins) and dimensionality of the feature space (number of keywords) are not too large. LOCkey reached a level of more than 82% accuracy in a full cross-validation test. However, due to a lack of functional annotations, the system failed to infer localization for more than half of all proteins in the test set. For five entirely sequenced proteomes, namely Saccharomyces cerevisiae (yeast), Caenorhabditis elegans (worm), Drosophila melanogaster (fly), Arabidopsis thaliana (plant) and a subset of all human proteins, the LOCkey system automatically found about 8000 new annotations about sub-cellular localization. LOCkey has been optimised to provide fast annotations. For example, annotating the entire C. elegans proteome took less than four hours on a PIII 900 MHz machine. The algorithm is limited to problems with relatively few data points (proteins) in the vector set (n<<1000000) and with few keywords (n<<10000).

Fig. 2. : The LOCkey algorithm. A sequence unique data set of localization annotated SWISS-PROT proteins was first compiled. Keywords were extracted for these proteins and merged with any keywords found in homologues. The keywords were represented as binary vectors in the 'Trusted Vector Set'. An unknown query was first annotated with keywords through identification of SWISS-PROT homologues. Keywords for the query were represented as binary vectors. All possible keyword combinations were constructed (the SUB vectors). The best matching vector was found based on entropy criteria (see methods). This vector was used to infer localization for the query.

EUCLID: dictionary-based classification. The EUCLID system [47] uses SWISS-PROT keywords to classify proteins into 14 classes of cellular function according to the scheme originally proposed by Monika Riley [66, 67, 52, 54] . The 14 classes are the grouped into three broad functional classes (energy, information and communication). First, keywords characteristic of each of the functional classes is extracted from a set of classified example proteins provided by a human expert. This dictionary of characteristic keywords satisfies the following criteria: (1) Only keywords with functional meaning are used; keywords with no functional information are excluded (e.g. hypothetical or 3D-structure). (2) Only keywords appearing in more than one SWISS-PROT entry are considered. (3) Only keywords with more than 85% of their occurrences in a single functional category are included in the dictionaries. For assigning sequences to classes a simple voting scheme is used. A sequence is automatically classified in the functional class to which the majority of its keywords belong. The dictionary of keywords is then used to automatically assign all proteins from the database if a sufficient match is found. Proteins thus assigned to a functional class are analyzed to extract a new, more extensive dictionary of characteristic keywords. The process is iterated until classification quality no longer increases ( Fig. 3 ). A limitation of this approach is that only simple correlations between keywords can be 'discovered'. The method is scalable and can be applied to very large protein databases. For the genome sequence of Mycoplasma genitalium [68] , the EUCLID system was able to classify 52% of the sequences at a classification accuracy of 82%. The EUCLID algorithm has been incorporated into the GeneQuiz system [69] . GeneQuiz is a semi-automated protein sequence analysis workbench whose principal purpose is to infer a specific and reliable functional assignment together with a broad cellular role for a query protein by analysis of annotations from sequence database matches.

Fig. 3. : The EUCLID algorithm. Scheme of the iterative method used to classify sequences in three functional classes. The classification relies on the definition of a dictionary of keywords characteristic for a particular functional class. (1) Experts assign hexokinase from yeast (hxkb_yeast) to the ENERGY class. (2) A keyword dictionary is constructed scoring the keywords associated with hexokinase in the ENERGY class. (3) The same dictionary is then extended to classifying other proteins. The process is iterated until no more keywords are gained.

Mining free text from the literature

Digging deep into the vast, dark space of publications. Experimental results are usually published first in scientific journals. Since such publications do not conform to any standardised rules, this information is not computer-readable. At best, this lack of automation leads to a severe delay in incorporating the information into databases. Furthermore, a lot of the data will lie buried in the literature forever. The PDB database of protein structures defines standards to which the submitted data has to confer. One solution to the problem of burying information in the literature might be to adopt similar standards for the publication of functional information. For example, it could be required to deposit functional information into databases that have controlled vocabularies. While such a concept is currently being discussed, for the time being text-mining tools are the only means of retrieving functional information from the literature. In recent years, many groups have worked on dedicated problems in this area, like machine-selection of articles of interest [70, 71] , automated extraction of information using statistical methods [72, 73] ,or natural language processing techniques [74, 75, 76, 77] as well as setting up specialized knowledge bases for storing molecular knowledge [78] . The invaluable electronic availability of scientific publications through MEDLINE [79] not only severely impacted the ways of writing papers and doing science in general, it also enabled the development of an avalanche of methods that mine these data. Automatic text-analysis tools can assist human annotators and can thus significantly shorten the time-lag of functional annotations. One of the most crucial bottle-necks for automated text analysis is the mapping of gene/protein names [80, 81, 15] . While this problem may be over-come in the near future by particular standards adopted by journals, this hurdle currently hinders the availability and usefulness of public methods, considerably.

Natural language processing vs. field-specific 'grammars'. Many tools focus on mining MEDLINE abstracts. While the principal reason for this restriction is supposedly related to complexity (abstracts available, fit onto a disk, can be searched quickly), abstract occasionally are more easy to mine since many papers contain less precise and less well supported sections in the text that are difficult to distinguish from more informative sections by machines [82, 83, 84] . The current version of MEDLINE contains nearly 12 million abstracts stored on approximately 43GB of disk space. A prominent example of methods that target entire papers is still restricted to a small number of journals [76, 85] . The task of unravelling information about function from MEDLINE abstracts can be approached from two different angles. On the one hand, computational techniques for understanding text written in natural language (NL) are based on lexical, syntactical and semantic analysis [65, 86] . In addition to indexing 'terms' in documents, natural language processing (NLP) methods extract and index higher level semantic structures composed of terms, and relationships between terms. This can be done in different ways [87] . However, this approach is confronted with the variability, fuzziness and complexity of human language [83] . The Genies system [76, 85] for automatically gathering and processing of knowledge about molecular pathways and the IFBP transcription factor database [88] are natural language processing (NLP) based systems. An alternative approach that may be more relevant in practice, is based on the treatment of text with statistical methods [89, 90] . In this approach, the possible relevance of words in a text is deduced from the comparison of frequency of different words in this text with the frequency of same words in reference sets of text [91] . Some of the major methods using the statistical approach are AbXtract [92, 90, 93] and the automatic pathway discovery tool of Ng and Wong [74] . There are advantages to each of these approaches (grammar or pattern matching). Generally, the less syntax is used, the more domain-specific the system. This allows the construction of a robust system relatively quickly, but many subtleties may be lost in the interpretation of sentences. In some applications, however, the domain-dependent pattern matching approach may be the only way to attain reasonable performance in the near future [94] .

AbXtract: extraction of keywords from abstracts. The AbXtract system [92, 90, 95, 96] is triggered by collections of abstracts related to a given protein, and it is able to extract functional information directly from MEDLINE abstracts. Relevant keywords are selected by their relative accumulation in comparison with a domain specific background distribution. To obtain a representative set of words (and their abundance) in protein families, the background distribution of abstracts is chosen so as to represent the widest range of protein families. For each of the representative set (dictionary) of words, two statistical parameters are computed: their frequency in each family and the deviation of the distribution of their frequencies in the set of families. Provided with a query family and an associated set of MEDLINE abstracts, words that are likely to be functionally important for the family (putative keywords) are found by comparison with the background set. This is done by measuring the frequency of the relevant word in the query family relative to its background frequency of occurrence using a z-score [90] . Words with a high z-score are likely to be potential keywords for the family. The system has been tested on a number of different protein families and showed a good ability to extract functionally important keywords. A modification of this algorithm, called SUISEKI [96, 81] , has been applied to the problem of extracting protein-protein interaction from MEDLINE abstracts. In addition to the statistical approach of AbXtract, SUISEKI (System for Information Extraction on Interactions) also takes advantage of the analysis of the syntactical structure of phrases and other developments in computational linguistics. The SUISEKI system was able to extract almost 70% of the interactions present in a relatively large text corpus at approximately 80% accuracy for the best defined interactions. The SUISEKI system discovered a total of 4657 protein-protein interactions between cell-cycle related proteins in yeast from ~5300 abstracts (~12 Mb). The authors identify a number of sources of error in mining MEDLINE abstracts, the currently most urgent problem are the numerous mistakes in identifying protein names. There is no systematic nomenclature for gene and protein names; this has led to a number of possible writing variants and synonyms. This babel obviously hampers detection and classification severely. The second major problem is caused by indirect

References