The Graph Theory and the Protein Universe: selecting the close-to-the-native structures within a model decoy set

Proteins are complex systems as the Anfinsen\u2019s thermodynamic hypothesis highlights. Their complexity hampers an analytical solution to the protein folding problem, so to say how to predict the tertiary structure of the proteins from the residue sequence or primary structure. However nature presently provides us with over 40000 protein structures known with atomic resolution suggesting that possibly heuristic methods may help us in unraveling protein folding. Indeed several methods have been described to address this point: how to generalize from known examples of folding predictive methods suited to compute the three-dimensional protein structure. This is stressed to the point the automatic servers nowadays may generate 3D structures as soon as genomes are sequenced contributing several millions of putative structures that however need to be validated in most of the cases. The question then arises: how to select good structures among many different models generated by different methods starting from the same protein sequence? In protein structure prediction potential energy functions are adopted both to compute \u201cab initio\u201d models and to score threading candidates. It is however known that small intrinsic errors in these models can lead to a high number of erroneous structures endowed with values of conformational energy lower than the native one (Filkenstein 1997). Decreasing the number of false candidates among the best scoring structures is therefore a major goal in protein structure prediction, and several types of energy functions and decoy sets have been described in order to address this issue (Park et al., 1997; Felts et al., 2002; Hardin et al., 2002; Tsai et al., 2003). The notion that the protein native structure is endowed with the lowest free energy with respect to all the other conformations may help us to develop a filter procedure. A very stringent test for reliability is when the adopted energy function is able to compute lower conformational energies for native and near native conformations with respect to non-native ones. To test the capabilities of new scoring functions, sets of \u201cgood decoys\u201d were developed (Tsai et al. (2003)). These sets routinely contain protein-like structures for a wide variety of different structural domains to avoid over-fitting; including conformations close to the native structure (RMSD