The breakthrough in protein structure prediction

One of the key pieces of information required to understand a biological process is the structure of its constitutive proteins, but experimental approaches to structure determination are often time-consuming, laborious, and have uncertain outcomes, requiring large investments of time and resources. In contrast, protein sequences are readily obtained by translating genomic sequence and are available in great abundance. Since the structure of a protein is fully specified by its sequence, attempts to deduce one from the other — known as the protein folding problem — have been ongoing for half a century, rising in importance with the exponential growth in sequence databases and in frustration with the succession of methods that failed to bring decisive advance. Indeed, starting with the first decade of this century, there was a growing realization in the protein science community that this problem was one of the grand challenges of computational biology [1].

Things did not start this way. The secondary structures modeled by Linus Pauling from stereochemical considerations of the polypeptide chain [2,3] and soon afterwards the demonstration that such secondary structures could be assembled into three-dimensional models for α-keratin [4,5] and collagen [6,7] led to the expectation that a combination of geometric considerations, model-building, and parametric equations could solve the principles of protein structure, as they had already done for nucleic acids. However, the first protein crystal structures and their astonishing irregularity gave way to the realization that these principles might be considerably more complex than expected [8].

Despite this, excitement at the beginning of the 1990s about progress achievable through simplified biophysical representations of the polypeptide chain [9,10] and threading [11,12] led to the perception of rapid, often decisive, advance in deducing structure from amino acid sequence. This was, however, not matched by real-life applications of these methods, and it became apparent that some of the reported successes might have been due to ‘postdiction’, that is to the prediction of targets whose structure was already known to the predictors. To obtain an objective assessment of the state of the art in protein structure prediction, a group of scientists led by John Moult of the University of Maryland organized an experiment in 1994, CASP (for critical assessment of structure prediction), in which predictors could evaluate their methods within a doubly blind framework [13]. The organizers would collect sequences of proteins whose structure was not released (and in some cases had not even been fully determined yet) and make them available as prediction targets to computational scientists. The organizers would then hand the submitted predictions and solved structures to assessors, who had no knowledge of the participating prediction teams behind the group numbers. At the end of the experiment, which was to be repeated every two years, there would be a conference at which the results would be discussed.

CASP1 was a sobering experience, as the tools for structure prediction turned out to be quite blunt. In the words of the organizers: ‘Plenty went wrong with these predictions, and therein lies the principal value of the experiment’ [13]. The one source of information that worked reliably was the structure of proteins related to the target, and targets having relatives of known structure were classified as the easiest, accessible through modeling on the homologous template (called template-based modeling or TBM). However, it turned out to be quite hard to make a model that was closer to the target than the nearest available template because of errors in detection and target-to-template alignment. Applying biophysical methods, such as energy minimization, only seemed to make errors worse. Correspondingly, CASP2 saw an increased investment in the detection, modeling, and refinement of more remote homologs [14,15]. CASP2 was more successful than CASP1, particularly in the harder targets lacking detectable templates in the structure database (called free modeling or FM) where CASP1 predictions had been essentially random, but progress was still limited. The New York Times famously headlined its report with ‘Proteins 1, Computer 0’ and quoted one of the organizers, who had seen small signs of progress, that ‘it's encouraging but still a very long way from anything that could be useful’, while one of the assessors quipped that ‘failure can no longer be guaranteed’ [16].

From this base, the CASP3-5 experiments offered further improvements, however, mainly in the area of targets with intermediate difficulty, where a succession of increasingly powerful sequence search tools [17–19] allowed for the detection of ever more distant homologs. As it turned out, homologous proteins retain substantially the same fold, even when their sequences have seemingly diverged into a ‘midnight zone’ of dissimilarity [20]. In contrast, efforts to incorporate biophysical parameters into the prediction methods [21], while providing some impressive successes for smaller targets, did not scale to larger ones, leaving the statistical detection of evolutionary relatedness the main tool of structure prediction.

A measure for model accuracy introduced in CASP3, GDT-TS (for global distance test-total score), allowed to compare outcomes within and between experiments [22]. After iterative superposition of two structures with identical sequence, this measure compares the positions of cognate Cα carbons, tallies the percentage of pairs falling within distance cutoffs of 1, 2, 4, and 8 Å, adds up the percentages and divides them by four. This focus on similarity allows the measure to distinguish models that are poor, but contain locally correct segments, from globally wrong models, something that is not achieved by other related measures, such as root-mean-square deviation. Very roughly, GDT-TS scores around 20 denote largely random models, scores around 50 models with overall correct topology, and scores around 70 models with accurate global and local topology. Above 80, details of the structure are increasingly modeled correctly and above 95, models are as accurate as models built from experimental data.

An overview of GDT-TS scores in individual CASP experiments, shown as polynomial fits through the best scores achieved for each target in that experiment, was presented by John Moult in the introduction to the CASP14 conference, slide 19 [23] (the slide is also found at https://en.wikipedia.org/wiki/AlphaFold#/media/File:CASP_results_2020.png). This overview shows that, after CASP5, overall progress largely came to a standstill until CASP12, leading some in the field to wonder whether we would ever get to a solution of the problem. The seeds of the next advance, however, had already been sown.

From the start of the CASP experiments, scientists had wondered whether it would be possible to compute inter-residue contact maps from correlated mutations in the multiple sequence alignments of homologous proteins, in order to obtain a fingerprint of the fold and guide structure prediction [24]. The idea was that if mutations were correlated, the residues at those positions were most likely in physical contact, providing the sort of information that allows structure determination by NMR. The accuracy of such contact maps remained low for many years, however, because analyzing correlations in a pairwise manner could not distinguish between direct, structural correlations and indirect, functional ones. Much better distinction between the different sets of co-evolving residues became possible from around 2010 onward by global contact predictions using direct coupling analysis [25–27], which considered all pairwise interactions simultaneously and optimized the contact map globally to the observed set of pairwise correlations. This approach took a further, major step forward in 2017 with the demonstration that deep learning methods could not only extract high-quality contact maps from multiple alignments in this way, even in cases with few homologs, but also interpret the predicted contacts into a set of distances that allowed for a finer-grained geometric fingerprint for the underlying fold [28]. The application of convolutional neural networks for distance map prediction was used by leading structure prediction groups in CASP13 (2018) and had a powerful effect on the hard targets, for which the GDT-TS of the best models went from around 40 to over 60 (see slide 19 in [23]).

Among the groups scoring highly in CASP13 was an unexpected newcomer, AlphaFold, fielded by DeepMind, the leading artificial intelligence laboratory of Alphabet Inc. To everybody's surprise, this group bested all participants with the key insight that the probability distribution of the distance map could be converted to a protein-specific statistical potential, which could generate the protein fold by minimization [29,30]. While AlphaFold's lead in CASP13 was larger than the typical distance between the first- and second-ranked groups at previous CASP experiments, its overall performance was more incremental than transformational, providing the best model in only about a third of the cases, albeit with a larger lead for harder targets than for easier ones (Figure 1).