Neural networks predict protein structure: hype or hit?

Burkhard Rost ^{1, 2, *}

CUBIC, Dept. Biochemistry and Molecular Biophysics, Columbia University, 650 West 168^th Street BB217, New York, NY 10032, USA, rost@columbia.edu

This article is published in P Frasconi & R Shamir (eds.) 'Artificial intelligence and heuristic methods in bioinformatics', 2003 © copyright IOS Press (2003). IOS 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

Neural networks have been applied to many pattern classification problems. Here, I review applications to the problem of predicting protein structure from protein sequence. Initially, many methods were apparently designed by researchers who just wanted a real-life application for their gadget. However, the competitiveness of the field separated the wheat from the chaff. Meanwhile, several neural network-based methods have contributed significantly to advancing the field of bio-informatics, and some are clearly influencing molecular biology. Today, a plethora of network methods is used in everyday sequence analysis, and an increasing number of applications explore very novel problems.

The protein structure prediction problem

Proteins constitute life’s machinery. The first bacterial genome was sequenced in 1995   [1] ; the first mono-cellular eukaryote (Saccharomyces cerevisiae, yeast) followed in 1996   [2] . Meanwhile, we know the entire proteomes (all proteins in a genome) of various multi-cellular eukaryotes: Drosophila melanogaster (fly)   [3] , Caenorhabditis elegans (worm)   [4] , the plant Arabidopsis thaliana   [5, 6, 7, 8] . The first drafts of the human genome   [9, 10] have also been completed, however, one year later, we still do not know all human proteins   [11] . Overall, more than 60 entire organisms have been sequenced over the last eight years. This avalanche of entirely sequenced organisms is exciting for biology because the genomes contain the blueprint for all parts of life’s machinery. The machinery itself consists of proteins that perform most important tasks in organisms (catalysis of biochemical reactions, transport of nutrients, recognition, and transmission of signals). Proteins are formed by joining 20 different amino acids (dubbed residues, when joined in proteins) into a stretched chain. In water, many proteins fold into unique three-dimensional (3D) structures. The main driving force is the need to pack residues for which a contact with water is energetically unfavourable (hydrophobic residues) into the interior of the molecule. This appears possible through the formation of a macroscopic substructure called secondary structure ( Fig. 1 ; for an introduction into protein structure, see:   [12] ; for principles of folding, see:   [13] ).

Sequence determines structure determines function. The world of proteins is governed by shape: interactions between proteins are mediated by the ‘key-hole’ principle, i.e., two proteins interact when they fit to one another like a key into a hole. Thus, protein structure determines protein function. What determines structure? All information about the native structure of a protein is coded in the amino acid sequence, plus its native solution environment   [14] . Can we decipher the code, i.e., can we predict 3D structure from sequence, or in other words: Can we unboil the egg   [15] ? In principle, the code could by deciphered from physico-chemical principles using, e.g., molecular dynamics   [16, 17, 18] . In practice, such approaches are frustrated by principle obstacles   [20, 21] . Furthermore, the last decade has unravelled that possibly most proteins do not adopt their native 3D structure in vitro, rather the need the cellular machinery to correctly fold in vivo   [22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33] .

Fig. 1. : Representation of HIV-1 protease (PDB code 1HHP) in 1D and in 3D. 1D: SEQ, sequence in one-letter code; SEC, secondary structure assignment (E for strand, blank for loop); note only the first 34 residues corresponding to the first strands (upper left arrows in 3D representation) are shown. 3D: The trace of the protein chain in 3D is plotted schematically as a ribbon Ca-trace (alpha carbons = backbone of protein). Strands are indicated by arrows, the short helix is on the right towards the end (C-term) of the protein. Graph made with MOLSCRIPT   [19] .

