BACKGROUND
with the successful sequencing of the human genome and the genomes of many model organisms, attention has focused on determining the function of the protein products derived from the genome.
function is difficult to define precisely and can be considered at many levels, from the molecular to the organismal or even the population level.
general function can often be assigned based solely on sequence analysis and similarity .
however, these methods are imperfect, as functions of proteins with common descent may evolve away from one another  <cit> .
the molecular functions associated with a three-dimensional  protein structure are somewhat less diverse and arguably more manageable: they include the basic activities of binding, catalysis, structural support, structural dynamics, and other functions that can be defined with respect to particular arrangements of atoms, the physical forces and environment they create, and the dynamics that result.
thus, when structure is available, the discussion of function can often become more detailed.
structure-based methods for predicting function have recently become important in the context of structural genomics initiatives.
traditionally, protein structures have been determined for biologically critical molecules where biologists have required knowledge of structure in order to understand the details of mechanism or interactions.
these proteins were often studied extensively prior to structural investigations, and so there was significant functional information available.
upon solving the structure, there were also many assays available to test the protein  in order to further probe the function.
with the rise of structural genomics initiatives, there is an increasing number of protein structures available for which there is little or no functional information  <cit> .
indeed, these proteins are often prioritized precisely because they represent relatively unexplored segments of the protein structural space.
thus, methods are needed that can look at a novel 3d structure and label areas of potential functional significance .
methods for structure-based function prediction are diverse.
many rely on global fold recognition in order to more sensitively detect family relationships  <cit> , but we stress in this brief review those methods that focus on local segments of 3d structures.
the fff  <cit>  and jess  <cit>  methods build 3d templates that specify amino acid residues and allowable geometric relationships to define sites of interest, using examples from which the models are constructed.
the evolutionary trace  method and consurf  <cit>  both take advantage of evolutionary information to highlight regions of 3d structure with high probability of functional importance.
thematics  <cit>  is a program that uses electrostatic environment and associated statistics of theoretical microscopic titration curves to highlight regions of likely enzymatic activity.
query3d  <cit>  is a system that stores annotation information for all residues in a protein and allows this information to be queried and compared in the context of looking for similar residue environments.
some methods have moved away from representations focused on amino acids and use representations that are both spatial and sensitive to chemical groups.
for example, sumo  <cit>  uses stereochemical groups to represent protein environments.
similarly, we have reported on the feature method  <cit> , which represents a microenvironment as a set of concentric shells  around a central point.
physical and chemical properties within these shells  are counted in sites of interest, and their counts are compared with control nonsites.
in this way, feature develops a statistical model of the three-dimensional distribution of properties that are distinct for the sites of interest and are not defined based on sequence features.
feature has been used to characterize sites such as calcium binding  <cit> , atp binding  <cit> , serine protease active sites  <cit> , and others  <cit> .
up until now, feature has relied on supervised machine learning to build models based on known examples of a site.
in this paper, we investigate the possibility of using feature's representation of sites to perform unsupervised machine learning  on all potential sites in a nonredundant subset of the protein data bank .
the ability to cluster sites would allow us to identify previously unrecognized similarities between 3d sections of diverse proteins and could provide important clues to the function of these sections.
while previous studies have used unsupervised learning techniques to discover functional relationships among structural fragments extracted from proteins  <cit> , our approach differs in that we examine the relationships among the local environments around residues.
we describe our results in performing a clustering of 3d protein environments, represented as feature vectors, on a subset of the pdb with no two structures having more than 50% sequence similarity.
feature vectors have previously been used to gain insight into a local environment's potential function by finding similar environments in other protein structures  <cit> , and we extend this approach by improving the distance measure used to compare vectors and by progressing from classification of individual sites of interest to a full clustering of a nonredundant subset of the pdb.
in particular, the aims of the current studies include the following:
• to develop a reduced representation of protein sites that can be rapidly compared using a distance metric during clustering but which yields tight and separated clusters
• to test this reduced representation using a fast k-means clustering algorithm employing a novel distance metric and a biologically informed selection of initial cluster centers
• to validate the resulting clusters with respect to their quality and their ability to rediscover known "positive control" clusters
in particular, we find that our method is able to detect clusters that capture known 1d motifs from prosite  <cit> .
these 1d motifs were not provided to the algorithm, and this result suggests that the reduced representation and cluster algorithm are finding clusters that are robust and biologically relevant.
they also provide statistics that will allow us to analyze and prioritize novel clusters in future work.
RESULTS
in order to ensure that protein environments with known similarities would cluster together using our feature vector representation, we compared the results of clustering vectors from environments known to be similar  using several different distance measures.
we use the silhouette value  in order to quantify clustering quality for each object in a cluster by a continuous number between + <dig>  and - <dig> .
the plot of these values, termed the silhouette plot, shows tight and separate clusters as blue bars to the right, whereas loose or overlapping clusters appear as blue bars to the left .
figures 1a and 1b compare clustering results using the euclidean distance between the original feature vectors to the hamming distance between binary vectors.
the hamming distance between two binary vectors is defined as the number of coordinates in which the vectors' values differ.
as seen in the plots, clustering vectors in their binary representation produces a better result in terms of the median silhouette values.
in figure 1c, we show that the f-distance  outperforms the hamming distance and produces clusters with much better definition in terms of the silhouette value.
on average, a cluster contains  <dig>  residues from each protein chain represented in the cluster, indicating that the potential similarities between overlapping local environments do not dominate the clustering results.
for the full clustering, we used a single-processor  <dig> -ghz p <dig> machine with  <dig> gb of memory running the linux operating system.
the total runtime of clustering nearly two million vectors was on the order of a few hours.
initial validation of clusters
we have defined a distance metric between two binary vectors based on the hamming distance that takes the information content of each feature into account .
we call this weighted hamming distance the f-distance.
in our clustering, the mean distance between clusters  was  <dig>  ±  <dig>  f-distance units.
the mean distance of vectors within clusters  was  <dig>  ±  <dig>  f-distance units.
thus, as expected from the trial silhouette plots using the f-distance in figure  <dig>  the resulting clusters are generally tight and separated.
figure  <dig> shows a histogram of cluster size.
the number of feature vectors in each cluster ranges from as few as  <dig> to as many as  <dig> .
the mean and median sizes are  <dig>  and  <dig>  respectively, and the standard deviation is  <dig> .
in terms of biological validation, figure  <dig> presents fingerprints of the features listed in table  <dig> that are over- or underrepresented in each of the clusters described below with respect to the background of all two million feature vectors.
since some variation among environments sharing the same prosite annotation is expected, we do not anticipate that all examples of a given motif will cluster together.
we present five examples in which at least 75% of the hits to a prosite pattern among the  <dig>  protein chains used in this study occur in the same cluster.
all these clusters have additional unannotated residues.
these may represent novel predictions of shared function or they may be cases of related but different functions.
assessment of novelty will be addressed in future work.
our focus here is to evaluate the validity of the clustering approach.
tyrosine protein kinases specific active-site signature
thirteen of the  <dig> tyrosine_kinase_tyr prosite pattern  hits among the protein chains used in this study are contained within a single cluster.
there are  <dig> total residues clustered together.
of the  <dig> residues in this cluster that have prosite annotations, only  <dig> do not belong to this motif.
the average sequence identity among the proteins in this cluster with the tyrosine protein kinase motif is  <dig>  ±  <dig> %.
figure 4a shows a fingerprint of the features listed in table  <dig> that are over- or underrepresented in this cluster with respect to the background of all two million feature vectors, and figure 5a shows a comparison of the environments around two residues from the cluster that share the tyrosine_kinase_tyr annotation.
all the residues in the cluster annotated with this prosite pattern are centered around alanines, and they share a great deal of structural similarity even though only one-half of the residues in the environment are contained within the prosite pattern itself.
staphyloccocal enterotoxin/streptococcal pyrogenic exotoxin signature 2
ten examples of the staph_strep_toxin_ <dig> prosite motif  occur in our dataset, and nine of these occur in a single cluster .
there are  <dig> total residues in this cluster,  <dig> of which have prosite annotations other than staph_strep_toxin_ <dig>  the average sequence identity among the proteins in this cluster with this pattern is  <dig>  ±  <dig> %.
three clusters are required to capture all  <dig> instances of this motif in our data set.
the two examples of environments in this cluster around residues that participate in the staph_strep_toxin_ <dig> motif  exhibit greater structural diversity than do the environments from the other validation clusters described here.
fewer than one-third of the residues in these two environments are located within the motif.
guanylate kinase-like signature
four of the five hits to the guanylate_kinase_ <dig> prosite motif  within our dataset are represented in a single cluster .
there are  <dig> total residues in this cluster, and  <dig> residues have differing prosite annotations.
the average pairwise sequence identity among the proteins in this cluster with the guanylate kinase-like signature is  <dig>  ±  <dig> %.
glycosyl hydrolases family  <dig> active site
all the seven hits to the glycosyl_hydrol_f1_ <dig> prosite pattern  in our dataset are represented in a single cluster .
of the  <dig> residues in this cluster,  <dig> have prosite annotations other than glycosyl_hydrol_f1_ <dig>  the average pairwise sequence identity among the proteins with the glycosyl hydrolase family  <dig> active site motif is  <dig>  ±  <dig> %.
ubiquitin-conjugating enzymes active site
eight of the  <dig> hits to the ubiquitin_conjugat_ <dig> prosite pattern  occur in the same cluster .
of the  <dig> total residues in the cluster,  <dig> have alternate prosite annotations.
the average pairwise sequence identity among the proteins with the ubiquitin-conjugating enzyme active site motif is  <dig>  ±  <dig> %.
figure 5b shows two examples of environments around asparagine residues contained in the ubiquitin_conjugat_ <dig> motif.
despite the fact that the cysteine residue toward the top of this figure is annotated in the prosite database as the catalytic residue, it is in the outskirts of the environment.
because active sites are often dynamic, regions that are slightly removed from the center of catalytic activity may show stronger conservation than the active site itself.
fewer than one-half of the residues in the environments are located within the prosite motif.
statistical significance of the validation clusters
since it may have been the case that the five validation clusters described above could have occurred by chance, we repeatedly reassigned the two million feature vectors into our clusters randomly and assessed the segregation of residues with the same prosite annotation into clusters.
as all of the prosite patterns associated with the validation clusters reported above have at least five hits in our dataset, we limited our analysis to prosite patterns with at least five occurrences.
in approximately 13% of  <dig>  trials, we observed one case where at least 75% of the hits to a prosite pattern occurred in a single cluster.
the probabilities of obtaining two or three such clusters were  <dig> % and  <dig> %, respectively.
a random trial in which four prosite patterns were each predominantly captured in a single cluster occurred only once, and we never observed five patterns to cluster according to these criteria.
thus, the results reported above  are statistically significant.
we also evaluated the overall performance of the clustering algorithm by determining how well each prosite pattern with at least three hits in our dataset clustered.
for each pattern, we identified the cluster in which the highest percentage of hits is represented.
on average,  <dig>  ±  <dig> % of the hits to a pattern are represented in the cluster that best captures that pattern.
for the  <dig>  random clusterings described above, this number drops to  <dig>  ±  <dig> %.
if we exclude all patterns with fewer than five hits,  <dig>  ±  <dig> % of hits occur in the best cluster, whereas only  <dig>  ±  <dig> % are expected to cluster together by chance.
discussion
the major findings of this study are as follows.
first, a binary representation of the feature vectors with a weighted distance metric does not lose significant information necessary for clustering and in fact improves the compactness and separation of clusters in a manual assessment of  <dig> feature models built by hand .
this is a surprising finding since one might guess that continuous valued features would contain more information.
however, the simple division of discrete variables into "zero" or "not zero" and continuous variables into "less than median" and "more than median" outperforms the continuous features.
further, the f-weighting scheme that we employed upweights features with good discrimination power when computing distances while retaining the binary representation, as shown in figure  <dig>  these results give us confidence that real  3d environmental clusters are recognizable by our distance metric.
second, we have shown that the computational complexity of k-means clustering on  <dig> million residues is feasible, with clustering completed within hours on a single modest cpu.
the k-means algorithm is amenable to parallelization, and so we should be able to expand the granularity of our representation to not only include more atoms per residue, but also allow characterization of the "empty" space near residues, such as in pockets of proteins.
the k-means algorithm reaches local minima, so we have begun to experiment with hierarchical k-means  until the clusters are sufficiently small to allow hierarchical clustering.
these approaches may be more robust.
the choice to evaluate values of k up to  <dig>  is a somewhat arbitrary one.
we eventually chose to work with k =  <dig> .
the histogram in figure  <dig> shows that the median cluster size is  <dig>  but there is a very long tail.
all our positive validation examples come from clusters in the range of  <dig> to  <dig> vectors, and so this may be a clue to focus our search for novelty in clusters within that range.
a larger k might allow us to split some of the very large clusters.
we can also experiment with different strategies for seeding the initial centers.
it may be that our focus on surface points  left few centers that match internal, hydrophobic environments.
the large clusters may simply be undifferentiated hydrophobic environments, which account for a large volume of the total protein environments.
a preliminary analysis of clusters with more than  <dig> residues indicates that the top three amino acids occurring in those clusters are leucine, valine, and alanine.
third, our method has found clusters that are enriched for prosite motifs, which are based primarily on sequence analysis.
of course, these motifs have 3d conformations in the associated protein structures, and we have shown previously that these 3d conformations can be used as a seed to create a feature model that is more sensitive than the 1d sequence motif  <cit> .
not surprisingly, the addition of 3d information improves the motif because not only the identity of the amino acids, but also their relative positions can be encoded.
in this work, we have shown further that a clustering of amino acid environments based on the feature radial concentric shells encoded in a weighted binary vector can detect the similarity of the 3d environments associated with prosite motifs.
figure  <dig> shows the detailed feature fingerprint associated with these four clusters.
each is unique and picks up a different prosite motif .
if these motifs had not been previously known based on sequence analysis, our clustering would now have suggested their existence.
this forms the basis of our optimism that a complete analysis of the resulting clusters will yield not only other known 3d fingerprints , but also biologically novel motifs.
in order to discover and characterize these novel motifs, we will need to systematically characterize the cluster properties of the clusters corresponding to known motifs and then use these properties to identify other promising leads.
for example, in our five validated prosite clusters, only a small fraction of the vectors are annotated by prosite.
are these closer to one another than to the other cluster members, or are they scattered uniformly throughout the cluster?
if they are closer to one another, then we may need more cluster centers to distinguish subgroups, or a hierarchical clustering to show the relationships between subclusters.
if they are interspersed, it may suggest that we have found some unrecognized sites with environments that are very similar to those of the prosite-annotated residues.
thus in future work, we will need to dissect all the clusters in order to identify the key features of novel functional clusters.
CONCLUSIONS
we have developed a reduced representation for the environment around an amino acid in a protein.
the representation is binary and can be used in a weighted form to outperform ostensibly "higher information content" representations in identifying compact and separable clusters.
a preliminary k-means clustering of a 50% nonredundant subset of the pdb produced  <dig>  clusters, some of which clearly capture the key features of known prosite motifs as manifested in solved 3d structures.
these results suggest that further refinement and analysis of these clusters may provide previously undetected functional sites and metrics for recognizing them.

 with the successful sequencing of the human genome and the genomes of many model organisms, attention has focused on determining the function of the protein products derived from the genome. function is difficult to define precisely and can be considered at many levels, from the molecular to the organismal or even the population level. general function can often be assigned based solely on sequence analysis and similarity. however, these methods are imperfect, as functions of proteins with common descent may evolve away from one another. the molecular functions associated with a three-dimensional protein structure are somewhat less diverse and arguably more manageable: they include the basic activities of binding, catalysis, structural support, structural dynamics, and other functions that can be defined with respect to particular arrangements of atoms, the physical forces and environment they create, and the dynamics that result. thus, when structure is available, the discussion of function can often become more detailed. structure-based methods for predicting function have recently become important in the context of structural genomics initiatives. traditionally, protein structures have been determined for biologically critical molecules where biologists have required knowledge of structure in order to understand the details of mechanism or interactions. these proteins were often studied extensively prior to structural investigations, and so there was significant functional information available. upon solving the structure, there were also many assays available to test the protein in order to further probe the function. with the rise of structural genomics initiatives, there is an increasing number of protein structures available for which there is little or no functional information. indeed, these proteins are often prioritized precisely because they represent relatively unexplored segments of the protein structural space. thus, methods are needed that can look at a novel 3d structure and label areas of potential functional significance. methods for structure-based function prediction are diverse. many rely on global fold recognition in order to more sensitively detect family relationships, but we stress in this brief review those methods that focus on local segments of 3d structures. the fff and jess methods build 3d templates that specify amino acid residues and allowable geometric relationships to define sites of interest, using examples from which the models are constructed. the evolutionary trace method and consurf both take advantage of evolutionary information to highlight regions of 3d structure with high probability of functional importance. thematics is a program that uses electrostatic environment and associated statistics of theoretical microscopic titration curves to highlight regions of likely enzymatic activity. query3d is a system that stores annotation information for all residues in a protein and allows this information to be queried and compared in the context of looking for similar residue environments. some methods have moved away from representations focused on amino acids and use representations that are both spatial and sensitive to chemical groups. for example, sumo uses stereochemical groups to represent protein environments. similarly, we have reported on the feature method, which represents a microenvironment as a set of concentric shells around a central point. physical and chemical properties within these shells are counted in sites of interest, and their counts are compared with control nonsites. in this way, feature develops a statistical model of the three-dimensional distribution of properties that are distinct for the sites of interest and are not defined based on sequence features. feature has been used to characterize sites such as calcium binding, atp binding, serine protease active sites, and others. up until now, feature has relied on supervised machine learning to build models based on known examples of a site. in this paper, we investigate the possibility of using feature's representation of sites to perform unsupervised machine learning on all potential sites in a nonredundant subset of the protein data bank. the ability to cluster sites would allow us to identify previously unrecognized similarities between 3d sections of diverse proteins and could provide important clues to the function of these sections. while previous studies have used unsupervised learning techniques to discover functional relationships among structural fragments extracted from proteins, our approach differs in that we examine the relationships among the local environments around residues. we describe our results in performing a clustering of 3d protein environments, represented as feature vectors, on a subset of the pdb with no two structures having more than 50% sequence similarity. feature vectors have previously been used to gain insight into a local environment's potential function by finding similar environments in other protein structures, and we extend this approach by improving the distance measure used to compare vectors and by progressing from classification of individual sites of interest to a full clustering of a nonredundant subset of the pdb. in particular, the aims of the current studies include the following: • to develop a reduced representation of protein sites that can be rapidly compared using a distance metric during clustering but which yields tight and separated clusters • to test this reduced representation using a fast k-means clustering algorithm employing a novel distance metric and a biologically informed selection of initial cluster centers • to validate the resulting clusters with respect to their quality and their ability to rediscover known "positive control" clusters in particular, we find that our method is able to detect clusters that capture known 1d motifs from prosite. these 1d motifs were not provided to the algorithm, and this result suggests that the reduced representation and cluster algorithm are finding clusters that are robust and biologically relevant. they also provide statistics that will allow us to analyze and prioritize novel clusters in future work.  in order to ensure that protein environments with known similarities would cluster together using our feature vector representation, we compared the results of clustering vectors from environments known to be similar using several different distance measures. we use the silhouette value in order to quantify clustering quality for each object in a cluster by a continuous number between + and -. the plot of these values, termed the silhouette plot, shows tight and separate clusters as blue bars to the right, whereas loose or overlapping clusters appear as blue bars to the left. figures 1a and 1b compare clustering results using the euclidean distance between the original feature vectors to the hamming distance between binary vectors. the hamming distance between two binary vectors is defined as the number of coordinates in which the vectors' values differ. as seen in the plots, clustering vectors in their binary representation produces a better result in terms of the median silhouette values. in figure 1c, we show that the f-distance outperforms the hamming distance and produces clusters with much better definition in terms of the silhouette value. on average, a cluster contains residues from each protein chain represented in the cluster, indicating that the potential similarities between overlapping local environments do not dominate the clustering results. for the full clustering, we used a single-processor -ghz p machine with gb of memory running the linux operating system. the total runtime of clustering nearly two million vectors was on the order of a few hours. initial validation of clusters we have defined a distance metric between two binary vectors based on the hamming distance that takes the information content of each feature into account. we call this weighted hamming distance the f-distance. in our clustering, the mean distance between clusters was ± f-distance units. the mean distance of vectors within clusters was ± f-distance units. thus, as expected from the trial silhouette plots using the f-distance in figure the resulting clusters are generally tight and separated. figure shows a histogram of cluster size. the number of feature vectors in each cluster ranges from as few as to as many as. the mean and median sizes are and respectively, and the standard deviation is. in terms of biological validation, figure presents fingerprints of the features listed in table that are over- or underrepresented in each of the clusters described below with respect to the background of all two million feature vectors. since some variation among environments sharing the same prosite annotation is expected, we do not anticipate that all examples of a given motif will cluster together. we present five examples in which at least 75% of the hits to a prosite pattern among the protein chains used in this study occur in the same cluster. all these clusters have additional unannotated residues. these may represent novel predictions of shared function or they may be cases of related but different functions. assessment of novelty will be addressed in future work. our focus here is to evaluate the validity of the clustering approach. tyrosine protein kinases specific active-site signature thirteen of the tyrosine_kinase_tyr prosite pattern hits among the protein chains used in this study are contained within a single cluster. there are total residues clustered together. of the residues in this cluster that have prosite annotations, only do not belong to this motif. the average sequence identity among the proteins in this cluster with the tyrosine protein kinase motif is ± %. figure 4a shows a fingerprint of the features listed in table that are over- or underrepresented in this cluster with respect to the background of all two million feature vectors, and figure 5a shows a comparison of the environments around two residues from the cluster that share the tyrosine_kinase_tyr annotation. all the residues in the cluster annotated with this prosite pattern are centered around alanines, and they share a great deal of structural similarity even though only one-half of the residues in the environment are contained within the prosite pattern itself. staphyloccocal enterotoxin/streptococcal pyrogenic exotoxin signature 2 ten examples of the staph_strep_toxin_ prosite motif occur in our dataset, and nine of these occur in a single cluster. there are total residues in this cluster, of which have prosite annotations other than staph_strep_toxin_ the average sequence identity among the proteins in this cluster with this pattern is ± %. three clusters are required to capture all instances of this motif in our data set. the two examples of environments in this cluster around residues that participate in the staph_strep_toxin_ motif exhibit greater structural diversity than do the environments from the other validation clusters described here. fewer than one-third of the residues in these two environments are located within the motif. guanylate kinase-like signature four of the five hits to the guanylate_kinase_ prosite motif within our dataset are represented in a single cluster. there are total residues in this cluster, and residues have differing prosite annotations. the average pairwise sequence identity among the proteins in this cluster with the guanylate kinase-like signature is ± %. glycosyl hydrolases family active site all the seven hits to the glycosyl_hydrol_f1_ prosite pattern in our dataset are represented in a single cluster. of the residues in this cluster, have prosite annotations other than glycosyl_hydrol_f1_ the average pairwise sequence identity among the proteins with the glycosyl hydrolase family active site motif is ± %. ubiquitin-conjugating enzymes active site eight of the hits to the ubiquitin_conjugat_ prosite pattern occur in the same cluster. of the total residues in the cluster, have alternate prosite annotations. the average pairwise sequence identity among the proteins with the ubiquitin-conjugating enzyme active site motif is ± %. figure 5b shows two examples of environments around asparagine residues contained in the ubiquitin_conjugat_ motif. despite the fact that the cysteine residue toward the top of this figure is annotated in the prosite database as the catalytic residue, it is in the outskirts of the environment. because active sites are often dynamic, regions that are slightly removed from the center of catalytic activity may show stronger conservation than the active site itself. fewer than one-half of the residues in the environments are located within the prosite motif. statistical significance of the validation clusters since it may have been the case that the five validation clusters described above could have occurred by chance, we repeatedly reassigned the two million feature vectors into our clusters randomly and assessed the segregation of residues with the same prosite annotation into clusters. as all of the prosite patterns associated with the validation clusters reported above have at least five hits in our dataset, we limited our analysis to prosite patterns with at least five occurrences. in approximately 13% of trials, we observed one case where at least 75% of the hits to a prosite pattern occurred in a single cluster. the probabilities of obtaining two or three such clusters were % and %, respectively. a random trial in which four prosite patterns were each predominantly captured in a single cluster occurred only once, and we never observed five patterns to cluster according to these criteria. thus, the results reported above are statistically significant. we also evaluated the overall performance of the clustering algorithm by determining how well each prosite pattern with at least three hits in our dataset clustered. for each pattern, we identified the cluster in which the highest percentage of hits is represented. on average, ± % of the hits to a pattern are represented in the cluster that best captures that pattern. for the random clusterings described above, this number drops to ± %. if we exclude all patterns with fewer than five hits, ± % of hits occur in the best cluster, whereas only ± % are expected to cluster together by chance. discussion the major findings of this study are as follows. first, a binary representation of the feature vectors with a weighted distance metric does not lose significant information necessary for clustering and in fact improves the compactness and separation of clusters in a manual assessment of feature models built by hand. this is a surprising finding since one might guess that continuous valued features would contain more information. however, the simple division of discrete variables into "zero" or "not zero" and continuous variables into "less than median" and "more than median" outperforms the continuous features. further, the f-weighting scheme that we employed upweights features with good discrimination power when computing distances while retaining the binary representation, as shown in figure these results give us confidence that real 3d environmental clusters are recognizable by our distance metric. second, we have shown that the computational complexity of k-means clustering on million residues is feasible, with clustering completed within hours on a single modest cpu. the k-means algorithm is amenable to parallelization, and so we should be able to expand the granularity of our representation to not only include more atoms per residue, but also allow characterization of the "empty" space near residues, such as in pockets of proteins. the k-means algorithm reaches local minima, so we have begun to experiment with hierarchical k-means until the clusters are sufficiently small to allow hierarchical clustering. these approaches may be more robust. the choice to evaluate values of k up to is a somewhat arbitrary one. we eventually chose to work with k =. the histogram in figure shows that the median cluster size is but there is a very long tail. all our positive validation examples come from clusters in the range of to vectors, and so this may be a clue to focus our search for novelty in clusters within that range. a larger k might allow us to split some of the very large clusters. we can also experiment with different strategies for seeding the initial centers. it may be that our focus on surface points left few centers that match internal, hydrophobic environments. the large clusters may simply be undifferentiated hydrophobic environments, which account for a large volume of the total protein environments. a preliminary analysis of clusters with more than residues indicates that the top three amino acids occurring in those clusters are leucine, valine, and alanine. third, our method has found clusters that are enriched for prosite motifs, which are based primarily on sequence analysis. of course, these motifs have 3d conformations in the associated protein structures, and we have shown previously that these 3d conformations can be used as a seed to create a feature model that is more sensitive than the 1d sequence motif. not surprisingly, the addition of 3d information improves the motif because not only the identity of the amino acids, but also their relative positions can be encoded. in this work, we have shown further that a clustering of amino acid environments based on the feature radial concentric shells encoded in a weighted binary vector can detect the similarity of the 3d environments associated with prosite motifs. figure shows the detailed feature fingerprint associated with these four clusters. each is unique and picks up a different prosite motif. if these motifs had not been previously known based on sequence analysis, our clustering would now have suggested their existence. this forms the basis of our optimism that a complete analysis of the resulting clusters will yield not only other known 3d fingerprints, but also biologically novel motifs. in order to discover and characterize these novel motifs, we will need to systematically characterize the cluster properties of the clusters corresponding to known motifs and then use these properties to identify other promising leads. for example, in our five validated prosite clusters, only a small fraction of the vectors are annotated by prosite. are these closer to one another than to the other cluster members, or are they scattered uniformly throughout the cluster? if they are closer to one another, then we may need more cluster centers to distinguish subgroups, or a hierarchical clustering to show the relationships between subclusters. if they are interspersed, it may suggest that we have found some unrecognized sites with environments that are very similar to those of the prosite-annotated residues. thus in future work, we will need to dissect all the clusters in order to identify the key features of novel functional clusters.  we have developed a reduced representation for the environment around an amino acid in a protein. the representation is binary and can be used in a weighted form to outperform ostensibly "higher information content" representations in identifying compact and separable clusters. a preliminary k-means clustering of a 50% nonredundant subset of the pdb produced clusters, some of which clearly capture the key features of known prosite motifs as manifested in solved 3d structures. these results suggest that further refinement and analysis of these clusters may provide previously undetected functional sites and metrics for recognizing them. 
