Automatic determination of protein fold signatures from structural superpositions

cootes@icrf.icnet.uk, stephen@cs.york.ac.uk, sternber@icrf.icnet.uk
 

Abstract. It remains unclear what principles underlie a protein sequence/structure adopting a given fold. Local properties such as the arrangement of secondary structure elements adjacent in sequence or global properties such as the total number of secondary structure elements may act as a constraint on the type of fold that a protein can adopt. Such constraints might be considered "signatures" of a given fold and their identification would be useful for the classification of protein structure. Inductive Logic Programming (ILP) has been applied to the problem of automatic identification of structural signatures. The signatures generated by ILP can then be both readily interpreted by a protein structure expert and tested for their accuracy.

A previous application of ILP to this problem indicated that large insertions/deletions in proteins are an obstacle to learning rules that effectively discriminate between positive and negative examples of a given fold. Here, we apply an ILP learning scheme that reduces this problem by employing the structural superposition of protein domains with similar folds. This was done in three basic steps. Firstly, a multiple alignment of domains was generated for each type of fold studied. Secondly, the alignment was used to determine the secondary structure elements in each of those domains that can be considered equivalent to one another (the "core" elements of that fold). Thirdly, an ILP learning experiment was conducted to learn rules defining a fold in terms of those core elements.

The relationship between a proteins sequence and its structure and function is complex and, as yet, not fully understood. To a large extent, the current understanding of protein sequence/structure/function has come from careful manual examination. However, the recent explosion in the amount of sequence data from genome projects and the ever increasing numbers of protein structures has highlighted the need for automatic approaches to the analysis of biological problems. One such problem is the identification of the key structural features that define a given protein fold. A previous study [1] that applied Inductive Logic Programming (ILP) [2] to the automatic identification of structural signatures in protein folds found that large insertions and deletions in a protein structure proved to be a major obstacle. This was because the structurally equivalent portions of proteins with the same overall fold could not easily be identified. In this study, we applied a multiple structure alignment technique to identify equivalent sub-structures in proteins with the same fold. ILP was then applied to learn the principles governing that fold in terms of those core sub-structures.

In this study, we build multiple structure alignments of all domains with the same fold from pairwise alignments calculated with the SSAP program. Obtaining a reliable multiple structure alignment is typically quite difficult [14] but this enables the identification of structurally equivalent (core) secondary structures in those domains and the elimination of inserted structures (non-core) that inhibit the learning of global structural features. From these core secondary structure elements rules were learnt for several SCOP fold classifications and tested for their accuracy.

The SCOP database is constructed manually and is based on the knowledge of protein expert A. Murzin, taking into account evolutionary relationships between protein sequence, structure and function. This classification scheme offers the advantage that each fold classification has a brief text description of the principles on which each fold type is categorised so that the rules learnt can also be compared to human expert knowledge.

The set of protein domains used for each fold category were obtained from the SCOP database [3], release number 1.50. For learning rules, one domain from each protein/species category within the four main fold classes (all alpha, all beta, alpha/beta and alpha+beta) were selected using the ASTRAL [15] database. This included some related domains from the same SCOP family but this was found to improve both the multiple structure alignments and the quality of the rules learnt as determined by our protein expert (M. Sternberg). However, for the purposes of testing, one domain per SCOP family was selected in order to eliminate redundancy.

In order to define the core structural elements for each domain within a given fold category, a multiple structure alignment of those domains was performed. Multiple structure alignments indicate which residue positions in the aligned domains that can be considered structurally equivalent and eliminate the variable regions in the structures from consideration.

For the purposes of this work, a technique was employed whereby multiple alignments were constructed by clustering pairwise alignments of domains with similar folds. Such a method tends to neglect global features of the multiple alignment but is fast to calculate. Pairwise alignments were generated for each possible pair of domains using the SSAP program [13]. The pairwise alignments were then clustered with respect to the structural similarity of the aligned domain pairs (given by their pairwise RMSD, which decreases with increasing structural similarity), in a similar manner to that in a previous publication [16], to give the final multiple structure alignment.