State-of-the-art in protein structure prediction. For over 40 years, there has been an ardent search for methods predicting protein structure from sequence (reviews:   [34, 35, 20, 21, 36, 37] ; books:   [38, 39, 40] ). Many methods were found which looked initially very promising - but always the hope has been dashed   [41] . How well do we do in practice? The following results stand out after four experiments initiated by John Moult (CARB, Washington) to explore the accuracy of structure prediction   [42, 43, 44, 45]. The goal to predict structure from sequence has not been reached, yet. However, most recently approaches that assemble fragments have scored considerable successes   [46, 37, 47]. Comparative modelling enables rather accurate predictions of 3D structure for proteins that have significant sequence similarity to proteins of known structure. This technique increases the number of known structures effectively by a factor of 5-30   [35, 20, 48, 36, 49, 50]. Methods addressed at solving simplified structure prediction problems, such as predictions of secondary structure, solvent accessibility, and inter-residue distances   [35, 20, 51] have become significantly more accurate, and useful by using the information contained in growing sequence databases.

How can neural networks predict protein structure? In practice, the only successful attempts at predicting aspects of protein structure are based on an analysis of common features extracted from proteins of known structures. Neural networks comprise a particular tool for pattern classification ( Fig. 2 ) that – along with many others – has been applied to the problem of protein structure prediction   [52, 53, 54, 55, 56, 57, 58] . We could write the history of neural network applications in four chapters. Initially, researchers applied black boxes, and searched improvements through optimising the internal free parameters (training speed, network architecture). These early applications were often not evaluated on representative data sets, and thus were scarcely used by biologists. (2) Later, researchers have opened the black box by extracting, or implementing rules, by carving specific knowledge into the networks, and by using networks to detect errors or outliers in data bases. (3) Then, the combination of neural networks with evolutionary information unleashed the full potential of the tool and thus established networks in the bioinformatics community. Incidentally, the successful prediction of protein secondary structure was one of the first examples for applications of neural networks in which these significantly exceeded the performance of all other systems and even of experts   [63]. The last five years of network applications combined many of the lessons learned in the first decade of the tools' history: non-network-experts applied these methods as a standard element in a tool box, and network-experts developed new architectures tailored to particular problems. Here, I focused on discussing but a few representative applications of neural networks (for an excellent review of network applications:   [58] ). 

Simple neural network: The simplest layered feed-forward neural network consists of a layer of input units (here two), and a layer of output unit(s) (here one). Signals are transmitted from input to output layer (feed-forward) via the connections (J’s). The network dynamic consists of a linear and a non-linear step. (1) The value of each input unit (example: 0 for unit 1; 1 for unit 2) is multiplied with the strength of the connection; the products sum to a local field (h) representing the signal that arrives at the output unit. The multiplication represents a projection of the input vector onto the vector of the connections. (2) The final output is determined by applying a sigmoid function (shown is the hyperbolic tangent) to the local field. The result is that the output is constrained to values between 0 and 1. On the right hand side the potential of such a network is illustrated: the open, and the dark circles are separated by a line.

Two-layered neural network: Two open and two dark circles can obviously not be separated by a single straight line. Two lines would enable the separation, but how can a neural network introduce two lines? The simple trick is the introduction of a layer of hidden layers (hidden as neither input nor output). The dynamics of such a network are identical to the simple network without hidden layer.

Training a neural network: How can particular pattern classification problems be implemented? The input is fixed by the pattern, as well is the desired output. The output for a given set of connections is uniquely determined by the dynamics of the network described above. The actual network error can be written as:

E = (output – desired)²

The free variables that contain the potential of the network to learn a given problem are the connections between the layers of units. The simplest way to reduce the network error is by changing the connections according to the derivative of the error with respect to the connections, i.e., by a gradient descent that assures to move downhill in the error-landscape:

This is often referred to as back-propagating the error through the neural network   [59, 60] . To avoid being trapped in local minima, in practise, the actual training is typically performed by a variant of this algorithm that permits up-hill moves (conjugate gradient descent   [61, 62, 57] ).

Generalisation ability: With enough hidden units neural networks can learn to separate any set of patterns. Typical applications require to extract particular features (underlying rules) present in the patterns rather than to learn the known examples ‘by heart’. A successful extraction of such features permits the network to generalise, i.e., to also correctly classify patterns that have not been learned explicitly. Generalisation requires a balance between the number of training examples (enough to enable feature extraction), and the number of connections (enough to separate patterns). As a rule-of-thumb the number of connections should be an order of magnitude lower than the number of patterns to avoid over-fitting the training data (this learning-by-heart of the training set is also referred to as ‘over-training’).

