BACKGROUND
this article deals with the problem of predicting critical amino acid residues for a given protein's function, i.e., those residues that, if mutated, result in a loss of protein function by the lack of proper folding and/or the inability to perform a biochemical function .
a common approach to this problem consists of aligning multiple orthologous protein sequences, and predicting as critical residues the most highly conserved ones.
this approach is known as the phylogenetic approach, and requires that a significant number of distinct protein sequences be aligned.
this approach also assumes that the aligned sequences from different species serve the same function in the different species.
however, for an increasing number of proteins studied by the structural genomic consortium, a different trend is observed: for a given protein there may be a lack of a significant number of homologous sequences, whereas the three-dimensional structure  of the protein of interest may already have been described.
for this set of proteins, having an accurate way to identify critical residues in the absence of known orthologues – i.e., simply from the protein's three-dimensional structure – may be valuable.
identifying critical residues from protein structures can also be extended to those proteins for which there are a significant number of homologous sequences  <cit> .
furthermore, the prediction of critical residues from protein structures has been shown to be useful in validating protein structure predictions  <cit> .
over the past few decades, network analyses have been used to model diverse systems such as the world wide web, social systems, and biological systems   <cit> .
only very recently has such an approach been used to predict critical amino acids from protein structures .
by definition, a network is composed of two sets: a set of vertices and a set of edges .
a protein can be modelled in a network as follows: each vertex of the network represents an amino acid residue, and each edge represents a chemical interaction between any two amino acid residues.
in the particular case in which the 3d structure of the protein is known, it can be assumed, for the sake of the model, that there is a chemical interaction between two amino acids if they are sufficiently close to one another .
this gives a way of building a network of amino acid interactions , with the obvious caveat that the accuracy of such a model will be affected by the accuracy of the assumption of chemical interactions between different residues.
previous studies have related specific centrality measurements of these amino acid interaction networks to the tolerance for replacement  of the various amino acids within the network.
in particular, the most traversed vertices  have been shown to be important for folding  <cit>  and for the functions of the modelled proteins  <cit> .
these vertices, when detected from several structures for a given protein, relate more accurately with critical residues than the most conserved residues detected from some phylogenetic approaches  <cit> .
hence, betweenness, a network centrality measurement, is associated with the capacity of any given amino acid residue to play a critical role in a protein's function.
these results indicate that critical residues are central to the interactions among the residues in a protein structure.
however, whether or not the experimentally determined critical residues are best predicted by measures of betweenness, as opposed to any other centrality measurement, has not been tested.
evaluation of other centrality measurements may also help to understand the significance of the observed relationship.
in the current work we compare five different network centrality measurements, applying them to the study of the structure/function relationship of proteins.
previous studies on the structure/function relationship of proteins have shown that critical residues tend to display specific geometrical characteristics, such as distorted dihedral angles or central location, buried within the proteins' cores .
however, whether these geometrical properties are related to network centrality  has not been studied.
in this work, we analyze some of these relationships, as well.
it is possible to define several centrality measurements at a vertex p of a network.
some of these centrality measurements have already been used for modelling different systems.
one of the most direct and widely used centrality measurements is the connectivity cp , which is the number of neighbours of p .
another, the clustering coefficient  <cit> , defined by 2np/cp, where np is the number of connections between the neighbours of p, estimates the degree of interconnectivity among the neighbours of p. these two measurements are local, in the sense that their values only depend on the vertex p and on its neighbours.
there are also global centrality measurements assignable to every vertex in a network .
many of these are based on the notion of shortest path.
we say that a path connects two vertices p and q if there exists a sequence of edges that connect p and q. the length of a path is its number of edges.
the distance l between p and q is the length of the shortest path connecting p and q. hence, one of these global centrality measurements is the closeness centrality – also referred as chemical distance  – and is defined as the inverse of the average distance value between p and all the other vertices of the network.
another, the eccentricity  <cit> , is the inverse of the maximum distance from p to any other vertex.
we can also define the betweenness at a vertex p  <cit>  as the number of all shortest paths connecting two vertices of the network that pass through p normalized by the total number of paired vertices.
here, we show that closeness centrality correlates more accurately with critical residues than betweenness or any other centrality measurement tested.
also, we show that the sets of critical residues predicted by any of the centrality measurements  do not completely overlap with those based on phylogeny.
hence, we present evidence that combined predictions based on closeness centrality and phylogeny improve the predictions achieved by any of these approaches alone.
finally, we observe that the critical residues detected by centrality measurements correlate with low-accessibility solvent residues, although these are not exclusively in the protein's core.
these results are used to suggest an explanation for the improvement achieved by the combined approach to detect critical residues.
RESULTS
five methods based on network analyses
we propose and compare five different centrality measurements to predict critical amino acids from a protein structure: connectivity, cluster coefficient, closeness centrality, betweenness and 2-connectivity.
the 2-connectivity at a vertex p is the number of vertices connected to p with fewer than  <dig> edges.
this new measurement is local and can be seen as a generalization of the connectivity.
let us describe now how we proceed to determine the critical residues from one of these centrality measurements, for example the closeness centrality .
we assume that the amino acids that have the largest closeness centrality are critical for the function of the protein.
since the set of predicted critical residues depends on the cut-off value used to define the "largest closeness centrality", we evaluated all possible cut-off values.
hence, we define five methods to predict critical residues, each one based on a different centrality measurement.
for each, the set of critical amino acids is defined to be composed of the vertices:
• method 1: with the largest closeness centrality,
• method 2: with the largest betweenness,
• method 3: with the largest 2-connectivity,
• method 4: with the largest connectivity,
• method 5: with the smallest cluster coefficient.
we compared these methods on a set of five well-characterized proteins in terms of their 3d structures and biochemical identification of critical residues.
these include tem <dig> beta-lactamase, t <dig> lysozyme and hiv- <dig> protease .
exhaustive mutagenesis and analysis has been utilized to identify every residue critical for the functioning of these three proteins, and therefore they serve as excellent test proteins for the computational methods described here.
we also include barnase  <cit>  and the bacteriophage f <dig> gene v protein  <cit> .
two differences are relevant for these two proteins with respect to the previous set of three proteins mentioned before: the number of homologous sequences available is reduced and the sensitivity of the biological assay is augmented.
for the beta-lactamase and the protease of the hiv- <dig>  more than  <dig> unique homologous sequences were found by the conseq server, while for the bacteriophage f <dig> gene v protein only  <dig> homologous sequences were found on the hssp database.
for barnase, fewer than  <dig> homologous sequences were found by the conseq server and  <dig> homologous sequences were found within the hssp database .
although our choice of these proteins was not simply because of the relative lack of homologous sequences, this limitation of the current experimental data serves to illustrate the point that a method that does not require a large number of homologous sequences is desirable as a complement to phylogenetic analyses.
finally, the sensitivity of the biological assay employed to identify critical residues in barnase  was much higher than the one employed for the other four proteins, thus reducing the total number of critical residues detected experimentally.
in order to evaluate the quality of our predictions, we use the sensitivity and the specificity statistical measurements.
however, one of these two criteria alone is not sufficient to compare the different methods .
therefore, in order to obtain a single value to evaluate the predictions of our methods that includes both sensitivity and specificity, we propose three different strategies:
<dig>  for a given centrality measurement and cut-off value, we calculate the error dist .
this error considers simultaneously the specificity and the sensitivity.
it is small if both the sensitivity and the specificity are good.
this error allows us to sort all the predictions obtained by any centrality measurement/cut-off value used .
for every method, results are obtained in average over five 3d structures: 1hiv, 2lzm, 1btl, 1a2p and 1gvp.
numbers are obtained the following way: for a given cut-off value , we calculate the average  of the dist error, the sensitivity and the specificity.
this is done for several cut-off values.
then we choose the cut-off for which the average of the dist error is minimal.
note that in most of the cases, the error is the smallest if we predict around 40% of the amino acids to be essential.
furthermore the smallest error for 1/eccentricity is worse than the smallest errors for the five other centrality measurements .
results are obtained in average other the set of  <dig> proteins.
numbers are obtained by calculating the average as in table  <dig>
<dig>  for a given centrality measurement and cut-off value, we also compare the sensitivity value to the proportion of predicted amino acids .
this is relevant, because the sensitivity is greater than the proportion of predicted amino acids if and only if the method is better than random .
furthermore, by plotting the sensitivity versus the proportion of predicted amino acids , we can compare all the methods with all of their different cut-off values.
<dig>  we also compare the specificity values of the different methods when the sensitivity is equal to 50% .
for every method, results are obtained in average over the set of five proteins.
numbers are obtained by calculating the average as in table  <dig>  for each method, we indicate the value of the specificity and the proportion of residues that are predicted when the sensitivity is equal to 50%.
results are obtained in average over the set of  <dig> proteins.
numbers are obtained by calculating the average as in table  <dig>  for each method, we indicate the value of the specificity and the proportion of residues that are predicted when the sensitivity is equal to 50%.
we show that the five methods give better results than a random prediction of critical residues, at any given cut-off value selected .
that is, if we randomly select between 10% and 75% of the amino acids in a given protein, there is a probability of less than 1% to have better results than with methods 1– <dig> .
furthermore, if we predict as critical residues fewer than 30% of the protein's amino acids, the best method is based on the global centrality measurement closeness centrality .
alternatively, if we predict as critical residues 30% to 55% of the protein's amino acids, the method based on the local centrality measurement 2-connectivity  gives the best results .
method  <dig>  always gives better results than method  <dig> .
we also tried other network centrality measurements , however, the results obtained indicated much less accuracy than with these five methods: the method using the eccentricity measurement is worse than random  and the method using 1/eccentricity measurement is worse than methods 1– <dig> .
our results improve the reliability of predictions based on the network centrality measurement betweenness described in  <cit> , in which one structure was used to identify critical residues.
this is probably due to the fact that we considered several cut-off values.
for example, if we want to maximize both the specificity and the sensitivity for the predictions based on betweenness, we need to predict around 40% of a protein's amino acids , while in  <cit>  less than 20% of a protein's amino acids were predicted as critical.
different centrality measurements do not recognize the same set of critical amino acids
the comparison of the level of accuracy in predicting critical residues of the five network centrality-based methods and two phylogenetic approaches reveals that these phylogenetic methods  are as reliable as the best network centrality-based methods .
we analyzed whether the sets of critical residues identified by any of these approaches display overlap.
if there is little or no overlap, then combining the predictions from these methods may improve the reliability of their individual predictions.
there is no strong "functional relationship" between any two different network-based centrality measurements.
in other words, we cannot express precisely one of these properties as a mathematical function of any other properties.
for example, plotting the betweenness versus closeness centrality  shows a cloud of points that are not disposed on a curve.
more generally, we do not observe any strong "functional relationship" between any two of these network-based centrality measurements: the connectivity, the cluster coefficient, the eccentricity, the closeness centrality, the betweenness and the 2-connectivity.
hence, the centrality-based methods  may not predict the same set of critical amino acids.
alternatively, looking at a less rigorous relationship among centrality measurements, we did observe some overlap.
as shown in fig.
<dig>  the critical amino acids detected by two network centrality-based measurements present some overlap: if the betweenness of an amino acid is high, then its closeness centrality is typically high, as well.
hence, the set of vertices with high betweenness is completely included in a set of vertices with high closeness centrality.
a similar trend is also observed for other centrality measurements, as expected from the fact that these all share some common factors .
there is also no strong "functional relationship" between the set of amino acids predicted with any of the five network methods and the set of amino acids predicted with phylogenetic approaches.
this also implies that a network method and a phylogenetic method do not predict the same set of residues, although they both present similar reliability in their abilities to predict critical residues.
for example, fig.
<dig> shows that the score from one of the phylogenetic approaches used  is not related to the closeness centrality score .
therefore, since these two methods predict with the best confidence critical residues and do not predict the same set of amino acids, a combination of the two methods is expected to improve these results .
an improved method using the conseq server and the closeness centrality
we propose a new method that improves the accuracy of the predictions achieved by the phylogenetic approaches tested here  or the five methods based on network analyses.
this method is based on combining critical residues predicted by closeness centrality and by one phylogenetic approach .
the method is now briefly described.
for a given number k, the set union is obtained by combining both the k amino acids that have the largest conseq value and the k amino acids that have the largest closeness centrality value.
the set intersection is obtained by taking the common amino acids between the k amino acids that have the largest conseq value with the k amino acids that have the largest closeness centrality value.
if we predict less than 35% of a protein's amino acids to be critical for protein function, then the set intersection gives better results than both phylogenetic approaches and centrality-based methods; if we predict more than 60% of the amino acid residues, the union set gives the best results .
furthermore, the sensitivity and the specificity considered simultaneously are better for the union set than for the other methods .
if we compare the different methods for a sensitivity value of 50%, we notice that the union set is also giving the best results .
therefore, we have a method that improves both the phylogenetic methods and the centrality-based methods.
testing the method in a different set of proteins
in order to evaluate our combined method in a different set of proteins, we used a set of  <dig> proteins .
these proteins all have their three-dimensional structures solved, and information is available about some but not all of their critical residues .
this set was used to evaluate the reliability of the predictions of the closeness centrality .
we observed as with the previous set of proteins, that for a sensitivity value of 50%, the union set predicts more true critical residues than phylogenetic approaches  .
the sensitivity and specificity values are reported for each individual protein , and the average values obtained for these proteins and the set of  <dig> proteins.
these sensitivity and specificity values correspond to the best cut-off value of the error ) estimated for the closeness centrality.
results in average are obtained by taking the best cut-off value for every protein .
to compare closeness centrality against phylogenetic approaches, we noticed that the site annotation in this  <dig> proteins, mostly included residues annotated to be involved in catalysis , ligand binding  and/or metal-binding  sites .
many of the metal binding sites were identified from crystallization conditions, as opposed to be truly involved in any biochemical function.
for instance,  <dig> out of  <dig> residues involved in metal binding sites participated in catalysis.
our method identified with similar or better reliability than phylogenetic methods active site residues, ligand binding sites and metal binding sites involved in catalysis .
overall, phylogenetic methods predict with better reliability the set of annotated sites for these  <dig> proteins, mainly because these methods detected better metal binding sites than our method.
the number of predicted residues that were annotated as site in  <dig> selected proteins is reported for columns closeness centrality, hssp and conseq.
these last two columns correspond to the results obtained with phylogenetic methods .
four classes of site annotations were distinguished and included in column site.
relationship between central amino acids and protein surface-accessible area
looking for an explanation for why the combination of phylogeny with network centrality renders improved results in the prediction of critical residues, we decided to analyze the nature of the residues detected by these two approaches.
it has been previously shown that critical amino acids present special geometrical properties  <cit> .
for instance, critical residues have been proposed to have a tendency to be in low surface-accessibility areas  <cit> .
since proteins are compact molecules and the methods described here aim to detect residues central to a protein's amino acid interactions, it is expected that central residues may be at the protein's core .
indeed, tem <dig> beta-lactamase, hiv- <dig> protease, t <dig> lysozyme, barnase and bacteriophage f <dig> gene v protein have their critical residues at a low-surface area : if we assume that residues above  <dig> square angstroms of surface accessibility are exposed, and buried otherwise, all critical residues for this protein are buried , as well as all central residues.
furthermore, phylogenetically highly conserved residues also present this trend: conserved residues have low surface accessibility.
however, it is clear that the surface accessibility measurement alone is not a good predictor of critical residues .
also, it is important to note that the cut-off value chosen to define buried residues is an arbitrary one.
in this sense, critical residues are not all "buried" inside a protein; some of them tend to be "exposed" .
for instance, the critical residues detected in the five proteins by closeness centrality include active site residues that are not core residues .
in any case, changing the criterion that defines core residues does not change the conclusions reached here: network centrality measurements are good predictors of the criticality of an amino acid in protein structure and function.
on the other hand, there is a relationship between the surface accessibility and the centrality measurement for a given residue : the most central residues tend to have a low-accessibility surface.
this relationship is not observed for the conserved residues .
hence, in order to explain our results showing centrality measurements as good predictors of critical residues, we propose that these measurements represent more accurately the property that establishes a residue as one critical for protein function: critical residues are central to the residue-residue interactions and these tend to have low-accessibility surfaces.
while revising this manuscript, we became aware that amitai and colleagues  <cit>  reported that closeness centrality was effective in identifying critical residues from protein structures in a different set of proteins than ours.
this may constitute an additional validation that centrality is a new feature of protein structures that is related to the function of residues in a protein.
however, we cannot compare directly our results with theirs.
the main difference is the procedure used to build the network of contacts in these two studies.
based on this difference, amitai and colleagues reported a correlation between conserved residues and central ones, a feature we did not observe.
another difference is that the specificity of the method reported by amitai and colleagues  is much lower than ours .
also, the sensitivity of both methods differs .
however, amitai and colleagues found that closeness centrality is related to low surface accessibility, just as we did.
CONCLUSIONS
we compared several methods for prediction of critical residues for a given protein function.
in the case in which the protein cannot be aligned with a significant number of homologues, we provide five network-based methods that require the proteins' 3d structures but do not require homologous proteins.
although these five methods do not predict the same sets of critical residues, they all give results much better than random.
in the case in which a protein with known 3d structure has enough protein sequence homologues, phylogenetic approaches are as reliable as the five network-based methods.
more importantly, there is little overlap in the set of predicted critical residues by any compared method.
hence we propose a new method based on both a network centrality measurement  and a phylogeny approach  to predict critical residues for protein function based on the 3d structure of proteins and multiple sequence alignments.
this hybrid approach improves upon the results of any of the methods compared here.
we observed that there is a trend in plotting centrality measurements and surface accessibility: the most central residues are also those with least likelihood of surface exposure.
such a trend is not as striking for conservation scores and surface accessibility.
since critical residues tend to be more within or near the core , we propose that the improvement achieved by combining phylogeny with network centrality measurements is due to the complementary nature of these two approaches.

 this article deals with the problem of predicting critical amino acid residues for a given protein's function, i.e., those residues that, if mutated, result in a loss of protein function by the lack of proper folding and/or the inability to perform a biochemical function. a common approach to this problem consists of aligning multiple orthologous protein sequences, and predicting as critical residues the most highly conserved ones. this approach is known as the phylogenetic approach, and requires that a significant number of distinct protein sequences be aligned. this approach also assumes that the aligned sequences from different species serve the same function in the different species. however, for an increasing number of proteins studied by the structural genomic consortium, a different trend is observed: for a given protein there may be a lack of a significant number of homologous sequences, whereas the three-dimensional structure of the protein of interest may already have been described. for this set of proteins, having an accurate way to identify critical residues in the absence of known orthologues – i.e., simply from the protein's three-dimensional structure – may be valuable. identifying critical residues from protein structures can also be extended to those proteins for which there are a significant number of homologous sequences. furthermore, the prediction of critical residues from protein structures has been shown to be useful in validating protein structure predictions. over the past few decades, network analyses have been used to model diverse systems such as the world wide web, social systems, and biological systems. only very recently has such an approach been used to predict critical amino acids from protein structures. by definition, a network is composed of two sets: a set of vertices and a set of edges. a protein can be modelled in a network as follows: each vertex of the network represents an amino acid residue, and each edge represents a chemical interaction between any two amino acid residues. in the particular case in which the 3d structure of the protein is known, it can be assumed, for the sake of the model, that there is a chemical interaction between two amino acids if they are sufficiently close to one another. this gives a way of building a network of amino acid interactions, with the obvious caveat that the accuracy of such a model will be affected by the accuracy of the assumption of chemical interactions between different residues. previous studies have related specific centrality measurements of these amino acid interaction networks to the tolerance for replacement of the various amino acids within the network. in particular, the most traversed vertices have been shown to be important for folding and for the functions of the modelled proteins. these vertices, when detected from several structures for a given protein, relate more accurately with critical residues than the most conserved residues detected from some phylogenetic approaches. hence, betweenness, a network centrality measurement, is associated with the capacity of any given amino acid residue to play a critical role in a protein's function. these results indicate that critical residues are central to the interactions among the residues in a protein structure. however, whether or not the experimentally determined critical residues are best predicted by measures of betweenness, as opposed to any other centrality measurement, has not been tested. evaluation of other centrality measurements may also help to understand the significance of the observed relationship. in the current work we compare five different network centrality measurements, applying them to the study of the structure/function relationship of proteins. previous studies on the structure/function relationship of proteins have shown that critical residues tend to display specific geometrical characteristics, such as distorted dihedral angles or central location, buried within the proteins' cores. however, whether these geometrical properties are related to network centrality has not been studied. in this work, we analyze some of these relationships, as well. it is possible to define several centrality measurements at a vertex p of a network. some of these centrality measurements have already been used for modelling different systems. one of the most direct and widely used centrality measurements is the connectivity cp, which is the number of neighbours of p. another, the clustering coefficient, defined by 2np/cp, where np is the number of connections between the neighbours of p, estimates the degree of interconnectivity among the neighbours of p. these two measurements are local, in the sense that their values only depend on the vertex p and on its neighbours. there are also global centrality measurements assignable to every vertex in a network. many of these are based on the notion of shortest path. we say that a path connects two vertices p and q if there exists a sequence of edges that connect p and q. the length of a path is its number of edges. the distance l between p and q is the length of the shortest path connecting p and q. hence, one of these global centrality measurements is the closeness centrality – also referred as chemical distance – and is defined as the inverse of the average distance value between p and all the other vertices of the network. another, the eccentricity, is the inverse of the maximum distance from p to any other vertex. we can also define the betweenness at a vertex p as the number of all shortest paths connecting two vertices of the network that pass through p normalized by the total number of paired vertices. here, we show that closeness centrality correlates more accurately with critical residues than betweenness or any other centrality measurement tested. also, we show that the sets of critical residues predicted by any of the centrality measurements do not completely overlap with those based on phylogeny. hence, we present evidence that combined predictions based on closeness centrality and phylogeny improve the predictions achieved by any of these approaches alone. finally, we observe that the critical residues detected by centrality measurements correlate with low-accessibility solvent residues, although these are not exclusively in the protein's core. these results are used to suggest an explanation for the improvement achieved by the combined approach to detect critical residues.  five methods based on network analyses we propose and compare five different centrality measurements to predict critical amino acids from a protein structure: connectivity, cluster coefficient, closeness centrality, betweenness and 2-connectivity. the 2-connectivity at a vertex p is the number of vertices connected to p with fewer than edges. this new measurement is local and can be seen as a generalization of the connectivity. let us describe now how we proceed to determine the critical residues from one of these centrality measurements, for example the closeness centrality. we assume that the amino acids that have the largest closeness centrality are critical for the function of the protein. since the set of predicted critical residues depends on the cut-off value used to define the "largest closeness centrality", we evaluated all possible cut-off values. hence, we define five methods to predict critical residues, each one based on a different centrality measurement. for each, the set of critical amino acids is defined to be composed of the vertices: • method 1: with the largest closeness centrality, • method 2: with the largest betweenness, • method 3: with the largest 2-connectivity, • method 4: with the largest connectivity, • method 5: with the smallest cluster coefficient. we compared these methods on a set of five well-characterized proteins in terms of their 3d structures and biochemical identification of critical residues. these include tem beta-lactamase, t lysozyme and hiv- protease. exhaustive mutagenesis and analysis has been utilized to identify every residue critical for the functioning of these three proteins, and therefore they serve as excellent test proteins for the computational methods described here. we also include barnase and the bacteriophage f gene v protein. two differences are relevant for these two proteins with respect to the previous set of three proteins mentioned before: the number of homologous sequences available is reduced and the sensitivity of the biological assay is augmented. for the beta-lactamase and the protease of the hiv- more than unique homologous sequences were found by the conseq server, while for the bacteriophage f gene v protein only homologous sequences were found on the hssp database. for barnase, fewer than homologous sequences were found by the conseq server and homologous sequences were found within the hssp database. although our choice of these proteins was not simply because of the relative lack of homologous sequences, this limitation of the current experimental data serves to illustrate the point that a method that does not require a large number of homologous sequences is desirable as a complement to phylogenetic analyses. finally, the sensitivity of the biological assay employed to identify critical residues in barnase was much higher than the one employed for the other four proteins, thus reducing the total number of critical residues detected experimentally. in order to evaluate the quality of our predictions, we use the sensitivity and the specificity statistical measurements. however, one of these two criteria alone is not sufficient to compare the different methods. therefore, in order to obtain a single value to evaluate the predictions of our methods that includes both sensitivity and specificity, we propose three different strategies: for a given centrality measurement and cut-off value, we calculate the error dist. this error considers simultaneously the specificity and the sensitivity. it is small if both the sensitivity and the specificity are good. this error allows us to sort all the predictions obtained by any centrality measurement/cut-off value used. for every method, results are obtained in average over five 3d structures: 1hiv, 2lzm, 1btl, 1a2p and 1gvp. numbers are obtained the following way: for a given cut-off value, we calculate the average of the dist error, the sensitivity and the specificity. this is done for several cut-off values. then we choose the cut-off for which the average of the dist error is minimal. note that in most of the cases, the error is the smallest if we predict around 40% of the amino acids to be essential. furthermore the smallest error for 1/eccentricity is worse than the smallest errors for the five other centrality measurements. results are obtained in average other the set of proteins. numbers are obtained by calculating the average as in table for a given centrality measurement and cut-off value, we also compare the sensitivity value to the proportion of predicted amino acids. this is relevant, because the sensitivity is greater than the proportion of predicted amino acids if and only if the method is better than random. furthermore, by plotting the sensitivity versus the proportion of predicted amino acids, we can compare all the methods with all of their different cut-off values. we also compare the specificity values of the different methods when the sensitivity is equal to 50%. for every method, results are obtained in average over the set of five proteins. numbers are obtained by calculating the average as in table for each method, we indicate the value of the specificity and the proportion of residues that are predicted when the sensitivity is equal to 50%. results are obtained in average over the set of proteins. numbers are obtained by calculating the average as in table for each method, we indicate the value of the specificity and the proportion of residues that are predicted when the sensitivity is equal to 50%. we show that the five methods give better results than a random prediction of critical residues, at any given cut-off value selected. that is, if we randomly select between 10% and 75% of the amino acids in a given protein, there is a probability of less than 1% to have better results than with methods 1–. furthermore, if we predict as critical residues fewer than 30% of the protein's amino acids, the best method is based on the global centrality measurement closeness centrality. alternatively, if we predict as critical residues 30% to 55% of the protein's amino acids, the method based on the local centrality measurement 2-connectivity gives the best results. method always gives better results than method. we also tried other network centrality measurements, however, the results obtained indicated much less accuracy than with these five methods: the method using the eccentricity measurement is worse than random and the method using 1/eccentricity measurement is worse than methods 1–. our results improve the reliability of predictions based on the network centrality measurement betweenness described in, in which one structure was used to identify critical residues. this is probably due to the fact that we considered several cut-off values. for example, if we want to maximize both the specificity and the sensitivity for the predictions based on betweenness, we need to predict around 40% of a protein's amino acids, while in less than 20% of a protein's amino acids were predicted as critical. different centrality measurements do not recognize the same set of critical amino acids the comparison of the level of accuracy in predicting critical residues of the five network centrality-based methods and two phylogenetic approaches reveals that these phylogenetic methods are as reliable as the best network centrality-based methods. we analyzed whether the sets of critical residues identified by any of these approaches display overlap. if there is little or no overlap, then combining the predictions from these methods may improve the reliability of their individual predictions. there is no strong "functional relationship" between any two different network-based centrality measurements. in other words, we cannot express precisely one of these properties as a mathematical function of any other properties. for example, plotting the betweenness versus closeness centrality shows a cloud of points that are not disposed on a curve. more generally, we do not observe any strong "functional relationship" between any two of these network-based centrality measurements: the connectivity, the cluster coefficient, the eccentricity, the closeness centrality, the betweenness and the 2-connectivity. hence, the centrality-based methods may not predict the same set of critical amino acids. alternatively, looking at a less rigorous relationship among centrality measurements, we did observe some overlap. as shown in fig. the critical amino acids detected by two network centrality-based measurements present some overlap: if the betweenness of an amino acid is high, then its closeness centrality is typically high, as well. hence, the set of vertices with high betweenness is completely included in a set of vertices with high closeness centrality. a similar trend is also observed for other centrality measurements, as expected from the fact that these all share some common factors. there is also no strong "functional relationship" between the set of amino acids predicted with any of the five network methods and the set of amino acids predicted with phylogenetic approaches. this also implies that a network method and a phylogenetic method do not predict the same set of residues, although they both present similar reliability in their abilities to predict critical residues. for example, fig. shows that the score from one of the phylogenetic approaches used is not related to the closeness centrality score. therefore, since these two methods predict with the best confidence critical residues and do not predict the same set of amino acids, a combination of the two methods is expected to improve these results. an improved method using the conseq server and the closeness centrality we propose a new method that improves the accuracy of the predictions achieved by the phylogenetic approaches tested here or the five methods based on network analyses. this method is based on combining critical residues predicted by closeness centrality and by one phylogenetic approach. the method is now briefly described. for a given number k, the set union is obtained by combining both the k amino acids that have the largest conseq value and the k amino acids that have the largest closeness centrality value. the set intersection is obtained by taking the common amino acids between the k amino acids that have the largest conseq value with the k amino acids that have the largest closeness centrality value. if we predict less than 35% of a protein's amino acids to be critical for protein function, then the set intersection gives better results than both phylogenetic approaches and centrality-based methods; if we predict more than 60% of the amino acid residues, the union set gives the best results. furthermore, the sensitivity and the specificity considered simultaneously are better for the union set than for the other methods. if we compare the different methods for a sensitivity value of 50%, we notice that the union set is also giving the best results. therefore, we have a method that improves both the phylogenetic methods and the centrality-based methods. testing the method in a different set of proteins in order to evaluate our combined method in a different set of proteins, we used a set of proteins. these proteins all have their three-dimensional structures solved, and information is available about some but not all of their critical residues. this set was used to evaluate the reliability of the predictions of the closeness centrality. we observed as with the previous set of proteins, that for a sensitivity value of 50%, the union set predicts more true critical residues than phylogenetic approaches. the sensitivity and specificity values are reported for each individual protein, and the average values obtained for these proteins and the set of proteins. these sensitivity and specificity values correspond to the best cut-off value of the error ) estimated for the closeness centrality. results in average are obtained by taking the best cut-off value for every protein. to compare closeness centrality against phylogenetic approaches, we noticed that the site annotation in this proteins, mostly included residues annotated to be involved in catalysis, ligand binding and/or metal-binding sites. many of the metal binding sites were identified from crystallization conditions, as opposed to be truly involved in any biochemical function. for instance, out of residues involved in metal binding sites participated in catalysis. our method identified with similar or better reliability than phylogenetic methods active site residues, ligand binding sites and metal binding sites involved in catalysis. overall, phylogenetic methods predict with better reliability the set of annotated sites for these proteins, mainly because these methods detected better metal binding sites than our method. the number of predicted residues that were annotated as site in selected proteins is reported for columns closeness centrality, hssp and conseq. these last two columns correspond to the results obtained with phylogenetic methods. four classes of site annotations were distinguished and included in column site. relationship between central amino acids and protein surface-accessible area looking for an explanation for why the combination of phylogeny with network centrality renders improved results in the prediction of critical residues, we decided to analyze the nature of the residues detected by these two approaches. it has been previously shown that critical amino acids present special geometrical properties. for instance, critical residues have been proposed to have a tendency to be in low surface-accessibility areas. since proteins are compact molecules and the methods described here aim to detect residues central to a protein's amino acid interactions, it is expected that central residues may be at the protein's core. indeed, tem beta-lactamase, hiv- protease, t lysozyme, barnase and bacteriophage f gene v protein have their critical residues at a low-surface area: if we assume that residues above square angstroms of surface accessibility are exposed, and buried otherwise, all critical residues for this protein are buried, as well as all central residues. furthermore, phylogenetically highly conserved residues also present this trend: conserved residues have low surface accessibility. however, it is clear that the surface accessibility measurement alone is not a good predictor of critical residues. also, it is important to note that the cut-off value chosen to define buried residues is an arbitrary one. in this sense, critical residues are not all "buried" inside a protein; some of them tend to be "exposed". for instance, the critical residues detected in the five proteins by closeness centrality include active site residues that are not core residues. in any case, changing the criterion that defines core residues does not change the conclusions reached here: network centrality measurements are good predictors of the criticality of an amino acid in protein structure and function. on the other hand, there is a relationship between the surface accessibility and the centrality measurement for a given residue: the most central residues tend to have a low-accessibility surface. this relationship is not observed for the conserved residues. hence, in order to explain our results showing centrality measurements as good predictors of critical residues, we propose that these measurements represent more accurately the property that establishes a residue as one critical for protein function: critical residues are central to the residue-residue interactions and these tend to have low-accessibility surfaces. while revising this manuscript, we became aware that amitai and colleagues reported that closeness centrality was effective in identifying critical residues from protein structures in a different set of proteins than ours. this may constitute an additional validation that centrality is a new feature of protein structures that is related to the function of residues in a protein. however, we cannot compare directly our results with theirs. the main difference is the procedure used to build the network of contacts in these two studies. based on this difference, amitai and colleagues reported a correlation between conserved residues and central ones, a feature we did not observe. another difference is that the specificity of the method reported by amitai and colleagues is much lower than ours. also, the sensitivity of both methods differs. however, amitai and colleagues found that closeness centrality is related to low surface accessibility, just as we did.  we compared several methods for prediction of critical residues for a given protein function. in the case in which the protein cannot be aligned with a significant number of homologues, we provide five network-based methods that require the proteins' 3d structures but do not require homologous proteins. although these five methods do not predict the same sets of critical residues, they all give results much better than random. in the case in which a protein with known 3d structure has enough protein sequence homologues, phylogenetic approaches are as reliable as the five network-based methods. more importantly, there is little overlap in the set of predicted critical residues by any compared method. hence we propose a new method based on both a network centrality measurement and a phylogeny approach to predict critical residues for protein function based on the 3d structure of proteins and multiple sequence alignments. this hybrid approach improves upon the results of any of the methods compared here. we observed that there is a trend in plotting centrality measurements and surface accessibility: the most central residues are also those with least likelihood of surface exposure. such a trend is not as striking for conservation scores and surface accessibility. since critical residues tend to be more within or near the core, we propose that the improvement achieved by combining phylogeny with network centrality measurements is due to the complementary nature of these two approaches. 