The clustering process is shown schematically in Figure 1 and proceeded as follows: Firstly, a master domain was selected by finding the domain with the lowest average RMSD to all other domains in that fold category. The master domain then acted as a seed for the subsequent alignment of the remaining domains. To eliminate outliers, any domains that had 6 Å RMSD with the master domain were firstly eliminated from further consideration. Then, the domain with the lowest RMSD to the master domain was then aligned to that domain so that the current alignment then contained two domains. The domain with the lowest average RMSD to the domains in the current alignment was then aligned to the closest domain in the current alignment. This process continued iteratively until all domains in that fold category have been considered. In order to avoid corrupting the multiple alignment with misaligned pairwise alignments, domains that align to less than 2/3 of the residue positions in the current alignment at any given step were eliminated from consideration. For most fold categories, only a few domains were eliminated in this way.

An example of a multiple structure alignment in shown in Figure 2.

The multiple structure alignment indicates which residues in each structure can be considered structurally equivalent. However, to learn rules for protein structure in terms of secondary structure elements (blocks of residues with an alpha-helical or beta-strand structure) the elements that can be deemed equivalent have to be identified. To do this, a simple matching scheme was employed to match secondary structures units in different domains based on the level of overlap of those units in the multiple alignment calculated previously (shown schematically in Figure 3).

The secondary structure for each protein in the multiple structure alignment was determined using the PROMOTIF [17] program. Firstly, those secondary structure elements that have less than half of their constituent residues aligned were removed from consideration. Then, all pairwise "matches" between secondary structure elements in each pair of aligned proteins were determined. A "match" was deemed to have occurred between two secondary structure elements from different proteins if each was the largest overlapping element of the other in their respective proteins. Secondary structure elements were then grouped into "maximally matched" groups (ie. each member of the group is "matched" with every other member of that group). Surprisingly, in some cases this was enough to find equivalent secondary structures in every protein. However, a more relaxed matching scheme is required to find some of the less easily identifiable core elements. Therefore, groups of "sub-maximally matched" elements were identified by breaking up the smallest maximally matched group and redistributing its individual member elements to the largest group for which that element matches more than 1/2 of the constituent members of that group. If no such group could be found then the element was eliminated from further consideration. This process continued iteratively until the only remaining groups contained elements in more than 2/3 of the aligned domains. The remaining elements were deemed to be core elements and equivalent to the other member elements in the same group. Each core group is labelled according to its position in the sequence (i.e. the first group is labelled "a", the second "b" and so on).

Once the core elements for a protein structure have be defined, the background knowledge containing the structural information for that example can be determined in terms of those core elements. The predicates describing the attributes of, and relationships between, core elements that were considered here and their descriptions are listed in Table 1. All of the structural information required for determining the background knowledge was taken from the output of the PROMOTIF [17] program for that example.

Rules were learnt for each SCOP fold category in which protein domains from more than 5 sequence families could be aligned (shown in Table 2) using the Progol-4.4 ILP system. Progol is described in more detail elsewhere [18,19], below is a brief description of the algorithm.

Progol then proceeds to learn a rule by selecting a positive example and collecting all related background information. It then builds steadily more specific rules from that information until its measure of compression is maximised. The measure of compression used f is:

where p is the number of positive examples covered by the rule, n is the number of negative examples covered and c is the length of the rule. The parameter c ensures that for rules with equal coverage of positive and negative examples the shorter one is favoured (i.e. the one that obeys the principle of parsimony). Once an optimal rule is found, the positive examples covered by that rule are removed and the process begins again. This continues until no positive examples remain.

The maximum number of nodes (or hypotheses) tested allowed for an individual search was set to 1000. The noise parameter controlled the number of negative examples that a rule was allowed to cover. The level of noise allowed was 20% (i.e. up to 20% of examples covered by a rule could be false positives).