Deus ex machina?

No improvement in secondary structure prediction by black boxes. Secondary structure prediction methods distinguish between helix (H), strand (E: for extended structure), and other (L for loop). Some stretches of sequence show a particular preference to be in one of these three states. The prediction task is to classify w adjacent residues as either H, E, or L ( Fig. 3 ). Simple neural networks reached values around 60% accuracy (percentage of residues predicted correctly in any of the three states HEL)   [64, 65, 66] . This was similar to the best methods 30 years of research had resulted in by the end of the 80's   [67, 61, 68, 69, 35, 70, 51] . Attempts to improve performance by changing the network details failed   [71, 53] . In contrast, combining neural networks with other methods succeeded to some extent   [72] .

Prediction of functional class. Methods predicting functional similarities between proteins have been based (i) on multiple feed-forward networks   [73] using proteins of similar sequences as input, (ii) on simple feed-forward networks using different amino acid features as input   [74, 75, 58] , and (iii) on Kohonen maps   [54] using the frequency with which any of the 20*20 possible residue pairs occurs in the sequence   [76, 77, 78, 79] , or using the information extracted from database annotations   [80, 81] . While feed-forward networks are useful to learn a classification into known features (e.g. types of secondary structure), Kohonen maps have been applied to render a general classification scheme of proteins (e.g. A and B, are similar, and A is more similar to C, than B). Such a classification is a priori not evident and by itself an area of controversy in active research, e.g., attempting to answer questions like: Are we more similar to an orang-utan than to a pig?. One hope guiding such analyses is to end up with similarities between proteins that might help to learn about details in bio-chemical reaction pathways. The neural network-based automatic annotation system   [80, 81] has already been applied successfully to genome analysis   [82] .

Prediction of surface exposure, and function-specific motifs. When attempting to arrange secondary structure segments in 3D, one needs to know to which extent a particular residue is exposed to solvent. Neural networks were used to classify amino acid residues as either buried or exposed   [83] . Often protein function is associated with relatively short (5-10 residues) sequence motifs (unique pattern of adjacent amino acids). Examples for motifs found by neural networks include: (i) sequence motifs that reveal binding of energy storage molecules   [52] , (ii) sequence motifs specific for particular proteins, e.g. the immunoglobulins   [84] , and (iii) signal peptide motifs in sequences   [85, 86] . The group of Søren Brunak (Copenhagen) has developed two methods of particular practical impact: (i) a system of neural networks predicting signal peptides and cleavage signals   [87] , (ii) and a combination of rules, and networks predicting glycosilation sites   [88] .

Fig. 3: Simple neural network for secondary structure prediction. For simplification the protein sequence given consists of two amino acid types (S and P). The protein sequence is translated into patterns by shifting a window of w adjacent residues (shown w = 5; typical values in practice are w = 13-21) through the protein. The output of the network is uniquely determined ( Fig. 2 ). Suppose the output would be: 0.2, 0.4, 0.5 for the three output states (H, E, L). For known examples the desired output is also known (1, 0, 0 if the central residue is in a helix). Consequently, the network error is given by the difference between actual network output and desired output. The only free variables are the connections. Training or learning means changing the connections such that the error decreases for the given examples. A training set typically comprises some 30,000 examples. If training is successful, the patterns are correctly classified. But how can new patterns be classified correctly? The hope is that the network succeeds in extracting general rules by the classification of the training patterns. The generalisation ability is checked by another set of test samples for which the mapping of sequence window to secondary structure is also known. Sufficient testing is crucial and requires (1) to remove any significant sequence similarity between test and training set, and (2) to evaluate the expected prediction accuracy on a sufficient number of test proteins (rule of thumb: > 100).

Opening the black box