as a preliminary validation, we asked whether known 3d environments associated with prosite motifs were "rediscovered". our results demonstrate that we can cluster protein environments successfully using a simplified representation and k-means clustering algorithm. structural genomics initiatives are producing increasing numbers of three-dimensional structures for which there is little functional information. however, feature uses supervised machine learning and so is limited to building models for sites of known importance and location. we previously presented feature, a method for describing microenvironments around functional sites in proteins. this information will then allow us to find new clusters with similar characteristics that represent novel structural or functional sites.
 structural genomics initiatives are producing increasing numbers of three-dimensional structures for which there is little functional information. structure-based annotation of molecular function is therefore becoming critical. we previously presented feature, a method for describing microenvironments around functional sites in proteins. however, feature uses supervised machine learning and so is limited to building models for sites of known importance and location. we hypothesized that there are a large number of sites in proteins that are associated with function that have not yet been recognized. toward that end, we have developed a method for clustering protein microenvironments in order to evaluate the potential for discovering novel sites that have not been previously identified.  we have prototyped a computational method for rapid clustering of millions of microenvironments in order to discover residues whose surrounding environments are similar and which may therefore share a functional or structural role. we clustered nearly, environments from protein chains and defined clusters. as a preliminary validation, we asked whether known 3d environments associated with prosite motifs were "rediscovered". we found examples of clusters highly enriched for residues that share prosite sequence motifs.  our results demonstrate that we can cluster protein environments successfully using a simplified representation and k-means clustering algorithm. the rediscovery of known 3d motifs allows us to calibrate the size and intercluster distances that characterize useful clusters. this information will then allow us to find new clusters with similar characteristics that represent novel structural or functional sites. august – september the second automated function prediction meeting la jolla, ca, usa 