BACKGROUND
although a protein can be first characterised by its amino acid sequence, most proteins fold into three-dimensional structures that encode their function.
genomics projects leave us with millions of protein sequences, currently ≈  <dig> ×  <dig>  of which only a small fraction  have their 3d structure experimentally determined.
in the future, we might devolve upon structural genomics projects  <cit>  the task to bridge the huge gap between sequence and structure.
so far, though, even high throughput pipelines have not been able to make a dent in the massive ratio  between known sequences and structures, and a large fraction of structures are found to be unsuitable for structural determination with the methods available  <cit> .
therefore, computational protein structure prediction remains an irreplaceable instrument for the exploration of sequence-structure-function relationships.
moreover, even if the structural genomics goal of providing a model for each fold is achieved, algorithms that are able to model protein structures based on putative homologues  will become even more important to fully harness this novel knowledge.
this is especially important for analyses at genomic or inter-genomic level, where informative structural models need to be generated for thousands of gene products in reasonable amounts of time.
template-based algorithms for protein structure prediction typically adopt heuristics based on sequence and/or structural similarity to model the unknown structure of a protein  based on known structures that are fathomed to be homologous to it.
automating the modelling process is not trivial: there are several stages and critical points in the design  and for some of them manual intervention is at least helpful  <cit> .
the use of multiple templates is also an open question .
the accuracy of template-based techniques strongly depends on the amount of detectable similarity between query and templates, thus preventing the reliable application of these methods to a significant fraction of unannotated proteins.
this is the realm of the so called ab initio or de novo protein structure prediction , where models are predicted not relying on similarity to proteins of known structure.
ab initio techniques are not nearly as accurate as those based on templates  <cit> , but the design in this case is generally somewhat simpler.
a system for the prediction of protein structures ab initio is usually composed of two elements: an algorithm to search the space of possible protein configurations to minimise some cost function; the cost function itself, composed of various restraints being either derived from physical laws, from structural features  predicted by machine learning or other kinds of statistical system  <cit> , or possibly constraints obtained from experiments.
fragment-based algorithms  <cit> , that use fragments of proteins of known structure to reconstruct the complete structure of the target protein , have shown potential to improve ab initio predictions by confining the search to locally native-like structures.
residue contact maps have been proposed as an intermediate representation between the primary sequence and the 3d structure of a protein and predicted by a score of different techniques  <cit> .
beyond the prediction of protein structure , contact maps have also been adopted to predict protein folding rates  <cit> , protein disorder  <cit> , and structure/function  <cit> .
most research has focussed on binary contact maps .
it is generally believed that binary maps provide sufficient information to unambiguosly reconstruct native or near-native models  <cit> .
nevertheless, the prediction quality of residue contact map predictors has not improved to satisfactory levels, despite years of attempts  <cit> .
the main reason for this is perhaps that, if it is true that contact maps are roughly equivalent to protein structures, contact map prediction is, ultimately, roughly equivalent to protein structure prediction itself, with all its daunting complexity.
more in detail: it is hard to learn long-range dependencies on contact maps, hence it is especially difficult to predict contacts between residues that have large sequence separations  <cit> ; contact map prediction is an unbalanced problem, with far fewer contacts than non-contacts, especially for long-range contacts, for which the ratio between negative and positive examples can exceed 100; moreover contact map predictors are often ab initio, i.e.
do not exploit information about homologues of known structure .
a more general problem with residue contact maps is that, although it has long been stated that native maps yield correct structures, this is true only at a relatively low resolution .
in this article, we introduce a representation of protein structures based on a generalisation of binary contact maps, multi-class distance maps, and show that it is powerful and predictable with some success.
our tests suggest that exact 4-class maps , can quickly guide a simple optimisation search to nearly perfect models – significantly better than binary contact maps.
we compare reconstructions based on binary and 4-class maps on a non-redundant set of  <dig> proteins of length between  <dig> and  <dig> residues.
the reconstructions based on 4-class maps have an average root mean square deviation  of roughly  <dig> Å and a tm-score of  <dig>  to the native structure .
we develop high-throughput systems for the prediction of 4-class distance maps, which exploit similarity to proteins of known structure, where available, in the form of simple structural frequency profiles from sets of pdb templates.
these predictors are designed so that binary contact maps  can be trivially derived from them.
we train two such predictors, by two-dimensional recursive neural networks: one ab initio, or relying on the sequence and on evolutionary information but no homology information from known structures; one in which homology information is provided as a further input.
we show that even very low sequence similarity to pdb templates  yields more accurate maps than the ab initio predictor.
furthermore, the predicted map is generally more accurate than the maps of the templates, suggesting that the combination of sequence and template information is more informative than templates alone.
although this is not the main focus of this work, we also benchmark both ab initio and template-based multi-class map predictions for protein cα trace reconstruction, using a simple algorithm that relies only on the maps and on basic geometrical rules.
we show that template-based traces are generally more accurate than ab initio ones even when homology is dubious, and that fair to accurate protein structure predictions can be generated for a broad range of homology to structures in the pdb.
RESULTS
in the first subsection of the results we briefly describe the quality of reconstructions of cα traces from native maps, and highlight that multi-class maps give rise to more accurate structures than binary contact maps.
in the following subsection we describe new ab initio and template-based predictive systems for 4-class distance maps, and discuss their performances, and the performances of contact map predictors derived from them.
in a third section we evaluate the contact map predictors thus developed against the methods that took part to the casp <dig> competition.
finally, we briefly gauge the quality of cα traces reconstructed from predicted maps.
reconstruction of cα traces from native maps
the cα trace reconstruction protocol, which we describe in some detail in the methods, is similar to that in  <cit>  and essentially the same as in  <cit> .
we should stress out that in the reconstruction protocol we only enforce the constraints encoded in the maps, plus very general geometrical rules .
if more constraints, for instance about short-range interactions, were taken into account, more accurate structural predictions would likely follow, and our results are to be considered a baseline for the resolution that maps can yield.
in the first set of simulations we compare the quality of reconstructions based on binary maps and multi-class maps for the case in which experimental constraints are known, that is the maps are native.
we use binary maps at  <dig> Å, since these lead to more accurate results than a number of alternative we tested .
in order to assess the quality of predictions, two measures are considered here: root mean square deviation  and tm-score  <cit>  between the predicted structure and the native one.
tm-score assesses the similarity among two protein topologies based on their cα trace, is always in the  <cit>  interval  and is independent on protein size.
two unrelated proteins have on average a tm-score of  <dig> , while tm-scores above  <dig>  are generally associated with structurally similar proteins  <cit> .
for each protein in the test set, we run  <dig> folding simulations and select the best one.
the results for the best simulations are then averaged over all the  <dig> proteins in the set and are reported in table  <dig>  while  <dig> Å maps produce structures at an average rmsd of  <dig> Å to the native, for multi-class maps this decreases to just over  <dig> Å. running more than  <dig> reconstructions decreases both deviations, with those based on  <dig> Å maps plateauing around  <dig> Å and multi-class ones at a near perfect  <dig> Å.
reconstruction algorithm results for the best models derived from binary and multi-class true contact maps.
multi-class distance map prediction
only a small number of algorithms have been developed for the prediction of distance maps or parts thereof .
far more common are methods for the prediction of binary contact maps  <cit> , with distance cutoffs of  <dig> Å,  <dig> Å,  <dig> Å, or  <dig> Å among the most common chosen to define the threshold between a contact and a non-contact.
at the critical assessment of protein structure prediction, casp  <cit> , maps are evaluated with a distance threshold of  <dig> Å between cβ atoms , probably because a distance threshold of  <dig> Å is a good first approximation of physical contact.
nevertheless, there is some evidence that larger thresholds induce an easier reconstruction problem .
there is a wide range of machine learning techniques for predicting contact maps: hidden markov models  <cit> , recursive neural networks  <cit> , multi-layer perceptrons  <cit> , support vector machines  <cit> , and self-organizing maps  <cit>  are just a few.
predictors of contact maps are nearly always ab initio, meaning that they do not directly rely on similarity to proteins of known structure.
in fact, often, much care is taken to try to exclude any detectable similarity between training and test set instances.
the method we present here is based on recursive neural networks, in particular 2-dimensional recursive neural networks .
we predict both binary and 4-class maps.
in the methods section we give a detailed overview of the algorithms and experimental protocol.
the main objective of the experiments is to compare ab initio systems  and template-based systems.
when very reliable pdb information  is available we expect template-based predictions to be substantially better, and in fact, to nearly exactly replicate the maps of the best templates.
more interesting questions are: whether template-based predictions improve on ab initio ones in the so called twilight zone of sequence similarity  and in the midnight zone ; whether, in these same regions, template-based predictions are better than can be obtained by simply copying the map of the best template, or a combination of the maps of the templates.
the base systems we test are multi-class ab intio  and multi-class with templates .
from these systems we also derive  binary map predictions at  <dig> Å for comparison with other predictors.
we label these as 8ai and 8te, for ab initio and template-based predictions, respectively.
percentage of correctly classified residue pairs for the ab initio  and template based  <dig> Å predictor  as a function of sequence identity to the best template.
template sequence identity  <dig> means all proteins that have a best hit template in the identity range [ <dig>  10) %, all is the complete set.
if one focusses only on the contact class, and in particular on contacts for sequence separations of  <cit> ,
<cit>  and [ <dig>  ∞) residues , 8ai performs slightly better than 8te if the best template shows a [ <dig> )% identity to the query, for sequence separations of  <cit>  and  <cit>  residues, but almost identically to 8te for the largest sequence separation class.
it is important to point out that approximately half of all proteins in this identity range have in fact no templates at all.
for all other template identity ranges and sequence separations 8te outperforms 8ai.
for template identities of [ <dig> )% 8te's f <dig> is roughly 50% compared to just over 10% for the ab initio predictor.
similarly, for multi class maps there is never a decrease in performance between mte and mai , in fact there is a small gain of mte over mai even when the best template has a % identity to the query.
m
ai
m
te
percentage of correctly classified residue pairs for the ab initio  and template based multi class predictor  as a function of sequence identity to the best template.
template sequence identity  <dig> means all proteins that have a best hit template in the identity range [ <dig>  10) %, all is the complete set.
in figure  <dig> we report mte and mai q <dig> as a function of the tm-score of the best template against the query's native structure.
a tm-score of  <dig>  or greater is deemed to indicate a clear structural relationship  <cit> .
mte outperforms mai, on average, for tm-scores of  <dig>  and above, while mai performs better if the best template is in the  <dig> – <dig>  region.
the two methods are tied again in the 0– <dig>  region, but in most of these cases psi-blast cannot find any template and both methods are effectively ab initio.
8te and 8ai show the same trends as the 4-class predictors.
prediction q <dig> and q <dig> for regions not covered by the templates are reported in tables  <dig> and  <dig>  in these areas the  <dig> Å predictions are virtually identical for the ab initio and template-based case, while for multi-class predictions there is a small difference, with an average improvement of  <dig> % for mte over mai.
this may be due to the easier contextual propagation in the multi-class case .
identical to table  <dig> except only calculated for non template regions of the map.
m
ai
m
te
identical to table  <dig> except only calculated for non template regions of the map.
tables  <dig> and  <dig> report the comparison of q <dig> and q <dig> between template based predictions and a baseline for  <dig> Å and multi-class respectively.
the baseline simply calculates the distance class for position  from the coordinates in the best template.
this means that the distance between the i-th and j-th residues is assumed to be the same as that between the corresponding  residues in the best template available .
we also tested different baselines in which, instead of just the top template, the top  <dig> templates and all templates were used to get the class by a majority vote among the templates covering each template.
we tested both an unweighed vote and a vote in which each template is weighed by its sequence similarity to the query, cubed.
the latter weighing scheme is identical to the one used to present the templates to the neural networks.
in all cases the baseline is worse than the best hit baseline.
we only report the predictions vs. baseline for the [ <dig> )% templates, since above 30% identity, as expected, the results are undistinguishable.
in this twilight region, where it is non-trivial to extract information from templates, both 8te and mte outperform the baseline by clear margins.
8te's f <dig> on contacts is also higher than the baseline's by roughly 4%, 3% and 1% in the [ <dig> )%, [ <dig> )% and [ <dig> )% template identity ranges, respectively.
percentage of correctly classified residue pairs for 8te when only considering the residues covered by the best template.
baseline is a predictor that copies the contact assignment from the best hit template.
template sequence identity  <dig> means all proteins that have a best hit template in the identity range [ <dig>  10) %.
m
te
percentage of correctly classified residue pairs for mte when only considering residues covered by the best template.
baseline is a predictor that copies the class assignment from the best hit template.
template sequence identity  <dig> means all proteins that have a best hit template in the identity range [ <dig>  10) %
in summary template-based systems outperform the baseline , always improve on ab initio predictions , and even improve slightly, on average, in non-template regions .
this suggests that it is possible to combine information from the sequence and from templates to produce contact map predictions that are more accurate than those that can be produced from either source.
the fact that improvements over ab initio occur down to essentially junk templates , seems to suggest that information beyond genuine homology can still be harnessed.
when we applied a similar technique for exploiting template information to predict secondary structure and relative solvent accessibility  <cit>  we only observed gains for higher  sequence identities.
one possible reason for this difference is that ab initio predictions of secondary structure and solvent accessibility are, on average, quite accurate, while ab initio predictions of contact maps are fairly poor, especially for the contact class.
finally, we looked at prediction accuracy for different classes of proteins, specifically all-alpha vs. all-beta.
while all-alpha proteins are predicted slightly more accurately ab initio, the difference becomes marginal  when templates are introduced.
contact map prediction for casp <dig> targets
we also tested 8ai and 8te on the casp <dig> targets  <cit> , for comparison with the state of the art.
comparisons at casp <dig> were run with numerous restrictions, ultimately resulting in only  <dig> targets being considered, only contacts at a sequence separation of  <dig> or more residues being assessed  and within these, only the l/ <dig> top ranked contacts  being considered.
although we do not mean to question the merit of the ranking , we here substantially relax its criteria for two reasons: to be able to assess our predictors also on targets for which templates were available, given that 8te is precisely designed for these; to focus on all sequence separations , and on whole maps rather than a very small number of contacts.
we measure performances by f <dig>  on the contact class.
we report the results for sequence separations of  <dig> to  <dig> residues,  <dig> to  <dig> residues, and  <dig> residues or greater, in tables  <dig>   <dig> and  <dig> respectively.
in all of them we report results for all the  <dig> targets, but also results split by sequence identity  to the best psi-blast template in the pdb as available on april  <dig>  <dig>  just before the beginning of the casp <dig> experiment.
results for the casp <dig> targets: sequence separations of  <dig> to  <dig> residues, inclusive.
comparison between our two predictors  and the predictors ranked highest at casp <dig>  we report f <dig> for the contact class, as a function of sequence similarity to the best psi-blast template.
predictions are from the casp <dig> web site.
profcon is in italics because it predicted  <dig> out of  <dig> maps, hence its results are not exactly comparable.
in bold is the highest f <dig> of all predictors, excluding profcon, and excluding 8te, which uses templates and has the highest f <dig> in all ranges except [ <dig> )% where it is slightly worse than only 8ai.
results for the casp <dig> targets: sequence separations of  <dig> to  <dig> residues, inclusive.
comparison between our two predictors  and the predictors ranked highest at casp <dig>  we report f <dig> for the contact class, as a function of sequence similarity to the best psi-blast template.
predictions are from the casp <dig> web site.
profcon is in italics because it predicted  <dig> out of  <dig> maps, hence its results are not exactly comparable.
in bold is the highest f <dig> of all predictors, excluding profcon, and excluding 8te, which uses templates and has the highest f <dig> in all ranges except [ <dig> )% where it is slightly worse than only 8ai.
results for the casp <dig> targets: sequence separations  <dig> residues or more, inclusive.
comparison between our two predictors  and the predictors ranked highest at casp <dig>  we report f <dig> for the contact class, as a function of sequence similarity to the best psi-blast template.
predictions are from the casp <dig> web site.
profcon is in italics because it predicted  <dig> out of  <dig> maps, hence its results are not exactly comparable.
in bold is the highest f <dig> of all predictors, excluding profcon, and excluding 8te, which uses templates and has the highest f <dig> in all ranges except [ <dig> )% where it performs worse than some of the predictors.
the first conclusion we can derive from the tables is that our ab initio predictor  is state-of-the-art.
in the  <dig> to  <dig> and  <dig> to  <dig> residue separation regions it outperforms all other predictors for which a direct comparison is possible both on all  <dig> targets and on the  <dig> targets for which psi-blast only finds pdb hits at 10% sequence identity or less.
for template identity of [ <dig> )% in the  <cit>  sequence separation table profcon  <cit>  has a slightly higher f <dig>  but the results are not directly comparable because profcon did not predict  <dig> of the  <dig> proteins in this bin.
in the [ <dig>  ∞) separation region 8ai performs best in  <dig> of the  <dig> bins, and only slightly worse than svmcon  <cit>   on the  <dig> targets, and slightly worse than svmcon  and than sam_t <dig>  <cit>   on the  <dig> targets with [ <dig> )% identity psi-blast templates.
8te's performances on the  <dig> casp <dig> targets essentially confirm what we found on the larger s <dig> set: there is a small decrease in f <dig> for the [ <dig> )% template identity class with respect to 8ai , respectively); overall the predictions are far more accurate than those of the other predictors, none of which exploits templates; in the the [ <dig> )% template identity class there is already a very large gain compared to the second best  – 8ai being the second best in the first two classes, and svmcon in the third one).
because of the way our predictor is designed accuracy ≈ coverage ≈ f <dig> .
for the other algorithms the trade-off between coverage and accuracy varies with some predicting more contacts  thus showing a higher coverage and lower accuracy, and the others being more balanced.
overall only in a handful of cases does a method's coverage exceed its accuracy by more than  <dig> to 1: sam_t <dig> for  <cit>  separation ; sam_t <dig> and svmcon for 24+ separation .
the opposite happens only once: possum for 24+ separation .
modelling protein structures from predicted maps
in figure  <dig>  the average rmsd vs sequence length is shown for models for set s <dig> derived from true 4-class contact maps , from mte maps  and from mai maps , together with the baseline .
the baseline represents a structure collapsed into its center of mass.
note that no templates are allowed that show a sequence identity greater than 95% to the query in order to prevent a structure from being reconstructed from its own pdb file.
hence, the mte results are based on a mixture of good, bad and no templates, akin to the distribution one would expect when presented with a protein sequence that is not in the pdb.
the distribution of template identity for s <dig>  resembles closely the one for the training/testing set, reported in figure  <dig>
in figure  <dig> we report the quality of reconstructions as a function of the tm-score between the best template and the query.
we measure quality as the fraction of the native structure's residues that are modelled within  <dig> Å. when the template is perfect to near-perfect  the reconstruction from the map is, on average, very slighly worse  than the template.
this is not surprising, as even from native maps model quality levels off at a tm-score of  <dig> .
when the tm-score between the best template and the native structure is between  <dig>  and  <dig> , models built from 4-class maps are slightly better than the templates , and substantially better  when the best template has a tm-score under  <dig> .
if instead of residue coverage at  <dig> Å we measure the tm-score of the model and of the best template vs. the native structure  we obtain broadly similar results, but slightly less favourable for the models, with results now undistinguishable in the  <dig> – <dig>  region and still slightly worse in the  <dig> – <dig> one.
we can broadly conclude that, if good templates are available, reconstructions from 4-class maps are only about as good as them in the area covered by the template.
it is also important to note that the results are an average of  <dig> reconstructions.
if more reconstructions were run and, especially, if these were ranked effectively, the results would improve considerably.
the average reconstruction rmsd for mte is  <dig>  Å and the average tm-score  <dig>  .
if the best of the  <dig> reconstructions is picked, these improve to  <dig>  Å and  <dig> , respectively.
tested on both ab initio and template-based 4-class maps, our results show that template-based reconstructions are generally more accurate than ab initio ones even when homology is dubious.
for sequence similarity above 30% the predictions' tm-score is on average slightly above  <dig> , is  <dig>  in the 20–30% interval, and  <dig>  in the region below 20%.
if reconstruction performances are measured on the s <dig> set without allowing homology information at any stage  the average tm-score is  <dig> , with  <dig> of the  <dig> structures above a tm-score of  <dig> .
m
ai
m
te
reconstruction algorithm results for models derived from multi-class predicted contact maps with  and without  allowing homology information.
note that, since no templates are allowed that show a sequence identity greater than 95% to the query, the mte results are based on a mixture of good, bad and no templates .
the reported values are the average over the  <dig> runs of simulated annealing.
CONCLUSIONS
in this work we have described a machine learning pipeline for high-throughput prediction of protein contact maps, and have introduced a number of novel algorithmic ideas.
based on the observation that protein binary contact maps are lossy representations of the structure and yield only relatively low-resolution models, we have introduced multi-class maps, and shown that, via a simple simulated annealing protocol and based on  <dig> reconstructions, these lead to much more accurate models than binary maps, with an average rmsd to the native structure of just over  <dig> Å and a tm-score of  <dig> .
extending on ideas we have developed for predictors of secondary structure and solvent accessibility  <cit>  we have presented systems for the prediction of binary and 4-class maps that use structural templates from the pdb.
4-class maps lead to a more balanced prediction problem than binary ones.
although it is unclear whether because of this, or because of the nature of the constraints encoded into the maps, template-based systems for the prediction of 4-class maps we tested are capable of exploiting both sequence and structure information even in cases of dubious homology, significantly improving over their ab initio counterpart well into and below the twilight zone of sequence identity.
4-class map predictions are also far more accurate than the maps of the best templates for all the twilight and midnight zone of sequence identity.
this also partly holds for  <dig> Å maps derived from 4-class predictors.
furthermore, we compared our  <dig> Å predictions with the best systems at the last casp <dig>  and showed that they are state-of-the-art, and, again, that even very low sequence similarity templates  induce far better contact maps that all the ab initio predictors that performed best at casp <dig>
finally we have shown that template-based predictions of 4-class maps lead to fair predictions of protein structures, with an average tm-score of  <dig>  or higher to the native when good templates are available , and of  <dig>  in the [20%, 30%) identity region.
predictions for lower sequence identities to structural templates are still generally poor, at an average tm-score of  <dig> .
nevertheless, it is important to note how: 1) the reconstruction protocol we use is basic, and would be likely improved by taking into account more than the interactions contained in the maps; 2) the component for homology detection in this study is basic , and entirely modular, in that it may be substituted by any other method that finds templates without substantially altering the pipeline.
whether more subtle homology detection or fold recognition components could be substituted to psi-blast, with or without retraining the underlying machine learning systems, is the focus of our current studies.
the overall pipeline, including the template-based component, is available at the url: .
protein structure predictions are based on 4-class maps and templates are automatically provided to the pipeline when available.

 although a protein can be first characterised by its amino acid sequence, most proteins fold into three-dimensional structures that encode their function. genomics projects leave us with millions of protein sequences, currently ≈ × of which only a small fraction have their 3d structure experimentally determined. in the future, we might devolve upon structural genomics projects the task to bridge the huge gap between sequence and structure. so far, though, even high throughput pipelines have not been able to make a dent in the massive ratio between known sequences and structures, and a large fraction of structures are found to be unsuitable for structural determination with the methods available. therefore, computational protein structure prediction remains an irreplaceable instrument for the exploration of sequence-structure-function relationships. moreover, even if the structural genomics goal of providing a model for each fold is achieved, algorithms that are able to model protein structures based on putative homologues will become even more important to fully harness this novel knowledge. this is especially important for analyses at genomic or inter-genomic level, where informative structural models need to be generated for thousands of gene products in reasonable amounts of time. template-based algorithms for protein structure prediction typically adopt heuristics based on sequence and/or structural similarity to model the unknown structure of a protein based on known structures that are fathomed to be homologous to it. automating the modelling process is not trivial: there are several stages and critical points in the design and for some of them manual intervention is at least helpful. the use of multiple templates is also an open question. the accuracy of template-based techniques strongly depends on the amount of detectable similarity between query and templates, thus preventing the reliable application of these methods to a significant fraction of unannotated proteins. this is the realm of the so called ab initio or de novo protein structure prediction, where models are predicted not relying on similarity to proteins of known structure. ab initio techniques are not nearly as accurate as those based on templates, but the design in this case is generally somewhat simpler. a system for the prediction of protein structures ab initio is usually composed of two elements: an algorithm to search the space of possible protein configurations to minimise some cost function; the cost function itself, composed of various restraints being either derived from physical laws, from structural features predicted by machine learning or other kinds of statistical system, or possibly constraints obtained from experiments. fragment-based algorithms, that use fragments of proteins of known structure to reconstruct the complete structure of the target protein, have shown potential to improve ab initio predictions by confining the search to locally native-like structures. residue contact maps have been proposed as an intermediate representation between the primary sequence and the 3d structure of a protein and predicted by a score of different techniques. beyond the prediction of protein structure, contact maps have also been adopted to predict protein folding rates, protein disorder, and structure/function. most research has focussed on binary contact maps. it is generally believed that binary maps provide sufficient information to unambiguosly reconstruct native or near-native models. nevertheless, the prediction quality of residue contact map predictors has not improved to satisfactory levels, despite years of attempts. the main reason for this is perhaps that, if it is true that contact maps are roughly equivalent to protein structures, contact map prediction is, ultimately, roughly equivalent to protein structure prediction itself, with all its daunting complexity. more in detail: it is hard to learn long-range dependencies on contact maps, hence it is especially difficult to predict contacts between residues that have large sequence separations; contact map prediction is an unbalanced problem, with far fewer contacts than non-contacts, especially for long-range contacts, for which the ratio between negative and positive examples can exceed 100; moreover contact map predictors are often ab initio, i.e. do not exploit information about homologues of known structure. a more general problem with residue contact maps is that, although it has long been stated that native maps yield correct structures, this is true only at a relatively low resolution. in this article, we introduce a representation of protein structures based on a generalisation of binary contact maps, multi-class distance maps, and show that it is powerful and predictable with some success. our tests suggest that exact 4-class maps, can quickly guide a simple optimisation search to nearly perfect models – significantly better than binary contact maps. we compare reconstructions based on binary and 4-class maps on a non-redundant set of proteins of length between and residues. the reconstructions based on 4-class maps have an average root mean square deviation of roughly Å and a tm-score of to the native structure. we develop high-throughput systems for the prediction of 4-class distance maps, which exploit similarity to proteins of known structure, where available, in the form of simple structural frequency profiles from sets of pdb templates. these predictors are designed so that binary contact maps can be trivially derived from them. we train two such predictors, by two-dimensional recursive neural networks: one ab initio, or relying on the sequence and on evolutionary information but no homology information from known structures; one in which homology information is provided as a further input. we show that even very low sequence similarity to pdb templates yields more accurate maps than the ab initio predictor. furthermore, the predicted map is generally more accurate than the maps of the templates, suggesting that the combination of sequence and template information is more informative than templates alone. although this is not the main focus of this work, we also benchmark both ab initio and template-based multi-class map predictions for protein cα trace reconstruction, using a simple algorithm that relies only on the maps and on basic geometrical rules. we show that template-based traces are generally more accurate than ab initio ones even when homology is dubious, and that fair to accurate protein structure predictions can be generated for a broad range of homology to structures in the pdb.  in the first subsection of the results we briefly describe the quality of reconstructions of cα traces from native maps, and highlight that multi-class maps give rise to more accurate structures than binary contact maps. in the following subsection we describe new ab initio and template-based predictive systems for 4-class distance maps, and discuss their performances, and the performances of contact map predictors derived from them. in a third section we evaluate the contact map predictors thus developed against the methods that took part to the casp competition. finally, we briefly gauge the quality of cα traces reconstructed from predicted maps. reconstruction of cα traces from native maps the cα trace reconstruction protocol, which we describe in some detail in the methods, is similar to that in and essentially the same as in. we should stress out that in the reconstruction protocol we only enforce the constraints encoded in the maps, plus very general geometrical rules. if more constraints, for instance about short-range interactions, were taken into account, more accurate structural predictions would likely follow, and our results are to be considered a baseline for the resolution that maps can yield. in the first set of simulations we compare the quality of reconstructions based on binary maps and multi-class maps for the case in which experimental constraints are known, that is the maps are native. we use binary maps at Å, since these lead to more accurate results than a number of alternative we tested. in order to assess the quality of predictions, two measures are considered here: root mean square deviation and tm-score between the predicted structure and the native one. tm-score assesses the similarity among two protein topologies based on their cα trace, is always in the interval and is independent on protein size. two unrelated proteins have on average a tm-score of, while tm-scores above are generally associated with structurally similar proteins. for each protein in the test set, we run folding simulations and select the best one. the results for the best simulations are then averaged over all the proteins in the set and are reported in table while Å maps produce structures at an average rmsd of Å to the native, for multi-class maps this decreases to just over Å. running more than reconstructions decreases both deviations, with those based on Å maps plateauing around Å and multi-class ones at a near perfect Å. reconstruction algorithm results for the best models derived from binary and multi-class true contact maps. multi-class distance map prediction only a small number of algorithms have been developed for the prediction of distance maps or parts thereof. far more common are methods for the prediction of binary contact maps, with distance cutoffs of Å, Å, Å, or Å among the most common chosen to define the threshold between a contact and a non-contact. at the critical assessment of protein structure prediction, casp, maps are evaluated with a distance threshold of Å between cβ atoms, probably because a distance threshold of Å is a good first approximation of physical contact. nevertheless, there is some evidence that larger thresholds induce an easier reconstruction problem. there is a wide range of machine learning techniques for predicting contact maps: hidden markov models, recursive neural networks, multi-layer perceptrons, support vector machines, and self-organizing maps are just a few. predictors of contact maps are nearly always ab initio, meaning that they do not directly rely on similarity to proteins of known structure. in fact, often, much care is taken to try to exclude any detectable similarity between training and test set instances. the method we present here is based on recursive neural networks, in particular 2-dimensional recursive neural networks. we predict both binary and 4-class maps. in the methods section we give a detailed overview of the algorithms and experimental protocol. the main objective of the experiments is to compare ab initio systems and template-based systems. when very reliable pdb information is available we expect template-based predictions to be substantially better, and in fact, to nearly exactly replicate the maps of the best templates. more interesting questions are: whether template-based predictions improve on ab initio ones in the so called twilight zone of sequence similarity and in the midnight zone; whether, in these same regions, template-based predictions are better than can be obtained by simply copying the map of the best template, or a combination of the maps of the templates. the base systems we test are multi-class ab intio and multi-class with templates. from these systems we also derive binary map predictions at Å for comparison with other predictors. we label these as 8ai and 8te, for ab initio and template-based predictions, respectively. percentage of correctly classified residue pairs for the ab initio and template based Å predictor as a function of sequence identity to the best template. template sequence identity means all proteins that have a best hit template in the identity range [ 10) %, all is the complete set. if one focusses only on the contact class, and in particular on contacts for sequence separations of, and [ ∞) residues, 8ai performs slightly better than 8te if the best template shows a [ )% identity to the query, for sequence separations of and residues, but almost identically to 8te for the largest sequence separation class. it is important to point out that approximately half of all proteins in this identity range have in fact no templates at all. for all other template identity ranges and sequence separations 8te outperforms 8ai. for template identities of [ )% 8te's f is roughly 50% compared to just over 10% for the ab initio predictor. similarly, for multi class maps there is never a decrease in performance between mte and mai, in fact there is a small gain of mte over mai even when the best template has a % identity to the query. m ai m te percentage of correctly classified residue pairs for the ab initio and template based multi class predictor as a function of sequence identity to the best template. template sequence identity means all proteins that have a best hit template in the identity range [ 10) %, all is the complete set. in figure we report mte and mai q as a function of the tm-score of the best template against the query's native structure. a tm-score of or greater is deemed to indicate a clear structural relationship. mte outperforms mai, on average, for tm-scores of and above, while mai performs better if the best template is in the – region. the two methods are tied again in the 0– region, but in most of these cases psi-blast cannot find any template and both methods are effectively ab initio. 8te and 8ai show the same trends as the 4-class predictors. prediction q and q for regions not covered by the templates are reported in tables and in these areas the Å predictions are virtually identical for the ab initio and template-based case, while for multi-class predictions there is a small difference, with an average improvement of % for mte over mai. this may be due to the easier contextual propagation in the multi-class case. identical to table except only calculated for non template regions of the map. m ai m te identical to table except only calculated for non template regions of the map. tables and report the comparison of q and q between template based predictions and a baseline for Å and multi-class respectively. the baseline simply calculates the distance class for position from the coordinates in the best template. this means that the distance between the i-th and j-th residues is assumed to be the same as that between the corresponding residues in the best template available. we also tested different baselines in which, instead of just the top template, the top templates and all templates were used to get the class by a majority vote among the templates covering each template. we tested both an unweighed vote and a vote in which each template is weighed by its sequence similarity to the query, cubed. the latter weighing scheme is identical to the one used to present the templates to the neural networks. in all cases the baseline is worse than the best hit baseline. we only report the predictions vs. baseline for the [ )% templates, since above 30% identity, as expected, the results are undistinguishable. in this twilight region, where it is non-trivial to extract information from templates, both 8te and mte outperform the baseline by clear margins. 8te's f on contacts is also higher than the baseline's by roughly 4%, 3% and 1% in the [ )%, [ )% and [ )% template identity ranges, respectively. percentage of correctly classified residue pairs for 8te when only considering the residues covered by the best template. baseline is a predictor that copies the contact assignment from the best hit template. template sequence identity means all proteins that have a best hit template in the identity range [ 10) %. m te percentage of correctly classified residue pairs for mte when only considering residues covered by the best template. baseline is a predictor that copies the class assignment from the best hit template. template sequence identity means all proteins that have a best hit template in the identity range [ 10) % in summary template-based systems outperform the baseline, always improve on ab initio predictions, and even improve slightly, on average, in non-template regions. this suggests that it is possible to combine information from the sequence and from templates to produce contact map predictions that are more accurate than those that can be produced from either source. the fact that improvements over ab initio occur down to essentially junk templates, seems to suggest that information beyond genuine homology can still be harnessed. when we applied a similar technique for exploiting template information to predict secondary structure and relative solvent accessibility we only observed gains for higher sequence identities. one possible reason for this difference is that ab initio predictions of secondary structure and solvent accessibility are, on average, quite accurate, while ab initio predictions of contact maps are fairly poor, especially for the contact class. finally, we looked at prediction accuracy for different classes of proteins, specifically all-alpha vs. all-beta. while all-alpha proteins are predicted slightly more accurately ab initio, the difference becomes marginal when templates are introduced. contact map prediction for casp targets we also tested 8ai and 8te on the casp targets, for comparison with the state of the art. comparisons at casp were run with numerous restrictions, ultimately resulting in only targets being considered, only contacts at a sequence separation of or more residues being assessed and within these, only the l/ top ranked contacts being considered. although we do not mean to question the merit of the ranking, we here substantially relax its criteria for two reasons: to be able to assess our predictors also on targets for which templates were available, given that 8te is precisely designed for these; to focus on all sequence separations, and on whole maps rather than a very small number of contacts. we measure performances by f on the contact class. we report the results for sequence separations of to residues, to residues, and residues or greater, in tables and respectively. in all of them we report results for all the targets, but also results split by sequence identity to the best psi-blast template in the pdb as available on april just before the beginning of the casp experiment. results for the casp targets: sequence separations of to residues, inclusive. comparison between our two predictors and the predictors ranked highest at casp we report f for the contact class, as a function of sequence similarity to the best psi-blast template. predictions are from the casp web site. profcon is in italics because it predicted out of maps, hence its results are not exactly comparable. in bold is the highest f of all predictors, excluding profcon, and excluding 8te, which uses templates and has the highest f in all ranges except [ )% where it is slightly worse than only 8ai. results for the casp targets: sequence separations of to residues, inclusive. comparison between our two predictors and the predictors ranked highest at casp we report f for the contact class, as a function of sequence similarity to the best psi-blast template. predictions are from the casp web site. profcon is in italics because it predicted out of maps, hence its results are not exactly comparable. in bold is the highest f of all predictors, excluding profcon, and excluding 8te, which uses templates and has the highest f in all ranges except [ )% where it is slightly worse than only 8ai. results for the casp targets: sequence separations residues or more, inclusive. comparison between our two predictors and the predictors ranked highest at casp we report f for the contact class, as a function of sequence similarity to the best psi-blast template. predictions are from the casp web site. profcon is in italics because it predicted out of maps, hence its results are not exactly comparable. in bold is the highest f of all predictors, excluding profcon, and excluding 8te, which uses templates and has the highest f in all ranges except [ )% where it performs worse than some of the predictors. the first conclusion we can derive from the tables is that our ab initio predictor is state-of-the-art. in the to and to residue separation regions it outperforms all other predictors for which a direct comparison is possible both on all targets and on the targets for which psi-blast only finds pdb hits at 10% sequence identity or less. for template identity of [ )% in the sequence separation table profcon has a slightly higher f but the results are not directly comparable because profcon did not predict of the proteins in this bin. in the [ ∞) separation region 8ai performs best in of the bins, and only slightly worse than svmcon on the targets, and slightly worse than svmcon and than sam_t on the targets with [ )% identity psi-blast templates. 8te's performances on the casp targets essentially confirm what we found on the larger s set: there is a small decrease in f for the [ )% template identity class with respect to 8ai, respectively); overall the predictions are far more accurate than those of the other predictors, none of which exploits templates; in the the [ )% template identity class there is already a very large gain compared to the second best – 8ai being the second best in the first two classes, and svmcon in the third one). because of the way our predictor is designed accuracy ≈ coverage ≈ f. for the other algorithms the trade-off between coverage and accuracy varies with some predicting more contacts thus showing a higher coverage and lower accuracy, and the others being more balanced. overall only in a handful of cases does a method's coverage exceed its accuracy by more than to 1: sam_t for separation; sam_t and svmcon for 24+ separation. the opposite happens only once: possum for 24+ separation. modelling protein structures from predicted maps in figure the average rmsd vs sequence length is shown for models for set s derived from true 4-class contact maps, from mte maps and from mai maps, together with the baseline. the baseline represents a structure collapsed into its center of mass. note that no templates are allowed that show a sequence identity greater than 95% to the query in order to prevent a structure from being reconstructed from its own pdb file. hence, the mte results are based on a mixture of good, bad and no templates, akin to the distribution one would expect when presented with a protein sequence that is not in the pdb. the distribution of template identity for s resembles closely the one for the training/testing set, reported in figure in figure we report the quality of reconstructions as a function of the tm-score between the best template and the query. we measure quality as the fraction of the native structure's residues that are modelled within Å. when the template is perfect to near-perfect the reconstruction from the map is, on average, very slighly worse than the template. this is not surprising, as even from native maps model quality levels off at a tm-score of. when the tm-score between the best template and the native structure is between and, models built from 4-class maps are slightly better than the templates, and substantially better when the best template has a tm-score under. if instead of residue coverage at Å we measure the tm-score of the model and of the best template vs. the native structure we obtain broadly similar results, but slightly less favourable for the models, with results now undistinguishable in the – region and still slightly worse in the – one. we can broadly conclude that, if good templates are available, reconstructions from 4-class maps are only about as good as them in the area covered by the template. it is also important to note that the results are an average of reconstructions. if more reconstructions were run and, especially, if these were ranked effectively, the results would improve considerably. the average reconstruction rmsd for mte is Å and the average tm-score. if the best of the reconstructions is picked, these improve to Å and, respectively. tested on both ab initio and template-based 4-class maps, our results show that template-based reconstructions are generally more accurate than ab initio ones even when homology is dubious. for sequence similarity above 30% the predictions' tm-score is on average slightly above, is in the 20–30% interval, and in the region below 20%. if reconstruction performances are measured on the s set without allowing homology information at any stage the average tm-score is, with of the structures above a tm-score of. m ai m te reconstruction algorithm results for models derived from multi-class predicted contact maps with and without allowing homology information. note that, since no templates are allowed that show a sequence identity greater than 95% to the query, the mte results are based on a mixture of good, bad and no templates. the reported values are the average over the runs of simulated annealing.  in this work we have described a machine learning pipeline for high-throughput prediction of protein contact maps, and have introduced a number of novel algorithmic ideas. based on the observation that protein binary contact maps are lossy representations of the structure and yield only relatively low-resolution models, we have introduced multi-class maps, and shown that, via a simple simulated annealing protocol and based on reconstructions, these lead to much more accurate models than binary maps, with an average rmsd to the native structure of just over Å and a tm-score of. extending on ideas we have developed for predictors of secondary structure and solvent accessibility we have presented systems for the prediction of binary and 4-class maps that use structural templates from the pdb. 4-class maps lead to a more balanced prediction problem than binary ones. although it is unclear whether because of this, or because of the nature of the constraints encoded into the maps, template-based systems for the prediction of 4-class maps we tested are capable of exploiting both sequence and structure information even in cases of dubious homology, significantly improving over their ab initio counterpart well into and below the twilight zone of sequence identity. 4-class map predictions are also far more accurate than the maps of the best templates for all the twilight and midnight zone of sequence identity. this also partly holds for Å maps derived from 4-class predictors. furthermore, we compared our Å predictions with the best systems at the last casp and showed that they are state-of-the-art, and, again, that even very low sequence similarity templates induce far better contact maps that all the ab initio predictors that performed best at casp finally we have shown that template-based predictions of 4-class maps lead to fair predictions of protein structures, with an average tm-score of or higher to the native when good templates are available, and of in the [20%, 30%) identity region. predictions for lower sequence identities to structural templates are still generally poor, at an average tm-score of. nevertheless, it is important to note how: 1) the reconstruction protocol we use is basic, and would be likely improved by taking into account more than the interactions contained in the maps; 2) the component for homology detection in this study is basic, and entirely modular, in that it may be substituted by any other method that finds templates without substantially altering the pipeline. whether more subtle homology detection or fold recognition components could be substituted to psi-blast, with or without retraining the underlying machine learning systems, is the focus of our current studies. the overall pipeline, including the template-based component, is available at the url:. protein structure predictions are based on 4-class maps and templates are automatically provided to the pipeline when available. 
