BACKGROUND
protein function and structure are inherently linked, with molecular interactions determined by the shape and energetics of the participating structures.
knowledge of structure is especially important for elucidating detailed molecular mechanisms of function for the development of disease therapeutics and pharmaceuticals.
galvanized by the protein structure initiative, the field of structural genomics has begun to solve the structures of proteins in high-throughput  <cit> .
by solving representative structures throughout protein structure space, researchers can more fully determine the relationship between protein structure and function  <cit> .
many of the solved structural genomics targets, however, lack annotation regarding the proteins' biological functions.
numerous methods exist for predicting protein function computationally, with most using some kind of sequence or structure-based similarity to match the query protein to other proteins or trained models of known function.
the most popular sequence-based methods employ hidden markov models to detect matches to functional domains, such as pfam  <cit>  and superfamily  <cit> , or use regular expression patterns and shorter motifs, such as prosite  <cit>  and prints  <cit> .
structure-based methods include those that use structural alignments of the protein backbone  or secondary structure elements , those that match spatial residue geometry such as 3d templates  <cit> , and those that use a combination of structural features more abstractly - for example, feature  <cit> .
since most of these methods use prior knowledge in a supervised fashion, they are good at detecting functions that are already well characterized in proteins that bear similarity in sequence and/or structure to known proteins.
by design, many unannotated structural genomics proteins have sequences with no detectable homology to known structures; these structures are, not surprisingly, often dissimilar in structure as well  <cit> .
consequently, most methods that rely on conserved similarities in sequence or structure may not successfully predict function for these proteins.
because structure is more conserved than sequence  <cit> , structure-based methods may have more success  <cit> , but even structure-based methods will struggle if structural similarity to known proteins is very low.
in these cases, we have shown that an abstract 3d representation, called a microenvironment, can better model and predict functional sites  <cit> .
most methods for function annotation require the sequence or structure motif to be present in a continuous stretch of polypeptide.
this requirement makes the discovery of convergent or highly divergent motifs more difficult.
3d templates - specifically the "reverse template" technique - can be used to describe recurring residue triads that are discontinuous in sequence, but this method has not been applied in a comprehensive manner across a large set of structures.
similarly, cleft- and patch-finding algorithms such as castp  <cit> , pocketpicker  <cit> , and patchfinder  <cit>  can identify interesting regions of protein structures, but have not been applied comprehensively to discover recurring motifs.
unsupervised approaches are useful for discovering patterns and groups in data without prior information or training.
a recent study by manikandan and colleagues  <cit>  clustered structural fragments from a fold-unique subset of the protein data bank   <cit>  based on backbone angles, resulting in groups of fragments with similar conformations.
they then associated each fragment with gene ontology  terms  <cit>  to produce significantly enriched functional labels for groups.
their findings support the idea that clustering of sub-structures can identify novel functional motifs.
in this work, we present an unsupervised procedure for clustering microenvironments in protein structures.
the microenvironments are described using physicochemical properties radially averaged around a site of interest and therefore do not constrain residue identities or continuity in sequence or structure.
we have used this representation previously to build robust, supervised models of protein function  <cit>  and to perform a preliminary study of unsupervised clustering  <cit> .
we have improved the clustering procedure by better defining the biological context and decreasing feature redundancy, and applied a discriminating cluster selection method to produce more coherent groups, which we then annotate using external knowledge from several sources.
we demonstrate that this approach, applied to a set of cysteine  residues from a subset of the pdb, is able to rediscover known functions, distinguish between functional sub-classes, make compelling functional site predictions for individual proteins, and identify novel groups of interesting microenvironments.
we therefore show the value of representing protein structure and functional sites using microenvironment similarity.
cysteine is an interesting initial residue on which to focus because it plays diverse and widespread roles in biology, including in proteolysis, redox-catalysis, structural stability, and metal-binding  <cit> .
RESULTS
we used k-means followed by hierarchical clustering to group a set of cysteine-based microenvironments into clusters.
to approximate the biological signal present in a cluster, we used a literature-based metric called functional coherence  <cit>  which measures the degree to which a set of proteins shares similar literature.
the resulting clusters were associated with descriptive terms derived from curated databases and literature abstracts associated with the proteins in each cluster.
the overall approach is outlined in figure  <dig>
evaluation of the functional coherence measure
in order to determine the suitability of the functional coherence measure for protein clusters, we compared the functional coherence of random protein clusters and clusters associated with six prosite patterns .
the functional clusters ranged in size from six proteins to over  <dig> proteins.
functional clusters attain much higher functional coherence scores than random clusters, with median values of  <dig> ,  <dig> , and  <dig>  for the prosite min, prosite subsets, and prosite max functional clusters, respectively, and  <dig>  for random clusters .
we tested the functional coherence measure using clusters associated with six functional motifs from prosite.
the minimum number of proteins is the smallest cluster size we used for that particular prosite pattern, derived from training sets from existing feature models.
the maximum number is the total number of proteins in swiss-prot annotated to that pattern.
we also calculated the functional coherence of the diluted clusters to see how the amount of signal in a cluster affects its functional coherence .
functional coherence clearly decreases as % signal decreases; when the size of the cluster is fixed, the relationship is approximately exponential.
note that the slight increase in functional coherence at very low % signal in the additive dilution sets is due to sharp increases in cluster size; the increase is negligible at the cluster sizes we worked with.
based on these observations, we set an empirical cutoff at  <dig>  to distinguish functionally coherent clusters from non-functional clusters.
application of two-phase clustering to cys microenvironments
we applied our two-phase clustering strategy to a data set of  <dig>  feature microenvironments centered on cysteine residues.
the procedure is described in detail in the methods section; briefly, we reduced the microenvironment vectors using principal component analysis and clustered them using k-means , and then applied hierarchical clustering-based cluster selection to each of these coarse-grained clusters.
all clusters with at least five microenvironments were considered for further analysis, since five is the minimum number of sites we have used for training feature models in the past.
the cluster selection produced  <dig> clusters with more than five microenvironments.
using a functional coherence cutoff of  <dig> , we identified  <dig> clusters to annotate in more detail .
we also investigated clusters with high internal correlation  but low functional coherence.
we annotated the  <dig> functionally coherent clusters automatically with information from the swiss-prot knowledgebase  <cit> , pdb heteroatoms, and pubmed  <cit>  abstracts, dividing the results into rediscoveries of known functional sites , novel predictions for individual proteins , and clusters representing potentially novel functional sites .
information for all clusters is available online  <cit> .
when we examined clusters with low functional coherence but high internal correlation, we found that many were associated with disulfide bonds, surface-exposed regions, or experimental artifacts such as alternate coordinates.
coarse clusters  <dig> and  <dig> seem to consist predominantly of these types of clusters.
upon examining clusters with higher functional coherence, however, we see that they have more functional themes.
coarse clusters  <dig> and  <dig> are enriched for zinc-binding, coarse clusters  <dig> and  <dig> are heavily annotated with cytochromes, and coarse cluster  <dig> contains iron-binding clusters.
although the cytochrome-associated clusters are only found in coarse clusters  <dig> and  <dig>  clusters related to metal ion-binding, phosphatase, and kinase activity are found across multiple coarse clusters.
these clusters represent functional annotations that are already known in that all or the vast majority of sites are annotated for that function.
fc = functional coherence.
rediscovery of known sites
we identified many examples of known functional sites, including copper binding sites, tryosine phosphatase active sites, and a motif associated with ser/thr protein kinases.
we present our observations on two of these functional sites, copper binding and zinc binding, in more detail below.
copper-binding proteins
clust33-sub <dig> represents a copper-binding site, with the majority of its member proteins belonging to the blue copper family of cyanins .
one of the structures is bound to zinc rather than copper, but is known to bind copper in that location.
all other structures in clust33-sub <dig> are bound to copper.
the microenvironment contains two his residues helping to coordinate the ion, and a met residue, which is not always bound but is always nearby.
terms associated with copper-binding and electron transport dominate annotations for this cluster.
another copper-binding cluster  is in an entirely different coarse cluster, and this environment seems to be associated with the family of multicopper oxidases.
again, all structures are bound to copper through the central cys residue, in addition to two his residues.
in three out of the five microenvironments, a met residue is present but not bound.
the annotations center around copper-binding, but with keywords for "oxidoreductase" rather than "electron transport", distinguishing the function of this cluster from that of clust33-sub <dig>  interestingly, both of these copper-binding clusters correspond to the same type of copper center - type  <dig>  which is coordinated by cys, two his residues and a fourth residue  <cit> .
in plastocyanins, the fourth residue is a met, while in multicopper oxidases it is often substituted by a non-coordinating residue  <cit> .
this is consistent with our observations in these two clusters.
zinc-binding clusters
we also identified clusters representing conserved environments in protein kinases and cytochrome c proteins, as well as iron, iron-sulfur, and zinc binding sites.
zinc binding is particularly interesting, as there are many motifs and catalytic sites known to bind zinc  <cit> .
figure  <dig> shows four types of zinc binding sites present in distinct coarse clusters in our data set.
the first three types are mononuclear, where a single zinc ion is coordinated by different numbers of cys and his residues -  <dig> cys,  <dig> cys and  <dig> his, or  <dig> cys and  <dig> his.
zinc-binding of this type is typically for protein structural stability.
the fourth type shown is a cocatalytic dinuclear zinc site coordinated by a more diverse set of residues, including his, asp, cys, and water.
these types of sites are found in metalloenzyme active sites, where the zinc ion is required for catalytic activity  <cit> .
since cysteine residues are often involved in binding metal ions, it is not surprising to see many clusters with metal-binding as the dominant functional annotation.
we were, however, intrigued by the fact that many - such as zinc - did not group into the same coarse cluster.
to investigate whether k-means was partitioning the clusters inappropriately, we combined  <dig> zinc-binding-associated clusters belonging to four coarse clusters into one large cluster and ran it through the cluster selection process again.
the exact same clusters were produced , indicating that the cluster boundaries from k -means are robust.
although many of the zinc-binding clusters differ according to the number and type of amino acids that coordinate the zinc, several disparate clusters do bind zinc in a similar manner.
when we examined the sets of principal component vectors for clusters with identical coordination types, we confirmed that there are indeed significant differences between them.
therefore, while the coordinating residues are identical, there are apparently subtle ways - specific principal components - in which they differ.
as each principal component is composed of weighted versions of the original microenvironment features, we can deduce which features contributed most heavily to these differences.
for the four clusters that bind zinc using four cysteines, features corresponding to arginine, histidine, and non-canonical residues vary significantly, as do features related to aromatic and aliphatic carbons and amide nitrogens.
the five clusters binding zinc using three cysteines and one histidine differed in features related to val, phe, cys, and thr residues, as well as aromatic and aliphatic carbons, hydroxyl and carboxyl oxygens, and charge.
the two c2h <dig> clusters also showed distinctions in features related to aromatic atoms, as well as amide atoms, different types of charges, and leu and his residues.
see additional files  <dig>   <dig> and  <dig> for more details on the zinc cluster analysis.
predictions of functional sites
we identified several microenvironments that may be novel metal-binding sites, some of which have supporting evidence or predictions made by other methods .
several proteins in clust1-sub <dig>  a zinc-binding cluster, have not been proven to bind zinc at the sites specified .
their microenvironments are highly suggestive of zinc binding, with the salient features being the presence of several his residues and occasionally an asp or glu residue around the central cys .
these annotations represent predictions for proteins in clusters where the function can be readily identified.
the functional coherence for clust1-sub <dig> is  <dig>  and functional coherence for clust22-sub <dig> is  <dig> .
there is evidence that 1nyq and 1uc <dig> may bind zinc at those locations.
others have noted the presence of conserved his and cys residues in 1uc <dig> corresponding to those in our site, similar to zinc metalloenzymes and trna synthetases  <cit> .
goyal and mande  <cit>  also predicted metal-binding at the same location using a structural template method.
1nyq, a threonyl-trna synthetase, is already known to bind zinc  <cit> , but in the crystal structure zinc is bound at a location far from our site.
cys <dig> may thus be a novel zinc binding site for 1nyq.
the third protein, 1gy <dig>  is a udp-galactose 4'-epimerase from t. brucei  <cit>  that is not known or suspected to bind zinc.
clusters with potentially novel biological significance
there are many clusters with more obscure themes that may have some biological importance .
we describe several examples in more detail below.
these predictions represent clusters where the function is not obvious but reasonable evidence exists for a coherent functional theme, even if it is in a structural role.
fc = functional coherence.
a recurrent cys hydrophobic helical motif
clust8-sub <dig>  has  <dig> microenvironments, all of which are characterized by an alpha helix containing the central cys residue, whose sidechain is surrounded by an abundance of hydrophobic, aliphatic residues such as isoleucine, leucine, and valine.
the residues present in the microenvironment are discontinuous in sequence and structure, making it unlikely that other methods would be able to identify it.
since the microenvironment is not usually surface-exposed, it may be reasonable to exclude explicit functions such as catalysis or binding to small molecules.
interestingly, all but three microenvironments  are involved in leucine-rich hydrophobic interfaces within helix bundles.
buried cys residues typically participate in disulfide bridges and so the fact that these microenvironments consist of a solitary buried cys in a hydrophobic context is interesting and raises the possibility that it is playing more than a structural role.
there is, in fact, precedence for leucine-rich environments being involved in protein-protein binding with a cysteine residue potentially regulating the interaction  <cit> .
a potential phosphorylation motif
another intriguing example is clust5-sub <dig> .
this cluster contains  <dig> microenvironments, eight of which are from protein tyrosine kinases.
the site, however, does not correspond to the active site, but to a surface-exposed loop.
in the kinases and in one of the other four sites, a yeast aldose 1-epimerase, there is a tyrosine residue within or adjacent to the microenvironment.
one or two other sulfur-containing sidechains are also present.
since the kinases are all known to be phosphorylated, it is possible that the tyrosine in the microenvironment may represent a phosphorylation site.
in fact, one of these tyrosines, tyr <dig> in 1k9a:a, is annotated in swiss-prot as a putative autophosphorylation site .
the other kinase-associated sites are not annotated, but it is conceivable that they may also be phosphorylation sites, perhaps by autophosphorylation.
the other four microenvironments belong to two aminotransferases, an epimerase, and a viral coat protein, and the significance for these cases is not clear.
a solvent-exposed d-c-k surface motif
lastly, we present clust36-sub <dig>  a set of five surface-exposed microenvironments .
the microenvironments from this cluster come from five proteins: plakophilin- <dig> , involved in epidermal morphogenesis; tumor susceptibility gene  <dig> protein , part of a vesicular trafficking complex; s-phase kinase-associated protein  <dig> , the substrate recognition component of a protein degradation complex; a dna-directed rna polymerase ; and hexokinase- <dig> , involved in carbohydrate metabolism.
the proteins are diverse in function and come from evolutionarily diverse organisms.
four out of the five are annotated as phosphoproteins.
a striking feature, however, is the presence of a solvent-exposed asp-cys-lys motif, where the cys represents the center of the microenvironment.
as all of these residues are capable of being catalytically active, their solvent accessibility and placement together make it possible that this microenvironment could play a functional role.
some classes of enzymes utilize a cys-his-asp catalytic triad; for certain transferases it is posited that the his is not critical for catalytic activity  <cit> .
it is thus possible that the main functional elements are the cys and asp residues.
as both lys and his have basic sidechains, it is also possible that lys could perform a similar role as his in this context.
additional studies have identified conserved cys-glu-lys triads in the nitrilase superfamily  <cit>  and a similar triad in an amidase from p. aeruginosa  <cit> .
glu and asp are very similar amino acids and often perform analogous functional roles.
although these known sites tend to be found in catalytic clefts, they provide some support for this microenvironment's potential functional significance.
cluster annotation output
each cluster that scored  <dig>  or more for functional coherence was analyzed for enriched terms from swiss-prot, pdb hetatms, and pubmed abstracts as described in the methods.
summary html pages with lists of the top-ranked terms contain links to more detailed pages showing contributions to each term by swiss-prot, pdb, or pubmed id.
there are also external links to the source databases for each protein, hetatm, and literature abstract.
see figure  <dig> for sample screen shots.
the annotation output for each cluster in tables  <dig>   <dig> and  <dig> is available online at http://feature.stanford.edu/clustering/cys <cit> .
discussion
protein function prediction has traditionally concentrated on modeling known functional domains and motifs.
this becomes a problem when increasing numbers of newly discovered proteins lack similarity to existing ones and when the new proteins may contain novel biological functions.
in this work, we present a two-step unsupervised clustering procedure combined with automated knowledge-based characterization methods - a pipeline that can be applied over a large number of protein structures to discover potentially novel functional sites systematically.
this pipeline uses a site representation - the feature microenvironment - that is sequence independent and captures physicochemical properties in a radially averaged way.
although detailed geometric information is not retained, the representation is robust to differences in exact sequence or structure.
as shown in previous work  <cit> , this allows more robust detection of function in proteins that are evolutionarily more distant.
in defining optimal clusters in the hierarchical clustering step, we use both internal and external coherence measures.
node correlation gives an indication of how physically similar two sets of microenvironments are, while the functional coherence measure approximates the biological signal through shared literature connections.
this enables us to define a cutoff above which we consider a cluster for further investigation.
we have applied this pipeline to microenvironments centered on cysteine residues.
the resulting clusters recapitulate many well-known cysteine-related functions, such as metal-binding and tyrosine phosphatase activity; these clusters can easily be used to train supervised feature models.
in addition, we make three kinds of novel predictions: new annotations for individual proteins, new 3d motifs with putative function, and new 3d motifs with unknown function.
in particular, we predict novel zinc binding sites in structures 1nyq, 1uc <dig>  and 1gy8; a potential tyrosine phosphorylation motif; an aliphatic microenvironment motif that may play a structural role; and a microenvironment motif containing a potentially active residue triad.
a two-phase clustering approach allows for fewer initial assumptions
one of the drawbacks of k-means clustering is that we must specify the number of clusters beforehand.
although heuristics can provide reasonable estimates, it is still a challenge to set parameters when the true structure of the data is not known a priori.
in this work, we demonstrate a two-step approach that would allow for fewer assumptions in the initial clustering and provide better separation in subsequent analyses.
the ability to post-process large "coarse" clusters into smaller, more coherent clusters means that we do not have to attempt to divide all the objects into the most optimal groups at the outset, but can simply group them into coarse "ballparks".
we can then use more accurate but more expensive methods such as hierarchical clustering to identify finer-grained distinctions within the large groups.
our analysis of the zinc-binding clusters illustrates this point.
if we had had prior knowledge of these clusters, we may have attempted to constrain the k-means to produce a cluster with all of these.
the hierarchical clustering, however, picked out biologically reasonable clusters while freeing us from attempting to deduce the underlying structure of the data in the k-means step.
the boundaries between the zinc-binding clusters themselves were robust, as shown by combining and re-clustering.
using different coherence measures allows for flexibility in cluster selection
by adapting the method from raychaudhuri et al  <cit> , we select clusters from a hierarchical clustering to strike a balance between internal and external coherence.
higher internal coherence indicates that the microenvironments are physically similar, while higher functional coherence suggests better supporting evidence in literature and knowledgebases for the possible biological causes of the similarity.
we use a scoring function that is approximately equal in its weighting of these two coherence measures, but the function can be easily modified to suit particular needs.
to recapture only well-known functional sites, a function heavily weighted towards functional coherence would perform better.
weighting the function more towards internal coherence would produce clusters that are very physically similar, but may not have clear or meaningful biological significance.
in fact, many of the clusters may instead be artifactual or strictly structural, reflecting, for instance, ambiguously defined coordinates or disulfide bonds.
our method is flexible in that we can modify the scoring function to make different types of discoveries.
clusters that are already well characterized  may have one or two members that are not annotated with that particular function; we can then transfer the annotation indicated by the cluster analysis to those members.
clusters that emphasize internal coherence but have low functional coherence, on the other hand, may sometimes represent completely novel functional sites.
somewhere in between lies a third type of discovery - that of a 3-dimensional motif for a characterized function that did not previously have a defined motif.
these three types of discoveries could be described as "individual protein annotation", "motif identification", and "novel biological site", and each one is more difficult to validate than the former.
each type is, however, also more interesting from a discovery standpoint than the preceding type.
the approach identifies recurring microenvironments
through rediscovery of metal binding sites and active sites for tyrosine phosphatases, we demonstrate that this method is effective at identifying functionally important environments; further analysis of the zinc and copper binding examples shows that it can also be precise, distinguishing between different types of binding sites for the same ligand.
several of our novel predictions for individual binding sites can be corroborated by other methods or evidence in the literature, though there are also a few that are more novel.
1nyq is not known to bind zinc at the location we predict, but it does have other zinc binding sites, and the presence of multiple binding sites in the same protein is not uncommon.
the available knowledge for 1gy <dig> makes no indication of zinc binding activity.
more interesting are the clusters that have no readily apparent functional theme according to known database annotations and literature and yet have very similar physicochemical microenvironments.
in some cases, they correspond to distinct substructures, such as a repeating beta sheet motif.
this type of motif is known to make up entire domains in some cases, such as the pectin lyase-like fold  <cit> , which we find in clust4-sub <dig>  or may be repeated in different numbers on a smaller scale as with wd-repeats  <cit> , which we find in clust21-sub <dig>  in other cases, the environment does not correspond to a known structural motif; indeed, in the majority of cases, the residues involved are highly discontinuous in sequence.
although these are difficult to validate, they are also the most intriguing.
some may be functional regions involved in interaction with other proteins or molecules ; others may be involved in structural stability  or represent a remnant of shared evolutionary history.
when the microenvironments come from diverse proteins it becomes more likely that they demonstrate examples of convergent evolution on a small scale or the re-use of chemically and physically favorable elements -potential modular building blocks  <cit> .
indeed, protein domains may be defined as a combination of recurring substructures  <cit> , and the view that smaller units are important for function is supported by many studies  <cit> .
other tools exist which view protein structure space as consisting of sub-substructures or fragments, such as fragnostic  <cit> .
the use of microenvironments here provides a unique approach to this problem for it captures chemical properties of amino acids, which are major contributors to biological function, without constraining linearity in the sequence or structure.
we also do not assume any evolutionary relationship.
at lower levels of similarity, we may be able to detect environments that recur despite global differences, and environments that have converged from different origins.
recurring microenvironments may also reveal general principles for protein stability and function.
clustering is a useful tool for exploration and hypothesis generation
beyond recapitulating known functions and identifying potentially novel sites, our cluster analysis approach allows open-ended exploration of protein function space as described by microenvironments.
the hierarchical trees that underlie the cluster selection process themselves have inherent value; we can use them to see how similar functional microenvironments are to each other, perhaps teasing out evolutionary relationships or the changes needed to convert a particular environment into another.
when testing parameters for hierarchical clustering, we used data sets consisting of known groups of microenvironments based on prosite motifs, but the resulting trees did not always map cleanly back to those groupings.
often, individual microenvironments were excluded either because their inclusion negatively impacted the internal or external coherence, or because they were located in a different area of the tree.
both cases suggest that the microenvironments for these "singleton" sites differ in some way from that of the other sites mapped to the same prosite motif.
what makes these sites so different, and what implications does this have for their classification?
what might this say about the evolution of a particular function?
inspection of the overall tree of clusters can also lead to interesting questions, for we can see how the microenvironments of different functions relate to one another.
for example, different types of protease active sites - including zinc proteases, serine proteases, and thiol proteases - have microenvironments that cluster distinctly into different areas of a hierarchical tree .
these observations make sense given the diverse origins of proteases, many of which arose independently even while sharing very similar catalytic mechanisms  <cit> .
other dissimilarities - or similarities - between different classes of enzymes may be less well known and worth investigating.
CONCLUSIONS
structural genomics efforts are rapidly expanding the diversity of known protein structures.
the lack of functional annotation for many novel structures and the identification of novel biological functions are two problems that existing methods have yet to address.
we have developed an unsupervised approach for exploring protein structure-function space that identifies groups of recurring 3d protein microenvironments that can be discontinuous in sequence.
by using a two-phase clustering approach, we incorporate flexibility into the procedure, while the addition of external knowledge enables better filtering and interpretation of resulting clusters.
we applied this approach to a set of cysteine microenvironments, identifying many known functional site motifs as well as novel predictions for individual proteins and potentially novel biological motifs.
this approach can be applied across other amino acid data sets to discover additional recurring microenvironments.

 protein function and structure are inherently linked, with molecular interactions determined by the shape and energetics of the participating structures. knowledge of structure is especially important for elucidating detailed molecular mechanisms of function for the development of disease therapeutics and pharmaceuticals. galvanized by the protein structure initiative, the field of structural genomics has begun to solve the structures of proteins in high-throughput. by solving representative structures throughout protein structure space, researchers can more fully determine the relationship between protein structure and function. many of the solved structural genomics targets, however, lack annotation regarding the proteins' biological functions. numerous methods exist for predicting protein function computationally, with most using some kind of sequence or structure-based similarity to match the query protein to other proteins or trained models of known function. the most popular sequence-based methods employ hidden markov models to detect matches to functional domains, such as pfam and superfamily, or use regular expression patterns and shorter motifs, such as prosite and prints. structure-based methods include those that use structural alignments of the protein backbone or secondary structure elements, those that match spatial residue geometry such as 3d templates, and those that use a combination of structural features more abstractly - for example, feature. since most of these methods use prior knowledge in a supervised fashion, they are good at detecting functions that are already well characterized in proteins that bear similarity in sequence and/or structure to known proteins. by design, many unannotated structural genomics proteins have sequences with no detectable homology to known structures; these structures are, not surprisingly, often dissimilar in structure as well. consequently, most methods that rely on conserved similarities in sequence or structure may not successfully predict function for these proteins. because structure is more conserved than sequence, structure-based methods may have more success, but even structure-based methods will struggle if structural similarity to known proteins is very low. in these cases, we have shown that an abstract 3d representation, called a microenvironment, can better model and predict functional sites. most methods for function annotation require the sequence or structure motif to be present in a continuous stretch of polypeptide. this requirement makes the discovery of convergent or highly divergent motifs more difficult. 3d templates - specifically the "reverse template" technique - can be used to describe recurring residue triads that are discontinuous in sequence, but this method has not been applied in a comprehensive manner across a large set of structures. similarly, cleft- and patch-finding algorithms such as castp, pocketpicker, and patchfinder can identify interesting regions of protein structures, but have not been applied comprehensively to discover recurring motifs. unsupervised approaches are useful for discovering patterns and groups in data without prior information or training. a recent study by manikandan and colleagues clustered structural fragments from a fold-unique subset of the protein data bank based on backbone angles, resulting in groups of fragments with similar conformations. they then associated each fragment with gene ontology terms to produce significantly enriched functional labels for groups. their findings support the idea that clustering of sub-structures can identify novel functional motifs. in this work, we present an unsupervised procedure for clustering microenvironments in protein structures. the microenvironments are described using physicochemical properties radially averaged around a site of interest and therefore do not constrain residue identities or continuity in sequence or structure. we have used this representation previously to build robust, supervised models of protein function and to perform a preliminary study of unsupervised clustering. we have improved the clustering procedure by better defining the biological context and decreasing feature redundancy, and applied a discriminating cluster selection method to produce more coherent groups, which we then annotate using external knowledge from several sources. we demonstrate that this approach, applied to a set of cysteine residues from a subset of the pdb, is able to rediscover known functions, distinguish between functional sub-classes, make compelling functional site predictions for individual proteins, and identify novel groups of interesting microenvironments. we therefore show the value of representing protein structure and functional sites using microenvironment similarity. cysteine is an interesting initial residue on which to focus because it plays diverse and widespread roles in biology, including in proteolysis, redox-catalysis, structural stability, and metal-binding.  we used k-means followed by hierarchical clustering to group a set of cysteine-based microenvironments into clusters. to approximate the biological signal present in a cluster, we used a literature-based metric called functional coherence which measures the degree to which a set of proteins shares similar literature. the resulting clusters were associated with descriptive terms derived from curated databases and literature abstracts associated with the proteins in each cluster. the overall approach is outlined in figure evaluation of the functional coherence measure in order to determine the suitability of the functional coherence measure for protein clusters, we compared the functional coherence of random protein clusters and clusters associated with six prosite patterns. the functional clusters ranged in size from six proteins to over proteins. functional clusters attain much higher functional coherence scores than random clusters, with median values of,, and for the prosite min, prosite subsets, and prosite max functional clusters, respectively, and for random clusters. we tested the functional coherence measure using clusters associated with six functional motifs from prosite. the minimum number of proteins is the smallest cluster size we used for that particular prosite pattern, derived from training sets from existing feature models. the maximum number is the total number of proteins in swiss-prot annotated to that pattern. we also calculated the functional coherence of the diluted clusters to see how the amount of signal in a cluster affects its functional coherence. functional coherence clearly decreases as % signal decreases; when the size of the cluster is fixed, the relationship is approximately exponential. note that the slight increase in functional coherence at very low % signal in the additive dilution sets is due to sharp increases in cluster size; the increase is negligible at the cluster sizes we worked with. based on these observations, we set an empirical cutoff at to distinguish functionally coherent clusters from non-functional clusters. application of two-phase clustering to cys microenvironments we applied our two-phase clustering strategy to a data set of feature microenvironments centered on cysteine residues. the procedure is described in detail in the methods section; briefly, we reduced the microenvironment vectors using principal component analysis and clustered them using k-means, and then applied hierarchical clustering-based cluster selection to each of these coarse-grained clusters. all clusters with at least five microenvironments were considered for further analysis, since five is the minimum number of sites we have used for training feature models in the past. the cluster selection produced clusters with more than five microenvironments. using a functional coherence cutoff of, we identified clusters to annotate in more detail. we also investigated clusters with high internal correlation but low functional coherence. we annotated the functionally coherent clusters automatically with information from the swiss-prot knowledgebase, pdb heteroatoms, and pubmed abstracts, dividing the results into rediscoveries of known functional sites, novel predictions for individual proteins, and clusters representing potentially novel functional sites. information for all clusters is available online. when we examined clusters with low functional coherence but high internal correlation, we found that many were associated with disulfide bonds, surface-exposed regions, or experimental artifacts such as alternate coordinates. coarse clusters and seem to consist predominantly of these types of clusters. upon examining clusters with higher functional coherence, however, we see that they have more functional themes. coarse clusters and are enriched for zinc-binding, coarse clusters and are heavily annotated with cytochromes, and coarse cluster contains iron-binding clusters. although the cytochrome-associated clusters are only found in coarse clusters and clusters related to metal ion-binding, phosphatase, and kinase activity are found across multiple coarse clusters. these clusters represent functional annotations that are already known in that all or the vast majority of sites are annotated for that function. fc = functional coherence. rediscovery of known sites we identified many examples of known functional sites, including copper binding sites, tryosine phosphatase active sites, and a motif associated with ser/thr protein kinases. we present our observations on two of these functional sites, copper binding and zinc binding, in more detail below. copper-binding proteins clust33-sub represents a copper-binding site, with the majority of its member proteins belonging to the blue copper family of cyanins. one of the structures is bound to zinc rather than copper, but is known to bind copper in that location. all other structures in clust33-sub are bound to copper. the microenvironment contains two his residues helping to coordinate the ion, and a met residue, which is not always bound but is always nearby. terms associated with copper-binding and electron transport dominate annotations for this cluster. another copper-binding cluster is in an entirely different coarse cluster, and this environment seems to be associated with the family of multicopper oxidases. again, all structures are bound to copper through the central cys residue, in addition to two his residues. in three out of the five microenvironments, a met residue is present but not bound. the annotations center around copper-binding, but with keywords for "oxidoreductase" rather than "electron transport", distinguishing the function of this cluster from that of clust33-sub interestingly, both of these copper-binding clusters correspond to the same type of copper center - type which is coordinated by cys, two his residues and a fourth residue. in plastocyanins, the fourth residue is a met, while in multicopper oxidases it is often substituted by a non-coordinating residue. this is consistent with our observations in these two clusters. zinc-binding clusters we also identified clusters representing conserved environments in protein kinases and cytochrome c proteins, as well as iron, iron-sulfur, and zinc binding sites. zinc binding is particularly interesting, as there are many motifs and catalytic sites known to bind zinc. figure shows four types of zinc binding sites present in distinct coarse clusters in our data set. the first three types are mononuclear, where a single zinc ion is coordinated by different numbers of cys and his residues - cys, cys and his, or cys and his. zinc-binding of this type is typically for protein structural stability. the fourth type shown is a cocatalytic dinuclear zinc site coordinated by a more diverse set of residues, including his, asp, cys, and water. these types of sites are found in metalloenzyme active sites, where the zinc ion is required for catalytic activity. since cysteine residues are often involved in binding metal ions, it is not surprising to see many clusters with metal-binding as the dominant functional annotation. we were, however, intrigued by the fact that many - such as zinc - did not group into the same coarse cluster. to investigate whether k-means was partitioning the clusters inappropriately, we combined zinc-binding-associated clusters belonging to four coarse clusters into one large cluster and ran it through the cluster selection process again. the exact same clusters were produced, indicating that the cluster boundaries from k -means are robust. although many of the zinc-binding clusters differ according to the number and type of amino acids that coordinate the zinc, several disparate clusters do bind zinc in a similar manner. when we examined the sets of principal component vectors for clusters with identical coordination types, we confirmed that there are indeed significant differences between them. therefore, while the coordinating residues are identical, there are apparently subtle ways - specific principal components - in which they differ. as each principal component is composed of weighted versions of the original microenvironment features, we can deduce which features contributed most heavily to these differences. for the four clusters that bind zinc using four cysteines, features corresponding to arginine, histidine, and non-canonical residues vary significantly, as do features related to aromatic and aliphatic carbons and amide nitrogens. the five clusters binding zinc using three cysteines and one histidine differed in features related to val, phe, cys, and thr residues, as well as aromatic and aliphatic carbons, hydroxyl and carboxyl oxygens, and charge. the two c2h clusters also showed distinctions in features related to aromatic atoms, as well as amide atoms, different types of charges, and leu and his residues. see additional files and for more details on the zinc cluster analysis. predictions of functional sites we identified several microenvironments that may be novel metal-binding sites, some of which have supporting evidence or predictions made by other methods. several proteins in clust1-sub a zinc-binding cluster, have not been proven to bind zinc at the sites specified. their microenvironments are highly suggestive of zinc binding, with the salient features being the presence of several his residues and occasionally an asp or glu residue around the central cys. these annotations represent predictions for proteins in clusters where the function can be readily identified. the functional coherence for clust1-sub is and functional coherence for clust22-sub is. there is evidence that 1nyq and 1uc may bind zinc at those locations. others have noted the presence of conserved his and cys residues in 1uc corresponding to those in our site, similar to zinc metalloenzymes and trna synthetases. goyal and mande also predicted metal-binding at the same location using a structural template method. 1nyq, a threonyl-trna synthetase, is already known to bind zinc, but in the crystal structure zinc is bound at a location far from our site. cys may thus be a novel zinc binding site for 1nyq. the third protein, 1gy is a udp-galactose 4'-epimerase from t. brucei that is not known or suspected to bind zinc. clusters with potentially novel biological significance there are many clusters with more obscure themes that may have some biological importance. we describe several examples in more detail below. these predictions represent clusters where the function is not obvious but reasonable evidence exists for a coherent functional theme, even if it is in a structural role. fc = functional coherence. a recurrent cys hydrophobic helical motif clust8-sub has microenvironments, all of which are characterized by an alpha helix containing the central cys residue, whose sidechain is surrounded by an abundance of hydrophobic, aliphatic residues such as isoleucine, leucine, and valine. the residues present in the microenvironment are discontinuous in sequence and structure, making it unlikely that other methods would be able to identify it. since the microenvironment is not usually surface-exposed, it may be reasonable to exclude explicit functions such as catalysis or binding to small molecules. interestingly, all but three microenvironments are involved in leucine-rich hydrophobic interfaces within helix bundles. buried cys residues typically participate in disulfide bridges and so the fact that these microenvironments consist of a solitary buried cys in a hydrophobic context is interesting and raises the possibility that it is playing more than a structural role. there is, in fact, precedence for leucine-rich environments being involved in protein-protein binding with a cysteine residue potentially regulating the interaction. a potential phosphorylation motif another intriguing example is clust5-sub. this cluster contains microenvironments, eight of which are from protein tyrosine kinases. the site, however, does not correspond to the active site, but to a surface-exposed loop. in the kinases and in one of the other four sites, a yeast aldose 1-epimerase, there is a tyrosine residue within or adjacent to the microenvironment. one or two other sulfur-containing sidechains are also present. since the kinases are all known to be phosphorylated, it is possible that the tyrosine in the microenvironment may represent a phosphorylation site. in fact, one of these tyrosines, tyr in 1k9a:a, is annotated in swiss-prot as a putative autophosphorylation site. the other kinase-associated sites are not annotated, but it is conceivable that they may also be phosphorylation sites, perhaps by autophosphorylation. the other four microenvironments belong to two aminotransferases, an epimerase, and a viral coat protein, and the significance for these cases is not clear. a solvent-exposed d-c-k surface motif lastly, we present clust36-sub a set of five surface-exposed microenvironments. the microenvironments from this cluster come from five proteins: plakophilin-, involved in epidermal morphogenesis; tumor susceptibility gene protein, part of a vesicular trafficking complex; s-phase kinase-associated protein, the substrate recognition component of a protein degradation complex; a dna-directed rna polymerase; and hexokinase-, involved in carbohydrate metabolism. the proteins are diverse in function and come from evolutionarily diverse organisms. four out of the five are annotated as phosphoproteins. a striking feature, however, is the presence of a solvent-exposed asp-cys-lys motif, where the cys represents the center of the microenvironment. as all of these residues are capable of being catalytically active, their solvent accessibility and placement together make it possible that this microenvironment could play a functional role. some classes of enzymes utilize a cys-his-asp catalytic triad; for certain transferases it is posited that the his is not critical for catalytic activity. it is thus possible that the main functional elements are the cys and asp residues. as both lys and his have basic sidechains, it is also possible that lys could perform a similar role as his in this context. additional studies have identified conserved cys-glu-lys triads in the nitrilase superfamily and a similar triad in an amidase from p. aeruginosa. glu and asp are very similar amino acids and often perform analogous functional roles. although these known sites tend to be found in catalytic clefts, they provide some support for this microenvironment's potential functional significance. cluster annotation output each cluster that scored or more for functional coherence was analyzed for enriched terms from swiss-prot, pdb hetatms, and pubmed abstracts as described in the methods. summary html pages with lists of the top-ranked terms contain links to more detailed pages showing contributions to each term by swiss-prot, pdb, or pubmed id. there are also external links to the source databases for each protein, hetatm, and literature abstract. see figure for sample screen shots. the annotation output for each cluster in tables and is available online at http://feature.stanford.edu/clustering/cys. discussion protein function prediction has traditionally concentrated on modeling known functional domains and motifs. this becomes a problem when increasing numbers of newly discovered proteins lack similarity to existing ones and when the new proteins may contain novel biological functions. in this work, we present a two-step unsupervised clustering procedure combined with automated knowledge-based characterization methods - a pipeline that can be applied over a large number of protein structures to discover potentially novel functional sites systematically. this pipeline uses a site representation - the feature microenvironment - that is sequence independent and captures physicochemical properties in a radially averaged way. although detailed geometric information is not retained, the representation is robust to differences in exact sequence or structure. as shown in previous work, this allows more robust detection of function in proteins that are evolutionarily more distant. in defining optimal clusters in the hierarchical clustering step, we use both internal and external coherence measures. node correlation gives an indication of how physically similar two sets of microenvironments are, while the functional coherence measure approximates the biological signal through shared literature connections. this enables us to define a cutoff above which we consider a cluster for further investigation. we have applied this pipeline to microenvironments centered on cysteine residues. the resulting clusters recapitulate many well-known cysteine-related functions, such as metal-binding and tyrosine phosphatase activity; these clusters can easily be used to train supervised feature models. in addition, we make three kinds of novel predictions: new annotations for individual proteins, new 3d motifs with putative function, and new 3d motifs with unknown function. in particular, we predict novel zinc binding sites in structures 1nyq, 1uc and 1gy8; a potential tyrosine phosphorylation motif; an aliphatic microenvironment motif that may play a structural role; and a microenvironment motif containing a potentially active residue triad. a two-phase clustering approach allows for fewer initial assumptions one of the drawbacks of k-means clustering is that we must specify the number of clusters beforehand. although heuristics can provide reasonable estimates, it is still a challenge to set parameters when the true structure of the data is not known a priori. in this work, we demonstrate a two-step approach that would allow for fewer assumptions in the initial clustering and provide better separation in subsequent analyses. the ability to post-process large "coarse" clusters into smaller, more coherent clusters means that we do not have to attempt to divide all the objects into the most optimal groups at the outset, but can simply group them into coarse "ballparks". we can then use more accurate but more expensive methods such as hierarchical clustering to identify finer-grained distinctions within the large groups. our analysis of the zinc-binding clusters illustrates this point. if we had had prior knowledge of these clusters, we may have attempted to constrain the k-means to produce a cluster with all of these. the hierarchical clustering, however, picked out biologically reasonable clusters while freeing us from attempting to deduce the underlying structure of the data in the k-means step. the boundaries between the zinc-binding clusters themselves were robust, as shown by combining and re-clustering. using different coherence measures allows for flexibility in cluster selection by adapting the method from raychaudhuri et al, we select clusters from a hierarchical clustering to strike a balance between internal and external coherence. higher internal coherence indicates that the microenvironments are physically similar, while higher functional coherence suggests better supporting evidence in literature and knowledgebases for the possible biological causes of the similarity. we use a scoring function that is approximately equal in its weighting of these two coherence measures, but the function can be easily modified to suit particular needs. to recapture only well-known functional sites, a function heavily weighted towards functional coherence would perform better. weighting the function more towards internal coherence would produce clusters that are very physically similar, but may not have clear or meaningful biological significance. in fact, many of the clusters may instead be artifactual or strictly structural, reflecting, for instance, ambiguously defined coordinates or disulfide bonds. our method is flexible in that we can modify the scoring function to make different types of discoveries. clusters that are already well characterized may have one or two members that are not annotated with that particular function; we can then transfer the annotation indicated by the cluster analysis to those members. clusters that emphasize internal coherence but have low functional coherence, on the other hand, may sometimes represent completely novel functional sites. somewhere in between lies a third type of discovery - that of a 3-dimensional motif for a characterized function that did not previously have a defined motif. these three types of discoveries could be described as "individual protein annotation", "motif identification", and "novel biological site", and each one is more difficult to validate than the former. each type is, however, also more interesting from a discovery standpoint than the preceding type. the approach identifies recurring microenvironments through rediscovery of metal binding sites and active sites for tyrosine phosphatases, we demonstrate that this method is effective at identifying functionally important environments; further analysis of the zinc and copper binding examples shows that it can also be precise, distinguishing between different types of binding sites for the same ligand. several of our novel predictions for individual binding sites can be corroborated by other methods or evidence in the literature, though there are also a few that are more novel. 1nyq is not known to bind zinc at the location we predict, but it does have other zinc binding sites, and the presence of multiple binding sites in the same protein is not uncommon. the available knowledge for 1gy makes no indication of zinc binding activity. more interesting are the clusters that have no readily apparent functional theme according to known database annotations and literature and yet have very similar physicochemical microenvironments. in some cases, they correspond to distinct substructures, such as a repeating beta sheet motif. this type of motif is known to make up entire domains in some cases, such as the pectin lyase-like fold, which we find in clust4-sub or may be repeated in different numbers on a smaller scale as with wd-repeats, which we find in clust21-sub in other cases, the environment does not correspond to a known structural motif; indeed, in the majority of cases, the residues involved are highly discontinuous in sequence. although these are difficult to validate, they are also the most intriguing. some may be functional regions involved in interaction with other proteins or molecules; others may be involved in structural stability or represent a remnant of shared evolutionary history. when the microenvironments come from diverse proteins it becomes more likely that they demonstrate examples of convergent evolution on a small scale or the re-use of chemically and physically favorable elements -potential modular building blocks. indeed, protein domains may be defined as a combination of recurring substructures, and the view that smaller units are important for function is supported by many studies. other tools exist which view protein structure space as consisting of sub-substructures or fragments, such as fragnostic. the use of microenvironments here provides a unique approach to this problem for it captures chemical properties of amino acids, which are major contributors to biological function, without constraining linearity in the sequence or structure. we also do not assume any evolutionary relationship. at lower levels of similarity, we may be able to detect environments that recur despite global differences, and environments that have converged from different origins. recurring microenvironments may also reveal general principles for protein stability and function. clustering is a useful tool for exploration and hypothesis generation beyond recapitulating known functions and identifying potentially novel sites, our cluster analysis approach allows open-ended exploration of protein function space as described by microenvironments. the hierarchical trees that underlie the cluster selection process themselves have inherent value; we can use them to see how similar functional microenvironments are to each other, perhaps teasing out evolutionary relationships or the changes needed to convert a particular environment into another. when testing parameters for hierarchical clustering, we used data sets consisting of known groups of microenvironments based on prosite motifs, but the resulting trees did not always map cleanly back to those groupings. often, individual microenvironments were excluded either because their inclusion negatively impacted the internal or external coherence, or because they were located in a different area of the tree. both cases suggest that the microenvironments for these "singleton" sites differ in some way from that of the other sites mapped to the same prosite motif. what makes these sites so different, and what implications does this have for their classification? what might this say about the evolution of a particular function? inspection of the overall tree of clusters can also lead to interesting questions, for we can see how the microenvironments of different functions relate to one another. for example, different types of protease active sites - including zinc proteases, serine proteases, and thiol proteases - have microenvironments that cluster distinctly into different areas of a hierarchical tree. these observations make sense given the diverse origins of proteases, many of which arose independently even while sharing very similar catalytic mechanisms. other dissimilarities - or similarities - between different classes of enzymes may be less well known and worth investigating.  structural genomics efforts are rapidly expanding the diversity of known protein structures. the lack of functional annotation for many novel structures and the identification of novel biological functions are two problems that existing methods have yet to address. we have developed an unsupervised approach for exploring protein structure-function space that identifies groups of recurring 3d protein microenvironments that can be discontinuous in sequence. by using a two-phase clustering approach, we incorporate flexibility into the procedure, while the addition of external knowledge enables better filtering and interpretation of resulting clusters. we applied this approach to a set of cysteine microenvironments, identifying many known functional site motifs as well as novel predictions for individual proteins and potentially novel biological motifs. this approach can be applied across other amino acid data sets to discover additional recurring microenvironments. 