Extracting rules from, and implementing rules into neural networks. Genome sequences do contain some information about protein structure   [89] . A prerequisite to uncover this result was to learn the genetic code by a neural network, i.e., the mapping between the four-letter alphabet of the nucleic acids (DNA), and the 20-letter alphabet of the amino acids (proteins). Analysing the rules learned by the network suggested evidence for a particular scenario for the evolution of the genetic code ( Fig. 4 ). In a similar attempt to extract rules by specific modulation of the training procedure Tchoumatchenko, Vissotsky and Ganascia extracted more complicated rules from networks that learned to predict secondary structure than were available by statistical analysis   [90] . Unfortunately, that attempt did not improve performance. Maclin and Shavlik explored the opposite approach by incorporating expert rules into a neural network and thus improved performance over simple statistical devices   [91, 92] . All these approaches proved that neural networks are not black boxes, but can become as ‘transparent’ as rule-based systems. The problem often has been to make use of the complex rules extracted.

Carving biology into neural networks. Two problems are common to most secondary structure prediction methods (including simple networks, Fig. 3 ): (1) strands are predicted at almost random levels of accuracy, (2) and predicted secondary structure segments are too short   [61, 68] . The common explanation for the first problem was that strands are stabilised by long-range interactions not visible in a segment of 13-21 residues. The training dynamics of neural networks revealed that networks learned to classify helix, and loop ten times faster than strand   [56] . Consequently, the idea was to simply increase the frequency in presenting strand residues during training. This change of the training dynamics improved strand accuracy significantly, indicating that the inferior prediction of strand did NOT result primarily from long-range interactions, but from technical problems. The second problem of predicting too short segments originates from the fact that the sliding window ( Fig. 3 ) erases the correlation between adjacent residues. This shortcoming was corrected by introducing a second level network   [56] ( Fig. 5 ). Such a network system learned correlations between adjacent residues. These examples illustrate that neural networks can easily be tailored to particular problems.

Fig. 4: Learning the genetic code. The four-letter nucleic acid code from the genomes is translated into a 20-letter amino acid code from proteins. Three nucleic acids (dubbed one codon) code for one amino acid. This implies that the four nucleic acid can code for 4*4*4 = 64 amino acids, i.e., the code is redundant: some amino acids are coded for by more than one codon, and three codons are used for stop-signals during the translation procedure. The minimal network that learned the genetic code had two hidden units   [93] . The four graphs represent the connections between the 20 input and the two hidden units. (1) The untrained network with randomly assigned weights locates all 61 points near the centre of the square. (2) After seven training epochs the points have moved into a transient local minimum, where the activities of the intermediate units are close to one and the activities of all the output units are close to zero. (3) At 30 epochs the groups have started to segregate, but are still mixed. (4) Finally at 13,000 epochs the network groups the 61 codons at the edge of the circular region. After the four epochs shown the number of correctly classified codons was 2, 6, 26 and 61, respectively. The final grouping separates hydrophobic residues (top: IMVPF) from hydrophilic (centre right and left: YQHKNEDR), and others (lower right: TSAGPCW). The figure is taken from   [93] .

Fig. 5: Second level neural network [56]. (1) The window of w adjacent residues is shifted through the protein (here w = 5). For each window secondary structure is predicted for the central residue (shown three windows with central residues S, P, S). (2) The prediction of this first level network is fed into a second level network. This is again realised by shifting a window of w adjacent predictions through the protein (for the second level w = 3). The final prediction of secondary structure is valid for the central residue of the second window (here a P).

Detecting database errors during training. Neural networks generalise by extracting the underlying physico-chemical principles from the training data. Obviously, this requires a correct training set. Søren Brunak has pioneered the idea to unravel errors in the training set by monitoring samples that could not be learned even when the networks were trained until over-fitting the data   [94, 95, 96, 97, 87, 98, 99] . This technique has not only been used successfully to identify errors, and inconsistencies in public databases, but also to improve the performance of the networks.

Learning from evolution to predict protein structure