some approaches to protein structure prediction, especially ab initio ones, rely to some extent on the prediction of residue contact maps. although it has been shown that exact contact maps generally yield correct three-dimensional structures, this is true only at a relatively low resolution. another known weakness of contact maps is that they are generally predicted ab initio, that is not exploiting information about potential homologues of known structure. we show that cα trace reconstructions based on 4-class native maps are significantly better than those from residue contact maps. we also extract binary residue contact maps at an Å threshold from the 4-class predictors and show that the template-based version is also more accurate than the best template and consistently better than the ab initio one, down to very low levels of sequence identity to structural templates. predictions of protein structures and Å contact maps based on the multi-class distance map predictors described in this paper are freely available to academic users at the url. furthermore, we test both ab-initio and template-based Å predictions on the casp targets using a pre-casp pdb, and find that both predictors are state-of-the-art, with the template-based one far outperforming the best casp systems if templates with sequence identity to the query of 10% or better are available. we then build two predictors of 4-class maps based on recursive neural networks: one ab initio, or relying on the sequence and on evolutionary information; one template-based, or in which homology information to known structures is provided as a further input. we show that template-based predictions by recursive neural networks are consistently better than the best template and than a number of combinations of the best available templates. we show that virtually any level of sequence similarity to structural templates yields more accurate 4-class maps than the ab initio predictor. although this is not the main focus of this paper we also report on reconstructions of cα traces based on both ab initio and template-based 4-class map predictions, showing that the latter are generally more accurate even when homology is dubious. accurate predictions of multi-class maps may provide valuable constraints for improved ab initio and template-based prediction of protein structures, naturally incorporate multiple templates, and yield state-of-the-art binary maps. we introduce a new class of distance restraints for protein structures: multi-class distance maps. prediction of protein structures from their sequences is still one of the open grand challenges of computational biology.
 prediction of protein structures from their sequences is still one of the open grand challenges of computational biology. some approaches to protein structure prediction, especially ab initio ones, rely to some extent on the prediction of residue contact maps. residue contact map predictions have been assessed at the casp competition for several years now. although it has been shown that exact contact maps generally yield correct three-dimensional structures, this is true only at a relatively low resolution. another known weakness of contact maps is that they are generally predicted ab initio, that is not exploiting information about potential homologues of known structure.  we introduce a new class of distance restraints for protein structures: multi-class distance maps. we show that cα trace reconstructions based on 4-class native maps are significantly better than those from residue contact maps. we then build two predictors of 4-class maps based on recursive neural networks: one ab initio, or relying on the sequence and on evolutionary information; one template-based, or in which homology information to known structures is provided as a further input. we show that virtually any level of sequence similarity to structural templates yields more accurate 4-class maps than the ab initio predictor. we show that template-based predictions by recursive neural networks are consistently better than the best template and than a number of combinations of the best available templates. we also extract binary residue contact maps at an Å threshold from the 4-class predictors and show that the template-based version is also more accurate than the best template and consistently better than the ab initio one, down to very low levels of sequence identity to structural templates. furthermore, we test both ab-initio and template-based Å predictions on the casp targets using a pre-casp pdb, and find that both predictors are state-of-the-art, with the template-based one far outperforming the best casp systems if templates with sequence identity to the query of 10% or better are available. although this is not the main focus of this paper we also report on reconstructions of cα traces based on both ab initio and template-based 4-class map predictions, showing that the latter are generally more accurate even when homology is dubious.  accurate predictions of multi-class maps may provide valuable constraints for improved ab initio and template-based prediction of protein structures, naturally incorporate multiple templates, and yield state-of-the-art binary maps. predictions of protein structures and Å contact maps based on the multi-class distance map predictors described in this paper are freely available to academic users at the url. 