in order to identify novel 3d motifs that may be associated with molecular functions, we employ an unsupervised, two-phase clustering approach that combines k-means and hierarchical clustering with knowledge-informed cluster selection and annotation methods. detailed annotation results are available online for all clusters at http://feature.stanford.edu/clustering/cys. the emergence of structural genomics presents significant challenges in the annotation of biologically uncharacterized proteins. the use of microenvironments instead of backbone geometric criteria enables flexible exploration of protein function space, and detection of recurring motifs that are discontinuous in sequence and diverse in structure.
 the emergence of structural genomics presents significant challenges in the annotation of biologically uncharacterized proteins. unfortunately, our ability to analyze these proteins is restricted by the limited catalog of known molecular functions and their associated 3d motifs.  in order to identify novel 3d motifs that may be associated with molecular functions, we employ an unsupervised, two-phase clustering approach that combines k-means and hierarchical clustering with knowledge-informed cluster selection and annotation methods. we applied the approach to approximately cysteine-based protein microenvironments and identified interesting clusters, some of which represent known motifs, and some of which are novel, including several zinc binding sites. detailed annotation results are available online for all clusters at http://feature.stanford.edu/clustering/cys.  the use of microenvironments instead of backbone geometric criteria enables flexible exploration of protein function space, and detection of recurring motifs that are discontinuous in sequence and diverse in structure. clustering microenvironments may thus help to functionally characterize novel proteins and better understand the protein structure-function relationship. 