Long-range information in multiple sequence alignments. Some residue substitutions do not alter protein structure. However, not every amino acid can be replaced by any other. On the contrary, one evolutionary step (exchange of one residue) can destabilise a structure. Thus, residue substitution patterns observed in protein families are highly specific for particular details of protein structure and function, i.e. they contain more information about structure than do single sequences. Furthermore, multiple alignments of sequence families implicitly also carry information about interactions between residues separated by more than w residues in sequence. We can profit from this evolutionary information for structure prediction in the following way   [56]. A sequence of unknown structure U is aligned against a database of known sequences. (2) Proteins with significant sequence identity to U are retrieved. (3) For each sequence position the profile of residue exchanges in the final multiple alignment is compiled, and fed into a network ( Fig. 6 ).

Significant improvement of secondary structure prediction. Using evolutionary information has improved secondary structure prediction accuracy from 65% to over 70%   [100] , or even over 72%   [56] . Such a profile based neural network system was the first method to surpass the magic line of 70% accuracy, and has proven to remain the most accurate method for almost a decade. Today's best methods still use the same idea of feeding evolutionary information into neural networks. The latest improvement to levels above 76% accuracy mainly resulted from larger databases and more sensitive search methods retrieving similar proteins from these larger databases   [101, 102, 103, 104, 105, 51, 106] .

Evolutionary information improved accuracy in predicting solvent accessibility. Solvent accessibility at each position of the protein structure is evolutionarily conserved within sequence families. This fact has been used to develop another neural network method for predicting accessibility from multiple alignment information   [56] . The final network system is clearly more accurate than methods not using alignment information, and has been established to be more accurate than other prediction methods. More recently, several groups have attempted to refine the concept by training networks to predict different implementations of the output state for solvent accessibility   [88, 101] , by focussing on particular protein families [Stahl, 2000 #5932; Lebeda, 1998 #5933; Lebeda, 1998 #5934; Lebeda, 1997 #5936], or by predicting the number of contact partners for each amino acid [Fariselli, 2000 #4978; Fariselli, 2001 #5355; Pollastri, 2001 #5863; Dosztanyi, 1997 #5935].

Predicting transmembrane helices by combining networks with dynamic programming. The neural network system designed to predict secondary structure for water-soluble proteins failed in predicting helices inserted into the lipid-bilayer of membranes. However, the networks have been re-trained to also predict transmembrane helices   [56] . Again information from multiple alignments improved prediction accuracy significantly   [56, 35, 20] . The problem of predicting transmembrane helices is ideal to incorporate additional globular information into the prediction method. The principal idea is to regard the neural network prediction as an energy landscape and to search the best path through this landscape given that transmembrane helices are constrained to a minimal and a maximal length. The final system has achieved a significantly higher accuracy than the simple neural network-based system, and has been applied to analysing entire genomes   [107, 108, 109, 49, 33] .

Fig. 6: Feeding evolutionary information into a neural network system [56]. (1) A sequence family is aligned (shown are the sequence of unknown structure and three aligned relatives). (2) For each sequence position of profile is compiled that gives the percentage of S, or P in the alignment (shown in centre for window of five adjacent residues). (3) Instead of using binary input units (0 or 1), now the profile is fed into the first neural network. (4) Finally, the output is again fed into a second level network ( Fig. 5 ).

Neural network architectures as simple and plastic tools

Avalanche of applications with standard architectures. The first neural networks were applied to protein structure prediction in 1988   [64, 65] . A decade later, networks have become a standard method that is tested on problems in bioinformatics ( Table 1 ). Particular recent examples are networks that discover motifs on 3D structures   [110] , distinguish good from bad drug targets   [111] , predict binding motifs   [112, 113, 114, 115, 116] , biological activity   [117, 118] , post-translational modifications   [97, 119, 87, 88, 120, 99, 121, 122, 123] , particular protein types   [124] , domains   [125] folding rates   [126] , disordered proteins   [127, 128, 129, 130] , and even substitution matrices   [131] . The major strength of networks for many of these applications appears to be that they can readily be adapted to particular problems ( Table 1 ). Two extreme examples of neural network applications are to replace first order statistics when averaging over a variety of scores, i.e. networks with very few input units that use results from a variety of threading methods to identify remote similarities between proteins   [132, 133] . The opposite extreme is to generate thousand different networks each specialised on some aspects of the secondary structure prediction problem and to then statistically average over the outputs of these networks   [103] .

References