5-fold cross-validation testing was performed for rules learnt for each fold category considered.

The composition of the rules that were learnt for all folds as given in the previous section are shown in Table 3.

Perhaps the most interesting difference between this study and previous work using ILP to discover structural signatures is the ability of this method to capture the global features of folds familiar to human experts. In this section, rules are presented for three important folds and compared to rules learnt previously with ILP without structural alignments [1] and the text descriptions of those folds that have been provided on the SCOP [3] website. The descriptions provided by SCOP are preliminary, and do not represent the sum total of expert-knowledge of the fold, but do give a general expert guide to the general features of the fold. Rules learnt using Progol are output in terms of clauses consisting of the combinations of the types of predicate listed in Table 1, but for clarity and ease of comparison, the rules so learnt have been interpreted into english statements similar to that of the SCOP descriptions. The rules given for Immunoglobulin-like beta-sandwich (SCOP classification 1 002 001), TIM barrels (1 003 001) and Rossmann-like folds (1 003 002) are shown in Table 4.

However, the approach to learning structural principles from multiple structure alignments of protein domains used here is currently limited to the well-represented SCOP fold types, as multiple structure alignments used here become far less reliable in defining core structural components when there are only a few domains as examples. As the majority of fold types defined by the SCOP classification have very few domain examples, the method used here may not prove to be as useful when applied to all possible fold categories. An automated method that could extract structural principles from less well represented folds would be far more useful generally. Human experts have a better understanding of the well-represented folds and an automated method may simply give them structural features that they already know for these folds. However, human expertise does not generally extend to many of the less-well represented folds and automated methods of knowledge discovery could yield useful insight in these cases.

Apart from extending this method to folds with fewer examples, other improvements could be made to this method. The representation used here (Table 1) does not include sequence motifs known to be associated with particular functions, such as those collated in the PROSITE [22] database. The inclusion of such motifs could give further insight into the relationships between sequence/structure/function and assist in fold classification and prediction. Currently, the only sequence properties that are represented here are the presence of glycines and prolines in secondary structure elements.

This study shows that ILP can learn global structure principles for fold after identifying the core structural elements via a multiple alignment. The rules learned for well-represented folds reflect principles known to protein experts.

This work was supported by a BBSRC grant.

[1] Turcotte, M., Muggleton, S.H. and Sternberg, M.J. (2001) Journal of Molecular Biology, 306, 591-605.

[2] Muggleton, S.H. and Raedt, L.D. (1994) Journal of Logic Programming, 19/20, 629-679.

[3] LoConte, L., Ailey, B., Hubbard, T.J.P., Brenner, S.E., Murzin, A.G. and Chothia, C. (2000) Nucleic Acids Research, 28, 257-259.

[4] Pearl, F.M.G., Lee, D., Bray, J.E., Sillitoe, I., Todd, A.E., Harrison, A.P., Thornton, J.M. and Orengo, C.A. (2000) Nucleic Acids Research, 28, 277-282.

[5] Holm, L. and Sander, C. (1998) Nucleic Acids Research, 26, 316-319.

[6] Hadley, C, Jones, D.T. (1999) Structure Fold. Des., 7,1099-112.

[7] Moult, J., Hubbard, T., Fidelis, K. and Pedersen, J.T. (1999) Proteins, 37 (S3), 2-6.

[8] Muggleton, S.H., King, R.D. and Sternberg, M.J. (1992) Protein Engineering, 5, 647-657.

[9] King, R.D., Muggleton, S.H., Lewis,R.A. and Sternberg, M.J. (1992) Proc. Nat. Acad. Sci. USA, 89, 11322-6.

[10] King, R.D., Clark, D.A., Shirazi, J. and Sternberg, M.J. (1994) Protein Engineering, 7, 1295-1303.

[11] Hirst, J.D., King, R.D., and Sternberg, M.J. (1994) Journal of Computer-aided Molecular Design, 8, 405-20.