we show that network analysis can be used to improve the prediction of amino acids critical for protein function, when utilized in combination with phylogenetic approaches. network analyses have been used in the modelling of many complex biological systems, but only very recently have they been used to predict critical residues from a protein's three-dimensional structure. it is proposed that such improvement is due to the complementary nature of these approaches: network-based methods tend to predict as critical those residues that are highly connected and internal, although some surface residues are indeed identified as critical by network analyses; whereas residues chosen by phylogenetic approaches display a lower overall probability of being surface inaccessible. we associate a network with each member of a set of proteins for which the three-dimensional structure is known and the critical residues have been previously determined experimentally. phylogenetic approaches are commonly used to predict which amino acid residues are critical to the function of a given protein. here we compare a couple of phylogenetic approaches to several different network-based methods for the prediction of critical residues, and show that a combination of one phylogenetic method and one network-based method is superior to other methods previously employed. phylogenetic approaches render predictions as reliable as the network-based measurements, although, interestingly, the two general approaches tend to predict different sets of critical residues. hence we propose a hybrid method that is composed of one network-based calculation – the closeness centrality – and one phylogenetic approach – the conseq server. we show that several network-based centrality measurements accurately detect residues critical for the protein's function. therefore, complementary or alternative approaches for the prediction of critical residues would be desirable. this hybrid approach predicts critical residues more accurately than the other methods tested here.
 phylogenetic approaches are commonly used to predict which amino acid residues are critical to the function of a given protein. however, such approaches display inherent limitations, such as the requirement for identification of multiple homologues of the protein under consideration. therefore, complementary or alternative approaches for the prediction of critical residues would be desirable. network analyses have been used in the modelling of many complex biological systems, but only very recently have they been used to predict critical residues from a protein's three-dimensional structure. here we compare a couple of phylogenetic approaches to several different network-based methods for the prediction of critical residues, and show that a combination of one phylogenetic method and one network-based method is superior to other methods previously employed.  we associate a network with each member of a set of proteins for which the three-dimensional structure is known and the critical residues have been previously determined experimentally. we show that several network-based centrality measurements accurately detect residues critical for the protein's function. phylogenetic approaches render predictions as reliable as the network-based measurements, although, interestingly, the two general approaches tend to predict different sets of critical residues. hence we propose a hybrid method that is composed of one network-based calculation – the closeness centrality – and one phylogenetic approach – the conseq server. this hybrid approach predicts critical residues more accurately than the other methods tested here.  we show that network analysis can be used to improve the prediction of amino acids critical for protein function, when utilized in combination with phylogenetic approaches. it is proposed that such improvement is due to the complementary nature of these approaches: network-based methods tend to predict as critical those residues that are highly connected and internal, although some surface residues are indeed identified as critical by network analyses; whereas residues chosen by phylogenetic approaches display a lower overall probability of being surface inaccessible. 