[12] King, R.D., Muggleton, S.H., Srinivasan, A. and Sternberg, M.J. (1996) Proc. Nat. Acad. Sci. USA, 93, 438-42.

[13] Taylor, W .R. and Orengo, C.A. (1989) Journal of Molecular Biology, 208,1-22.

[14] Gerstein, M. and Levitt, M. (1998) Protein Science, 7, 445-456.

[15] Brenner, S.E., Koehl, P. and Levitt, M. (2000) Nucleic Acids Research, 28, 254-256.

[16] Kelley, L.A., MacCallum, R.M. and Sternberg, M.J.E. (2000) Journal of Molecular Biology 299, 499-520.

[17] Hutchinson, E.G. and Thornton, J.M. (1996) Protein Science, 212-220.

[18] Muggleton, S.H. (ed.) (1992) Inductive Logic Programming. Academic Press, London.

[19] Muggleton, S.H. (1995) New Generation Computing Journal, 13, 245-286.

[20] Nagano, N., Hutchinson, E.G. and Thornton, J.M. (1999) Protein Science, 8, 2072-84.

[21] Wierenga, R.K., Terpstra, P. and Hol, W.G.J. (1986) Journal of Molecular Biology, 187, 101-107.

[22] Hofmann, K., Bucher, P., Falquet, L. and Bairoch, A. (1999) Nucleic Acids Research, 27, 215-219.

Figure 1. Flow diagram describing the construction of a multiple structure alignment for a given fold category.

Figure 3. Finding equivalent secondary structure elements in a multiple alignment. Represented are 5 proteins in a multiple structure alignment, aligned so that sequences are running horizontally. Rectangles represent secondary structure elements. Parts of those elements that are vertically above one another are considered to be structurally equivalent. (a) Maximally matched groups of elements are identified (groups are elements connected by lines). (b) Smaller groups are disbanded and their member elements are matched to the larger groups of elements using a less strict matching criterion. Dotted rectangles are the elements deemed to be non-core.

Table 1. The predicates from which rules were learnt. Each predicate is a logical expression in Prolog describing attributes of, or relationships between, elements in a protein domain.

number_helices(Lo =< D =< Hi): The number of helices in domain D.

adjacent(B, C): Secondary structure elements B and C are adjacent in sequence.

coil(B, C, N): Elements B and C are adjacent in sequence, separated by a coil of N residues.

contact(B, C): Elements B and C are in contact in space.

end_strand_distance(A, B, C, Dist): Strands B and C are the end strands of sheet A and are separated by distance Dist in space.

pair(B, C, Bloc, Cloc): Helices B and C are in contact. The parts (N-terminal, C-terminal or middle) of the helices B and C in contact are Bloc and Cloc respectively.

helix_angle(B, C, Angle): Helices B and C are in contact. B and C make angle Angle with each other, where Angle could be antiparallel, parallel or perpendicular.

has_n_strands(A, N): Sheet A has a total of N strands.

barrel(A): Sheet A is a barrel.

bifurcated(A): Sheet A contains a bifurcation.

sheet_top_X(A, N₁, N₂,…., N_X): Sheet A contains X strands, with topology N₁N₂…..N_X (i.e. the N's give the relative sequence order of the strands that are spatially adjacent in the sheet).

contains(B, AA, Loc): Element B contains amino acid AA at location Loc, where AA can be either glycine or proline and Loc can be the N-terminal, C-terminal or middle of the element.

contains(B, AA): As above, but independent of location in the element. 

Table 3. Composition of the rules learnt. Given are the relative proportion of rules learnt containing at least one of each type of predicate.

Table 4. Rules learnt for several fold types. Rules learnt using the method used in this study (ILP(new)) are compared to the rules learnt previously with ILP without multiple structure alignment (ILP (old)) and expert-like descriptions of those folds taken from the SCOP database (SCOP). Terms used in the SCOP descriptions are described in section 3.3.