BACKGROUND
computer modelling and simulations plays an important role in the drug discovery process  <cit> .
all protein molecules are inherently dynamic and may have multiple conformers with similar energies in both the bound and unbound states  <cit> .
the model of preexisting conformations, together with the "induced-fit" where the ligand binding event causes a change in protein conformation, can explain the process of protein-ligand binding.
nevertheless the experimental static structures obtained by the x-ray and nmr techniques, let alone the modelled structures, are the bases for various structure-based drug design strategies such as de novo design and docking  <cit> .
in these efforts, the consideration of the protein flexibility is important  <cit> .
even the conformational change of a single amino acid residue can change the size, shape, and electrostatic property of the binding pocket.
comparisons of the x-ray structures of the pairs of the holo and apo forms indicate that the degree of structural change of the protein varies considerably  <cit> .
some protein undergoes rather large conformational change of the backbone.
in the majority of the cases studied, however, the conformational changes occur only at the side chain level.
here we present a new method, rotaimage, for modelling the plausible conformers for the ligand binding site given a fixed backbone structure.
there are numerous methods to predict the side-chain conformations as a component of protein structure prediction and protein redesign.
this is known as the classical side-chain prediction problem  <cit> .
most of these methods utilize the rotamer library that restricts side-chain torsion angles to a set of preferred or commonly-observed low-energy conformations of a particular side chain  <cit> .
due to its combinatorial nature, it is considered as np-hard and the number of conformers grows steeply as more residues are considered.
for example, 105~ <dig> bump-free conformers were generated for a set of  <dig> residues, while the number went up to over  <dig> conformers for  <dig> residues .
application of docking to all these conformers, albeit plausible, is not practical.
from now on, we call this computational burden due to high number of conformers to handle as 'computational complexity'.
various algorithmic heuristics have been applied in order to reduce the 'computational complexity' such as monte carlo simulations  <cit> , steepest-descent minimization with random restarts  <cit> , and self consistent mean-field approaches  <cit> .
the tool scwrl combines the dead-end elimination  algorithm, which restricts the conformational space, with an exhaustive but fast search of the remaining conformational space  <cit> .
1the residues within  <dig> Å from the ligand ensemble
2the residues within  <dig> Å from the 3d points that are within  <dig> Å from flrs
3the residues showing 'conditional' contacts with the 3d points
4bit strings differ by less than  <dig> bits were merged
5the ratio defined as /
6cpu time elapsed using an intel xeon e <dig> cpu operating at  <dig>  ghz with  <dig> gb of main memory  on a linux box.
an alternative approach, called dynasite, has been developed with the aim of reducing the 'computational complexity' by clustering the conformers based on structural similarities and performing docking against a representative conformer of each cluster  <cit> .
it used principal component analysis  to cluster the conformers based on rmsd between the flexible side chain atoms and successfully generated one of the known conformers starting from a different conformer as a template.
however, some practical limitations were noticed with this approach.
in order to keep the number of conformers for clustering under a practical limit , the rotamer combination was restricted to the pocket residues with movements observed experimentally; the maximum number of pocket residues was  <dig> for the proteins studied  <cit> .
each conformer of the pocket residues generates a unique shape of complementary pocket volume.
thus clustering based on the pocket shape dissimilarity would be equivalent to that based on structural rmsd between conformers.
our method presented here, rotaimage, clusters the pocket conformers based on the dissimilarity of their complementary pocket volumes.
the shape similarity between two different volume objects can be defined as a relative volume overlap between them.
since they are already in common coordinate system, the relative volume overlap can be numerically integrated over a set of three-dimensional  grid points that encompass the ensemble of the pocket volumes.
the grid spacing controls the granularity of volume assimilation.
at its given level, the pocket volumes that differ only in fine detail can be treated as identical.
computationally, each 3d volume object is distinguished by the status of every one of the 3d grid points whether one is inside or outside the volume.
the status of a point is encoded into a bit position of a string, whose value instances a particular pocket surface shape.
this is widely used in the field of 3d image recognition in computer science.
representation of a volume object by a bit string enables efficient operation of tasks such as identification of those objects that are treated as having identical shapes at the given granularity and calculation of similarity index between two objects.
for example, the former can be achieved by storing the bit strings into a hash table.
while preserving the connection between a conformer and a bit string, only unique strings are identified and used in the subsequent analyses.
compared to the original number of conformers, one would expect reduction in the number of unique strings.
the reduction in 'computational complexity' was substantial with our test cases, allowing to enumerate sterically allowed conformers with more pocket residues than those used by dynasite and to yield a manageable number of unique bit strings for clustering.
calculation of the dissimilarity between two strings, defined as the tanimoto coefficient between them, involves bitwise and and or operations and should be more efficient than that of rmsd between two conformers.
application of standard clustering algorithms using the dissimilarity matrix would segregate the pockets by the similarity in shape.
selection of a representative pocket shape from each cluster would reduce the 'computational complexity' to a degree amenable to the downstream ligand docking in a practical way.
for example, each of our test cases yielded a handful of clusters.
here we present details of rotaimage and demonstrate its utility by modelling the ligand binding site of human matrix metalloproteinase- <dig>  and - <dig> , which have been actively studied due to their pharmacological and biochemical importance  <cit> .
methods
algorithm
the main objective of our algorithm, rotaimage, is to manage the ligand binding pocket shape using a bit string and to apply this technique to reduce the 'computational complexity' in handling the binding site conformers generated through the exhaustive search of rotameric combination of side chains on fixed backbone.
there are three preparatory steps prior to the main algorithm:  recognition of binding site residues;  mapping the binding pocket by 3d points;  generation of multiple binding site conformers by rotamer assignment and concurrent checking for steric clashes.
the core steps include checking the contact between the 3d points and each conformer and binary representation of the contact configuration, and pruning the conformers that produce identical bit strings.
the resulting set of bit strings are then analyzed using standard clustering algorithms.
the algorithm is outlined in figure  <dig> and described below in detail.
recognition of binding site residues and mapping the binding pocket by 3-d points
identification of ligand binding pockets and analysis of their shapes have been an active area of research, as reviewed by weisel et al.
<cit> .
there are many algorithms available for this, such as pass  <cit> , pocket  <cit> , ligsite  <cit> , surfnet  <cit> , castp  <cit> , and pocketpicker  <cit> .
our main objectives are to explore the conformational varieties of the ligand binding site via rotameric combination, and to map the corresponding variations of the pocket shape.
for this, we need a maximally expanded pocket where the side chains of the pocket residues are substituted by ala. thus the following simple and straightforward approach would suffice for our purpose.
for a given protein, the crystal structures of reasonably high resolution are collected.
if multiple structures are available, one of them is chosen as a template and all the others are superposed to it.
since our algorithm assumes fixed backbone conformation, any outliers in terms of backbone overlaps are excluded from consideration.
although our algorithm should work with a template structure of either ligand-bound  or ligand-free  form, we describe first the procedure for a halo form as the template.
the superposition of protein backbones creates a ligand ensemble if multiple structures of ligand complexes are available.
in order to identify the residues that are subject of conformational search, we conduct multiple steps of selection and pruning .
firstly, all protein residues that are within  <dig> Å of the ligand ensemble are identified and refer to as the 'first layer residues '.
these residues except for gly are then substituted with ala. this creates an afore-mentioned artificial volume enlarged compared to the original ligand-binding pocket.
it would be the volume maximally accessible by the exploration of side-chain conformations with fixed backbone atoms.
nevertheless, it is referred to as the ligand-binding pocket.
the second step is the generation of the 3-dimensional points that map this ligand-binding pocket.
as mentioned above there are several algorithms available for this and we use pocket, which generates a lattice-like 3d array and allows rather simple manipulation of the lattice spacing.
the lattice spacing is set to  <dig>  Å. the 3d lattice points fill in the pocket by approaching the binding site residues as close as their van der waals radius.
the points that are more than  <dig> Å away from the binding site residues or ligand ensemble are trimmed.
once side chains are put back into the flr, they are likely in contact with the outer layer of the 3d points.
the last step is the recognition of the residues whose rotameric combination would be explored.
if we limit the scope to those residues that might have direct contacts with the 3d points and do not allow simultaneous flexible movement of residues deeper inside the protein core, most rotameric variations except a few would face resistance from the wall of those secondary residues.
hence, it would make more sense to consider the residues underneath the pocket surface than the residues within a certain distance from the ligand ensemble like the flrs.
for convenience, we define the 'second layer residues ' as those residues within  <dig> Å from the 3d points that are in contact with flrs.
some flrs are bound to be included in slrs, but not all of them.
selection of flrs depends on the ligands included in the ensemble since the ligands are filtered by the distance from the flrs.
on the other hand, selection of the slrs is not directly influenced by the choice of the ligand ensemble.
rather the shape of the pocket dictates the distribution of the 3d points, which, in turn, governs the slrs.
if no halo form can serve as the template structure, one would select flrs manually based on prior knowledge from literature or skip it to the 3d point generation.
for the latter case, the potential pocket residues are not substituted by ala and thus the pocket is not maximally expanded.
once 3d points are generated, slrs can be identified by the same procedure.
however the number of slrs would be somewhat less than that of the former.
rotamer combination and steric clash tests
we take into account the side chain flexibility by placing the so-called backbone-independent rotamers  <cit>  back on each of the slrs defined in the previous step and performing an exhaustive search of binding site conformers.
in general, the computational load for enumerating combinations of rotamers and subsequent filtering of the steric clashes in the resulting conformers grows exponentially with increasing number of rotamers.
in order to circumvent this problem, the rotamer library is reduced by checking the bumping between the main chain and the side chain of each rotamer using equation   <cit> .
two atoms a <dig> and a <dig> are considered to clash if
where ctd stands for clash tolerance distance.
based on the reduced library of the surviving rotamers only, the interactions between the residues are mapped as a graph, which is then searched by a backtracking and branch-and-bound algorithm that concurrently checks the bumping between the side chain atoms of each pair of residues.
this part of our algorithm follows the published graph theoretic cluster algorithm in scwrl  <cit> , except for the step of dead-end elimination and the scoring functions themselves.
binary image representation in protein binding site
the 3-dimensional points representing the enlarged binding pocket as obtained in the first step are screened for overlap with the atoms of each conformer that has been generated by rotamer combination and that has survived the subsequent bumping checks.
the contact between a binding site point 'p' and a slr atom 'a' is evaluated using
where cpd stands for contact padding distance, which is set to  <dig>  Å. summarizing the results over all the conformers, the points always in contact with some slrs regardless of conformers are eliminated, while the points always free of contacts are set aside and included later in the complete construction of the binding site.
only those points in 'conditional' contacts depending on the conformers are retained to discriminate the conformers.
for some residues in the slrs, none of the rotamers may contact the 'conditional' points at all; these slrs are eliminated.
the rest of the slrs, which have 'conditional' contacts with the 3d points, have potential for modulating the pocket shape and are defined as 'conditional contact residues '.
as shown in figure  <dig>  each conformer is represented by a configuration of which points are in contacts or not.
as it is a combination of binary states, the result is conveniently encoded by a bit string where each bit designates whether the corresponding point is in contact or not.
such representation of a 3-dimensional object by a bit string has been widely used in the field of image recognition in computer science  <cit> .
pruning multiple conformers having identical bit strings
the mapping relationship between the bit strings and the conformers is stored in a hash table.
by looking up those strings that are observed more than once, we can identify the strings that are mapped to multiple conformers.
these conformers have the identical status of contacts with the 3d points, i.e., their pocket shapes are indistinguishable at the specified ctd in equation .
there are several situations when this can happen.
as described in the previous section, some slrs are not included in the ccr list.
their rotamers would not generate new bit strings.
even for ccrs, some of their rotamers may not contact the 3d points, resulting in some redundant strings.
it is likely to occur at the periphery of the pocket.
besides, the coarser 3d points may cause the less sensitive differentiation of conformers.
in such cases identical bit strings may also result from different conformers.
since we keep track of which conformers are assigned to which bit strings, we do not lose any detail and reduce the computation complexity by dealing with non-redundant bit strings in the subsequent process.
clustering analysis of multiple binding sites and selection of representative conformers
the shape of the binding site is approximated using a set of 3d points, which are recorded as simple bit strings of length equal to the number of points.
each bit position corresponds to a sphere centered at a defined 3d point.
a shape-fingerprint tanimoto  coefficient between two such bit strings  <cit> , given by
measures the proportion of bits shared between the two strings, where na and nb represent the number of bits set in the strings a and b, respectively, while na b is the number of bit position set commonly in a and b. this is equivalent to a finite numerical integration of the relative volume overlap between two 3d volume objects.
a relative volume overlap between two 3d objects can be considered as one of the similarity indices, whose approximation can be given by a tanimoto coefficient.
with such a similarity index, clustering analysis such as multidimensional scaling  can be performed.
the optimum member of clusters is determined through a visual inspection of the mds plot in 3d using ggobi  <cit> .
mds was conducted using the r statistical system  <cit> .
a two-way hierarchical clustering of both bit strings and bits can be useful in analyzing the dependency between conformers and 3d points.
it was done with the linux implementation of cluster  <dig>   <cit>  using an m × n bit pattern matrix, where m and n are the number of unique bit strings and the bit size, respectively.
the time complexity of complete linkage hierarchical clustering is known as o  <cit> .
it should be noted that hierarchical clustering involving a few tens of thousands of bit strings can take extremely long .
one would need a representative conformer for each cluster for follow-up applications such as virtual screening or structural analyses.
since we use bit strings, a numerical averaging would not make sense.
we choose the medoid string as the representative of each cluster.
the medoid is defined as the member of the cluster whose average dissimilarity to all the other members is minimal  <cit> .
the pocket shapes and conformers corresponding to the medoid strings can be retrieved from the stored mapping information  of methods).
RESULTS
target proteins
we have tested our algorithm, rotaimage, by modelling the ligand-binding pockets of mmp- <dig> and mmp- <dig>  there are several reasons why we have tested our algorithm using these two mmps:  they are important targets for drug design and many inhibitors have been developed  <cit> ;  multiple ligand-bound complex crystal structures have been determined for each of them at reasonably high resolution  <cit> ;  most importantly, their crystal structures showed multiple conformer configurations in the ligand binding pocket  <cit> .
in addition, their conformational differences are large enough to prohibit rigid-body docking simulations of a known ligand from one configuration to the crystal structures from another configuration.
it would be interesting to see whether we can recover all of the conformers seen in the crystal structures from its clustered pools of conformers, or more precisely, whether those ligands could be fit into the representative binding pocket shapes that would result from the clustering of a number of shapes.
it would be more important to know how many clusters we have to consider in order to cover all the experimentally observed ligands.
beyond the commonalities, the ligand binding sites of mmp- <dig> and mmp- <dig> have quite distinct shapes and properties.
the side chain of arg  <dig> of mmp- <dig> limits the s1' pocket to a size suitable for an aromatic ring, while the corresponding residue in mmp- <dig> is replaced by leu  <dig>  <cit> , creating a long channel called s1'*  <cit> .
consequently, many more residues are involved in mmp- <dig> than mmp- <dig>  by testing our algorithm with cases of different complexities, we may gain more insight on variations of its performance.
generation of multiple binding site images
we downloaded eight and seven crystal structures determined at a resolution of  <dig>  Å or higher for mmp- <dig> and mmp- <dig>  respectively, from protein data bank   <cit> .
each set of proteins were superposed into a common reference structure  and 1xuc  for mmp- <dig> and mmp- <dig>  respectively).
one of the crystal structures of mmp- <dig> displayed a backbone structure distinct from the rest and was excluded in the subsequent analysis.
otherwise the average rmsd among backbone cα atoms were  <dig>  Å and  <dig>  Å for mmp- <dig> and mmp- <dig>  respectively.
the residues within  <dig> Å from the ligand ensemble  were identified and substituted with ala. the enlarged pockets were then filled with 3d lattice points of  <dig> Å spacing.
since flrs are determined based on the distances from the known ligands, they may reflect the current repertoire of ligands.
in order to remove such a bias and use residues that are within a constant depth underneath the pocket, we looked for residues within  <dig> Å from the 3d points.
these residues are referred to as slrs.
see figure  <dig>  for the definition of flrs and slrs.
some flrs deep inside the protein core were not used as slrs, while new ones were added at the periphery where the known ligands did not reach .
the next step involved an exhaustive search of conformers through rotamer combination and a concurrent bumping check.
in order to tolerate some uncertainty in the atomic positions, we also adopted the clash tolerance schemes defined in equation , where ctd was set at  <dig>  Å  <cit> .
for each conformer, the 3d points that were in contact with the side chain atoms were screened using equation  by setting cpd and a to  <dig>  Å and van der waals radius, respectively.
after scanning all the conformers, the points were classified into two groups.
when this scheme was applied to mmp- <dig>   <dig> residues out of the flrs were retained as ccrs .
in contrast, a smaller reduction occurred with mmp- <dig>  i.e., from  <dig> flrs to  <dig>  the number of 3d points indicated that the ligand-binding pocket of mmp- <dig> was ~50% larger than the binding pocket of mmp- <dig> .
after excluding those points free of contact with any of the conformers, there were twice as many 3d points with conditional contacts in mmp- <dig> than in mmp- <dig> .
the number of ccrs or 3d points showing conditional contacts is correlated to the size of the pocket surface area, not directly to the volume.
these numbers were in huge excess of the volume increase in mmp- <dig> compared to mmp- <dig>  indicating a larger ratio of contact surface-to-volume in the former than in the latter.
this may be explained by the fact that mmp- <dig> had a long and extended binding pocket unlike mmp- <dig>  which had a globular ligand-binding site  <cit> .
the 'computational complexity' due to a large number of conformers is governed by the number of ccrs, while the number of 3d points showing conditional contacts with ccrs dictates the variety of pocket shapes.
in this regards, mmp- <dig> and - <dig> were useful examples in assessing the complexity associated with these variables.
while the exhaustive rotameric combination generated  <dig>  sterically allowed conformers for mmp- <dig>  the same procedure produced over  <dig> billion conformers for mmp- <dig>  since the number of conformers for mmp- <dig> was too large to be handled on a reasonable time scale, we decided to split the number of 3d points of mmp- <dig> into half, with an overlap of points filling the s1' pocket.
the "proximal" ligand-binding site that limited to the s1' pocket is called mmp-13p, while the "distal" region that extends to s1'* is called mmp-13d .
all subsequent analyses were conducted independently.
after independently generating the final representative pocket shapes, the full pocket shapes may be produced by combining them based on the status of the 3d points shared between mmp-13d and mmp-13p.
almost twice as many residues were involved in the pocket of mmp-13d than mmp-13p, resulting in huge differences in the sterically allowed conformers .
interestingly the pocket volumes were similar in size.
however, there were  <dig>  times more conditional contact points in mmp-13d than in mmp-13p .
this implied that there was a difference in geometric topologies between these two partitions.
overall, we used three test cases of different complexities: mmp- <dig> , mmp-13d , and mmp-13p .
the contact status of each point was checked against each conformer and coded into a bit string.
since we used a finite number of 3d points with a fixed non-negligible spacing  and the contact check also employed a tolerance , it was likely that some conformers generated identical bit strings.
this is one of the interesting features of our approach; for a given 'resolution' defined by the lattice spacing and cpd, we can set a threshold below which minute differences in the pocket shapes can be ignored.
this has the effect of greatly reducing the 'computational complexity' without degrading the 'resolution'.
for mmp- <dig>  we obtained  <dig>  unique strings of  <dig> bits from a host of  <dig>  conformers, reaching at a 41-fold reduction in complexity.
mmp-13p had a rather small number of conformers to start with  and yielded only  <dig> unique strings of  <dig> bits .
for mmp-13d there were  <dig>  non-redundant strings after pruning identical ones.
although more than a 17-fold reduction was achieved, the number of strings was still too high.
an additional 10-fold reduction was obtained by merging the strings that differed from each other by less than  <dig> bits; thus, a total of  <dig>  strings were retained .
even with this much of reduction, the two-way hierarchical clustering took more than  <dig> hours for mmp-13d, while the smaller task with mmp- <dig> took only  <dig> min .
clustering analysis of multiple binding sites
we have shown that the 'computational complexity' of dealing with many conformers generated by combinatorial rotamer assignment was greatly reduced by representing the conformers as bit strings.
since these bit strings mimic the shape of the binding pocket volume, clustering them would be useful to assess the diversity of their shapes.
if a small number of distinctive clusters can be observed, then the entire conformational space accessible by the ligand-binding pocket residues can be encompassed by these clusters and the associated 'computational complexity' can be even further dramatically reduced.
using the non-redundant set of bit strings , a pairwise dissimilarity was calculated as  <dig> - sft ).
note that the sizes of the bit strings were  <dig>   <dig>  and  <dig> bits for mmp- <dig>  mmp-13d, and mmp-13p, respectively.
based on the resulting shape dissimilarity matrix, multidimensional scaling was conducted .
inspection of the principal component plot showed a pattern of distinctive clustering in all three cases, and led us to select  <dig>   <dig>  and  <dig> clusters for mmp- <dig>  mmp-13d, and mmp-13p, respectively.
after ordering the bit strings according to cluster membership obtained from the mds analysis, the bit positions were then hierarchically clustered based on their dissimilarity over the conformers.
the resulting heat maps are shown in figure  <dig> , additional file 1: supplementary figures  <dig>  and  <dig> .
indeed the conformers belonging to different clusters showed quite distinct bit patterns and interestingly some sets of bit positions that dominated the clustering process were recognized.
for example, the bit status of the blocks labeled "240" in figure  <dig> combinatorially split the conformers into four super-clusters  of mmp- <dig>  since the information regarding the contact relationship between 3d points and the residues per conformer has been stored, we are able to determine which residues correspond to the bit blocks and consequently are the most influential .
if the clustering process were to reflect the real dissimilarity in the pocket shape of the conformers, its result should satisfy the following criteria:  the atomic rmsd within clusters should be less than that between clusters;  the ligand-binding conformers observed in the known crystal structures should be found among the non-redundant set of conformers;  the conformers similar in their conformation should be found in the same cluster and the ones with distinctive conformations should be in different clusters;  the fitness or shape complementarity between a ligand and a conformer should be congruent with the clustering pattern.
these points are addressed below.
structural dissimilarity of shape clustering
clustering of the conformers in the previous studies has been based on the dissimilarity in atomic coordinates  <cit> .
these results are not necessarily identical to those of clustering by pocket shape dissimilarity.
on the other hand, if the latter yields irrelevant outcomes compared to those from the former, it would be hard to accept these results.
we calculated the rmsd between the flexible atoms of the binding site side-chains.
the results are presented as boxplots for mmp- <dig>  mmp-13d, and mmp-13p .
in all three cases, the atomic rmsd's within a cluster were consistently less than those between clusters.
this indicates that the clustering by pocket shape is structurally sound, despite the conceptual difference from the conventional rmsd-based clustering.
coverage of the conformational space
we have performed an exhaustive search of the conformational space and retained all the sterically allowed conformers in the subsequent bit string representation step.
consequently all the conformers observed in the ligand-bound or apo crystal structures should be mapped into the catalog of the predicted conformers, as long as the known structures did not involve substantial backbone movements.
furthermore, it is likely that some part of the predicted conformational space may not be covered by the known conformers.
we, then, asked the following questions: how many of the clusters corresponded to the observed conformers  and were there any clusters distinct from the known conformers .
in order to map each known conformer to one of the predicted ones, the closest predicted rotamer was assigned for each binding site residue  and their combination was examined among the pool of the predicted ones.
the results are summarized in table  <dig>  for mmp- <dig>  all the seven known conformers were mapped into two so-called "known" clusters , while the other ten clusters have not been observed in the crystal structures.
among the seven known structures, four were in ligand-bound forms .
in the heat map showing the contact status of the ccrs with the 3d points , the more bit positions that were set, the less the pocket volume.
compared to the "known" clusters, the "unknown" clusters showed diminished pocket volumes.
their pocket shapes were examined visually .
it appears that the "unknown" clusters exhibit a somewhat collapsed ligand-binding pocket that is also distinct from the apo form.
on the other hand, the known conformers belonged to the clusters that were the widest open as far as ccrs were concerned.
the collapsed pocket without the concomitant adjustment of the backbone atoms may result in energetically unfavorable loose packing of the side chain atoms.
we may heuristically conclude that a cluster having severely diminished pocket volume is unrealistic.
the pocket shapes of the four known ligand-bound crystal structures are shown in figure  <dig>  the most distinctive difference between the two "known" clusters  was in the region that protruded downward.
only in 966c  was the pocket deep  enough to accommodate rs <dig>  in the other three structures , the pocket residues occupied this region .
1mmp-13d
2mmp-13p
we have identified eight clusters for mmp-13d from the mds plot.
pc <dig> separated the four "known"  and the other four "unknown" clusters .
similar to mmp- <dig>  the "known" clusters displayed bigger pockets than the "unknown" ones.
within the "known" cluster group, the clusters  <dig> and  <dig> were separated from the clusters  <dig> and  <dig> by pc <dig> .
among the eight clusters identified from the mds plot for mmp-13p, the cluster  <dig> had the largest volume and included all the seven known conformers .
it should be noted that the "known" conformers shown in table  <dig> included both ligand-bound  and ligand-free  forms.
in fact all the halo forms except one belonged to the same cluster as the apo forms in mmp- <dig>  on the other hand, the apo form belonged to a cluster distinct from those of halo forms in mmp-13d.
as long as the difference between apo and halo forms is in side chain conformation with fixed backbone, we can use one form as the template and can recover the others among the clusters.
shape clustering and ligand incompatibility
having established that the known pocket conformers of similar shapes fall into the same cluster, we next determined whether these clusters can distinguish different ligands or not.
the ligand binding pocket of a conformer may easily accommodate some ligands, but not others.
if we measure such shape incompatibility between a conformer and a ligand, its profile over a series of ligands should show a uniform pattern for all the member conformers in a given cluster.
we define the shape incompatibility between a ligand and a pocket as the volume of the ligand sticking out of the volume encompassed by the pocket.
we applied the following algorithm to estimate it.
we calculate the distance from every ligand atom to the pocket grid points we have generated based on the template structure.
the grid points that satisfy equation  are marked as belonging to the ligand, constituting the volume occupied by the ligand.
since they are mapped on the same lattice, their shapes can be easily compared using bit strings.
let the bit strings describing the ligand volume and the pocket l and p, respectively.
the incompatibility is then calculated as l \ p, the relative complement of p with respect to l.
as shown in the heat map , all members of a cluster had very similar profile of shape incompatibility with the known ligands of mmp- <dig>  the "unknown" clusters 1~ <dig> displayed closed pockets that could not accommodate any of the known ligands.
although the conformers in the clusters 10~ <dig> have not been observed in the known crystal structures , it appeared that their shapes were compatible with that of rs <dig>  since the relatively small rs <dig> binds deep inside the pocket, there was little discrimination against the "unknown" clusters.
the "known" clusters  <dig> and  <dig> were compatible with their respective known ligands.
the "unknown" cluster  <dig> showed an incompatible profile similar to those of the clusters  <dig> and  <dig> as the former had a pocket shape similar to those of latter .
similar heat maps were plotted for mmp-13d and mmp-13p, separately .
the two groups of the "known" clusters of mmp-13d separated by pc <dig> showed different preferences for the known ligands.
our analysis of the bit patterns showed the variation in pc <dig> was modulated by the rotameric status of leu  <dig> .
apparently, the wide-open pocket in the clusters  <dig> and  <dig> can accommodate all the known ligands, while the narrow-necked pocket in the clusters  <dig> and  <dig> preferred o <dig> and rs <dig> .
in mmp-13p, cluster  <dig> showed very similar patterns of shape incompatibility over the six ligands .
feasibility of the representative conformers
we have shown that the conformers of the ligand-binding residues were clustered based on their pocket shapes and the clustering pattern reflected the shape incompatibility between a conformer and a ligand.
for follow-up applications such as virtual screening or structural analyses, one would need a representative conformer for each cluster.
since the shape incompatibility profile for the known ligands was uniform over a cluster, any member of the cluster could be used to represent the entire cluster.
we chose the medoid string as the representative of each cluster  of methods).
since the medoid is one of the members, the pocket shape and conformer corresponding to the medoid string can be retrieved from the stored mapping.
see additional file 1: supplementary table  <dig> for the shape incompatibility between the medoid pockets and the known ligands.
in mmp- <dig>  all the known ligands including rs <dig> showed minimal bumping with the medoid of the cluster  <dig>  to which its ostensible binding site conformer mapped.
the medoid of cluster  <dig> was also compatible with the three known ligands excluding rs <dig>  as expected.
the compatibility patterns between the cluster medoids and the corresponding known ligands of mmp- <dig> were consistent with the cluster mapping results.
identification of key pocket residues
the two-way clustering heat map of the bit patterns depicting the contacts between 3d points and the pocket residues  implied that some sets of clustered bits were more influential than others in clustering the conformers.
if those influential bits were in contact with a few residues only, the latter may be considered the key pocket residues.
in order to identify such residues, we ran through the residue list and colored the conformers in the mds plot by the residue rotamer status.
we visually inspected each colored plot to see whether the coloring pattern was segregated along the major principal component  axes.
as shown in figure  <dig> for mmp- <dig>  the variances along pc <dig> and pc <dig> can be explained by the rotameric status of the tyr  <dig> and arg  <dig> residues, respectively.
similarly, the key residues of mmp-13d were identified as phe  <dig>  leu  <dig>  and lys  <dig>  while those of mmp-13p were tyr  <dig>  glu  <dig>  and ile  <dig> .
it should be noted that the ability to discern the key binding site residue is an advantage of the rotaimage algorithm, which maps the binding pocket by 3d points.
other approaches that are based only on energy calculations of the binding site residues would pinpoint which residue contribute the most to the overall energetics of the conformer, but would not be able to define which residue most affect the shape of the binding pocket.
calculations of the accessible surface area  <cit>  may provide similar information, but it is not necessarily true that more exposed residues influence the binding pocket shape more.
CONCLUSIONS
the rotaimage algorithm thoroughly surveys the sterically allowed conformational space and reduces the conformational complexity by partitioning the conformers into a reasonable number of groups, as previously proposed  <cit> .
these approaches are different from the traditional ones, which attempt to search for the global minimum-energy conformation  through energy minimization of the conformers.
instead we propose a method to extract a list of representative conformers from the exhaustive set of pocket conformers.
since each one is nearby a distinct local minimum, gmec can be sought later by exploring the representative conformers in parallel flexible ligand docking exercises.
on the other hand, rotaimage is novel and distinct from dynasite in that the former compares and clusters the shapes of the pocket as opposed to the latter that handles the binding site conformers .
considering that a ligand should fit in the pocket volume, focusing on the shape of the pocket may provide a strong filter for ligand screening.
the rotaimage algorithm creates a 3d shape using a bit string, which is widely used in the field of image recognition in computer science, and is an efficient way to allow easy manipulation of the conformers.
judiciary application of the standard clustering technologies to the bit patterns can partition the conformers into groups that are structurally sensible.
bit representation offers the ability to examine the conformation context of the rotamers in that the most influential residues are determined from analysis of the bit pattern.
rotaimage may find wide acceptance and use in the area of ligand binding pocket modelling.
authors' contributions
es carried out the computational analysis to test the rotaimage algorithm, helped with the analysis of the results and helped to draft the paper.
sk helped with the design of the study, analysed the results, and drafted the paper.
ws helped with the design of the study and helped to draft the paper.
all authors read and approved the final manuscript.
supplementary material
additional file 1
supplementary figures and table.
this file contains  <dig> additional figures illustrating the results for the mds scatterplots, heat maps, and rotameric status.
furthermore a supplementary table is shown for shape incompatibility in mmp <dig>  mmp-13d, and mmp-13p.
click here for file
additional file 2
supplementary note.
this file contains additional description of comparative features of our rotaimage and dynasite or kalblad et al.
<cit> .
click here for file
acknowledgements
this work was supported by grants from the center for biological modulators of the 21st century frontier r&d program  and the national research foundation of korea  grant , funded by the korea government .

 computer modelling and simulations plays an important role in the drug discovery process. all protein molecules are inherently dynamic and may have multiple conformers with similar energies in both the bound and unbound states. the model of preexisting conformations, together with the "induced-fit" where the ligand binding event causes a change in protein conformation, can explain the process of protein-ligand binding. nevertheless the experimental static structures obtained by the x-ray and nmr techniques, let alone the modelled structures, are the bases for various structure-based drug design strategies such as de novo design and docking. in these efforts, the consideration of the protein flexibility is important. even the conformational change of a single amino acid residue can change the size, shape, and electrostatic property of the binding pocket. comparisons of the x-ray structures of the pairs of the holo and apo forms indicate that the degree of structural change of the protein varies considerably. some protein undergoes rather large conformational change of the backbone. in the majority of the cases studied, however, the conformational changes occur only at the side chain level. here we present a new method, rotaimage, for modelling the plausible conformers for the ligand binding site given a fixed backbone structure. there are numerous methods to predict the side-chain conformations as a component of protein structure prediction and protein redesign. this is known as the classical side-chain prediction problem. most of these methods utilize the rotamer library that restricts side-chain torsion angles to a set of preferred or commonly-observed low-energy conformations of a particular side chain. due to its combinatorial nature, it is considered as np-hard and the number of conformers grows steeply as more residues are considered. for example, 105~ bump-free conformers were generated for a set of residues, while the number went up to over conformers for residues. application of docking to all these conformers, albeit plausible, is not practical. from now on, we call this computational burden due to high number of conformers to handle as'computational complexity'. various algorithmic heuristics have been applied in order to reduce the'computational complexity' such as monte carlo simulations, steepest-descent minimization with random restarts, and self consistent mean-field approaches. the tool scwrl combines the dead-end elimination algorithm, which restricts the conformational space, with an exhaustive but fast search of the remaining conformational space. 1the residues within Å from the ligand ensemble 2the residues within Å from the 3d points that are within Å from flrs 3the residues showing'conditional' contacts with the 3d points 4bit strings differ by less than bits were merged 5the ratio defined as / 6cpu time elapsed using an intel xeon e cpu operating at ghz with gb of main memory on a linux box. an alternative approach, called dynasite, has been developed with the aim of reducing the'computational complexity' by clustering the conformers based on structural similarities and performing docking against a representative conformer of each cluster. it used principal component analysis to cluster the conformers based on rmsd between the flexible side chain atoms and successfully generated one of the known conformers starting from a different conformer as a template. however, some practical limitations were noticed with this approach. in order to keep the number of conformers for clustering under a practical limit, the rotamer combination was restricted to the pocket residues with movements observed experimentally; the maximum number of pocket residues was for the proteins studied. each conformer of the pocket residues generates a unique shape of complementary pocket volume. thus clustering based on the pocket shape dissimilarity would be equivalent to that based on structural rmsd between conformers. our method presented here, rotaimage, clusters the pocket conformers based on the dissimilarity of their complementary pocket volumes. the shape similarity between two different volume objects can be defined as a relative volume overlap between them. since they are already in common coordinate system, the relative volume overlap can be numerically integrated over a set of three-dimensional grid points that encompass the ensemble of the pocket volumes. the grid spacing controls the granularity of volume assimilation. at its given level, the pocket volumes that differ only in fine detail can be treated as identical. computationally, each 3d volume object is distinguished by the status of every one of the 3d grid points whether one is inside or outside the volume. the status of a point is encoded into a bit position of a string, whose value instances a particular pocket surface shape. this is widely used in the field of 3d image recognition in computer science. representation of a volume object by a bit string enables efficient operation of tasks such as identification of those objects that are treated as having identical shapes at the given granularity and calculation of similarity index between two objects. for example, the former can be achieved by storing the bit strings into a hash table. while preserving the connection between a conformer and a bit string, only unique strings are identified and used in the subsequent analyses. compared to the original number of conformers, one would expect reduction in the number of unique strings. the reduction in'computational complexity' was substantial with our test cases, allowing to enumerate sterically allowed conformers with more pocket residues than those used by dynasite and to yield a manageable number of unique bit strings for clustering. calculation of the dissimilarity between two strings, defined as the tanimoto coefficient between them, involves bitwise and and or operations and should be more efficient than that of rmsd between two conformers. application of standard clustering algorithms using the dissimilarity matrix would segregate the pockets by the similarity in shape. selection of a representative pocket shape from each cluster would reduce the'computational complexity' to a degree amenable to the downstream ligand docking in a practical way. for example, each of our test cases yielded a handful of clusters. here we present details of rotaimage and demonstrate its utility by modelling the ligand binding site of human matrix metalloproteinase- and -, which have been actively studied due to their pharmacological and biochemical importance. methods algorithm the main objective of our algorithm, rotaimage, is to manage the ligand binding pocket shape using a bit string and to apply this technique to reduce the'computational complexity' in handling the binding site conformers generated through the exhaustive search of rotameric combination of side chains on fixed backbone. there are three preparatory steps prior to the main algorithm: recognition of binding site residues; mapping the binding pocket by 3d points; generation of multiple binding site conformers by rotamer assignment and concurrent checking for steric clashes. the core steps include checking the contact between the 3d points and each conformer and binary representation of the contact configuration, and pruning the conformers that produce identical bit strings. the resulting set of bit strings are then analyzed using standard clustering algorithms. the algorithm is outlined in figure and described below in detail. recognition of binding site residues and mapping the binding pocket by 3-d points identification of ligand binding pockets and analysis of their shapes have been an active area of research, as reviewed by weisel et al.. there are many algorithms available for this, such as pass, pocket, ligsite, surfnet, castp, and pocketpicker. our main objectives are to explore the conformational varieties of the ligand binding site via rotameric combination, and to map the corresponding variations of the pocket shape. for this, we need a maximally expanded pocket where the side chains of the pocket residues are substituted by ala. thus the following simple and straightforward approach would suffice for our purpose. for a given protein, the crystal structures of reasonably high resolution are collected. if multiple structures are available, one of them is chosen as a template and all the others are superposed to it. since our algorithm assumes fixed backbone conformation, any outliers in terms of backbone overlaps are excluded from consideration. although our algorithm should work with a template structure of either ligand-bound or ligand-free form, we describe first the procedure for a halo form as the template. the superposition of protein backbones creates a ligand ensemble if multiple structures of ligand complexes are available. in order to identify the residues that are subject of conformational search, we conduct multiple steps of selection and pruning. firstly, all protein residues that are within Å of the ligand ensemble are identified and refer to as the'first layer residues'. these residues except for gly are then substituted with ala. this creates an afore-mentioned artificial volume enlarged compared to the original ligand-binding pocket. it would be the volume maximally accessible by the exploration of side-chain conformations with fixed backbone atoms. nevertheless, it is referred to as the ligand-binding pocket. the second step is the generation of the 3-dimensional points that map this ligand-binding pocket. as mentioned above there are several algorithms available for this and we use pocket, which generates a lattice-like 3d array and allows rather simple manipulation of the lattice spacing. the lattice spacing is set to Å. the 3d lattice points fill in the pocket by approaching the binding site residues as close as their van der waals radius. the points that are more than Å away from the binding site residues or ligand ensemble are trimmed. once side chains are put back into the flr, they are likely in contact with the outer layer of the 3d points. the last step is the recognition of the residues whose rotameric combination would be explored. if we limit the scope to those residues that might have direct contacts with the 3d points and do not allow simultaneous flexible movement of residues deeper inside the protein core, most rotameric variations except a few would face resistance from the wall of those secondary residues. hence, it would make more sense to consider the residues underneath the pocket surface than the residues within a certain distance from the ligand ensemble like the flrs. for convenience, we define the'second layer residues' as those residues within Å from the 3d points that are in contact with flrs. some flrs are bound to be included in slrs, but not all of them. selection of flrs depends on the ligands included in the ensemble since the ligands are filtered by the distance from the flrs. on the other hand, selection of the slrs is not directly influenced by the choice of the ligand ensemble. rather the shape of the pocket dictates the distribution of the 3d points, which, in turn, governs the slrs. if no halo form can serve as the template structure, one would select flrs manually based on prior knowledge from literature or skip it to the 3d point generation. for the latter case, the potential pocket residues are not substituted by ala and thus the pocket is not maximally expanded. once 3d points are generated, slrs can be identified by the same procedure. however the number of slrs would be somewhat less than that of the former. rotamer combination and steric clash tests we take into account the side chain flexibility by placing the so-called backbone-independent rotamers back on each of the slrs defined in the previous step and performing an exhaustive search of binding site conformers. in general, the computational load for enumerating combinations of rotamers and subsequent filtering of the steric clashes in the resulting conformers grows exponentially with increasing number of rotamers. in order to circumvent this problem, the rotamer library is reduced by checking the bumping between the main chain and the side chain of each rotamer using equation. two atoms a and a are considered to clash if where ctd stands for clash tolerance distance. based on the reduced library of the surviving rotamers only, the interactions between the residues are mapped as a graph, which is then searched by a backtracking and branch-and-bound algorithm that concurrently checks the bumping between the side chain atoms of each pair of residues. this part of our algorithm follows the published graph theoretic cluster algorithm in scwrl, except for the step of dead-end elimination and the scoring functions themselves. binary image representation in protein binding site the 3-dimensional points representing the enlarged binding pocket as obtained in the first step are screened for overlap with the atoms of each conformer that has been generated by rotamer combination and that has survived the subsequent bumping checks. the contact between a binding site point'p' and a slr atom'a' is evaluated using where cpd stands for contact padding distance, which is set to Å. summarizing the results over all the conformers, the points always in contact with some slrs regardless of conformers are eliminated, while the points always free of contacts are set aside and included later in the complete construction of the binding site. only those points in'conditional' contacts depending on the conformers are retained to discriminate the conformers. for some residues in the slrs, none of the rotamers may contact the'conditional' points at all; these slrs are eliminated. the rest of the slrs, which have'conditional' contacts with the 3d points, have potential for modulating the pocket shape and are defined as'conditional contact residues'. as shown in figure each conformer is represented by a configuration of which points are in contacts or not. as it is a combination of binary states, the result is conveniently encoded by a bit string where each bit designates whether the corresponding point is in contact or not. such representation of a 3-dimensional object by a bit string has been widely used in the field of image recognition in computer science. pruning multiple conformers having identical bit strings the mapping relationship between the bit strings and the conformers is stored in a hash table. by looking up those strings that are observed more than once, we can identify the strings that are mapped to multiple conformers. these conformers have the identical status of contacts with the 3d points, i.e., their pocket shapes are indistinguishable at the specified ctd in equation. there are several situations when this can happen. as described in the previous section, some slrs are not included in the ccr list. their rotamers would not generate new bit strings. even for ccrs, some of their rotamers may not contact the 3d points, resulting in some redundant strings. it is likely to occur at the periphery of the pocket. besides, the coarser 3d points may cause the less sensitive differentiation of conformers. in such cases identical bit strings may also result from different conformers. since we keep track of which conformers are assigned to which bit strings, we do not lose any detail and reduce the computation complexity by dealing with non-redundant bit strings in the subsequent process. clustering analysis of multiple binding sites and selection of representative conformers the shape of the binding site is approximated using a set of 3d points, which are recorded as simple bit strings of length equal to the number of points. each bit position corresponds to a sphere centered at a defined 3d point. a shape-fingerprint tanimoto coefficient between two such bit strings, given by measures the proportion of bits shared between the two strings, where na and nb represent the number of bits set in the strings a and b, respectively, while na b is the number of bit position set commonly in a and b. this is equivalent to a finite numerical integration of the relative volume overlap between two 3d volume objects. a relative volume overlap between two 3d objects can be considered as one of the similarity indices, whose approximation can be given by a tanimoto coefficient. with such a similarity index, clustering analysis such as multidimensional scaling can be performed. the optimum member of clusters is determined through a visual inspection of the mds plot in 3d using ggobi. mds was conducted using the r statistical system. a two-way hierarchical clustering of both bit strings and bits can be useful in analyzing the dependency between conformers and 3d points. it was done with the linux implementation of cluster using an m × n bit pattern matrix, where m and n are the number of unique bit strings and the bit size, respectively. the time complexity of complete linkage hierarchical clustering is known as o. it should be noted that hierarchical clustering involving a few tens of thousands of bit strings can take extremely long. one would need a representative conformer for each cluster for follow-up applications such as virtual screening or structural analyses. since we use bit strings, a numerical averaging would not make sense. we choose the medoid string as the representative of each cluster. the medoid is defined as the member of the cluster whose average dissimilarity to all the other members is minimal. the pocket shapes and conformers corresponding to the medoid strings can be retrieved from the stored mapping information of methods).  target proteins we have tested our algorithm, rotaimage, by modelling the ligand-binding pockets of mmp- and mmp- there are several reasons why we have tested our algorithm using these two mmps: they are important targets for drug design and many inhibitors have been developed; multiple ligand-bound complex crystal structures have been determined for each of them at reasonably high resolution; most importantly, their crystal structures showed multiple conformer configurations in the ligand binding pocket. in addition, their conformational differences are large enough to prohibit rigid-body docking simulations of a known ligand from one configuration to the crystal structures from another configuration. it would be interesting to see whether we can recover all of the conformers seen in the crystal structures from its clustered pools of conformers, or more precisely, whether those ligands could be fit into the representative binding pocket shapes that would result from the clustering of a number of shapes. it would be more important to know how many clusters we have to consider in order to cover all the experimentally observed ligands. beyond the commonalities, the ligand binding sites of mmp- and mmp- have quite distinct shapes and properties. the side chain of arg of mmp- limits the s1' pocket to a size suitable for an aromatic ring, while the corresponding residue in mmp- is replaced by leu, creating a long channel called s1'*. consequently, many more residues are involved in mmp- than mmp- by testing our algorithm with cases of different complexities, we may gain more insight on variations of its performance. generation of multiple binding site images we downloaded eight and seven crystal structures determined at a resolution of Å or higher for mmp- and mmp- respectively, from protein data bank. each set of proteins were superposed into a common reference structure and 1xuc for mmp- and mmp- respectively). one of the crystal structures of mmp- displayed a backbone structure distinct from the rest and was excluded in the subsequent analysis. otherwise the average rmsd among backbone cα atoms were Å and Å for mmp- and mmp- respectively. the residues within Å from the ligand ensemble were identified and substituted with ala. the enlarged pockets were then filled with 3d lattice points of Å spacing. since flrs are determined based on the distances from the known ligands, they may reflect the current repertoire of ligands. in order to remove such a bias and use residues that are within a constant depth underneath the pocket, we looked for residues within Å from the 3d points. these residues are referred to as slrs. see figure for the definition of flrs and slrs. some flrs deep inside the protein core were not used as slrs, while new ones were added at the periphery where the known ligands did not reach. the next step involved an exhaustive search of conformers through rotamer combination and a concurrent bumping check. in order to tolerate some uncertainty in the atomic positions, we also adopted the clash tolerance schemes defined in equation, where ctd was set at Å. for each conformer, the 3d points that were in contact with the side chain atoms were screened using equation by setting cpd and a to Å and van der waals radius, respectively. after scanning all the conformers, the points were classified into two groups. when this scheme was applied to mmp- residues out of the flrs were retained as ccrs. in contrast, a smaller reduction occurred with mmp- i.e., from flrs to the number of 3d points indicated that the ligand-binding pocket of mmp- was ~50% larger than the binding pocket of mmp-. after excluding those points free of contact with any of the conformers, there were twice as many 3d points with conditional contacts in mmp- than in mmp-. the number of ccrs or 3d points showing conditional contacts is correlated to the size of the pocket surface area, not directly to the volume. these numbers were in huge excess of the volume increase in mmp- compared to mmp- indicating a larger ratio of contact surface-to-volume in the former than in the latter. this may be explained by the fact that mmp- had a long and extended binding pocket unlike mmp- which had a globular ligand-binding site. the'computational complexity' due to a large number of conformers is governed by the number of ccrs, while the number of 3d points showing conditional contacts with ccrs dictates the variety of pocket shapes. in this regards, mmp- and - were useful examples in assessing the complexity associated with these variables. while the exhaustive rotameric combination generated sterically allowed conformers for mmp- the same procedure produced over billion conformers for mmp- since the number of conformers for mmp- was too large to be handled on a reasonable time scale, we decided to split the number of 3d points of mmp- into half, with an overlap of points filling the s1' pocket. the "proximal" ligand-binding site that limited to the s1' pocket is called mmp-13p, while the "distal" region that extends to s1'* is called mmp-13d. all subsequent analyses were conducted independently. after independently generating the final representative pocket shapes, the full pocket shapes may be produced by combining them based on the status of the 3d points shared between mmp-13d and mmp-13p. almost twice as many residues were involved in the pocket of mmp-13d than mmp-13p, resulting in huge differences in the sterically allowed conformers. interestingly the pocket volumes were similar in size. however, there were times more conditional contact points in mmp-13d than in mmp-13p. this implied that there was a difference in geometric topologies between these two partitions. overall, we used three test cases of different complexities: mmp-, mmp-13d, and mmp-13p. the contact status of each point was checked against each conformer and coded into a bit string. since we used a finite number of 3d points with a fixed non-negligible spacing and the contact check also employed a tolerance, it was likely that some conformers generated identical bit strings. this is one of the interesting features of our approach; for a given'resolution' defined by the lattice spacing and cpd, we can set a threshold below which minute differences in the pocket shapes can be ignored. this has the effect of greatly reducing the'computational complexity' without degrading the'resolution'. for mmp- we obtained unique strings of bits from a host of conformers, reaching at a 41-fold reduction in complexity. mmp-13p had a rather small number of conformers to start with and yielded only unique strings of bits. for mmp-13d there were non-redundant strings after pruning identical ones. although more than a 17-fold reduction was achieved, the number of strings was still too high. an additional 10-fold reduction was obtained by merging the strings that differed from each other by less than bits; thus, a total of strings were retained. even with this much of reduction, the two-way hierarchical clustering took more than hours for mmp-13d, while the smaller task with mmp- took only min. clustering analysis of multiple binding sites we have shown that the'computational complexity' of dealing with many conformers generated by combinatorial rotamer assignment was greatly reduced by representing the conformers as bit strings. since these bit strings mimic the shape of the binding pocket volume, clustering them would be useful to assess the diversity of their shapes. if a small number of distinctive clusters can be observed, then the entire conformational space accessible by the ligand-binding pocket residues can be encompassed by these clusters and the associated'computational complexity' can be even further dramatically reduced. using the non-redundant set of bit strings, a pairwise dissimilarity was calculated as - sft ). note that the sizes of the bit strings were and bits for mmp- mmp-13d, and mmp-13p, respectively. based on the resulting shape dissimilarity matrix, multidimensional scaling was conducted. inspection of the principal component plot showed a pattern of distinctive clustering in all three cases, and led us to select and clusters for mmp- mmp-13d, and mmp-13p, respectively. after ordering the bit strings according to cluster membership obtained from the mds analysis, the bit positions were then hierarchically clustered based on their dissimilarity over the conformers. the resulting heat maps are shown in figure, additional file 1: supplementary figures and. indeed the conformers belonging to different clusters showed quite distinct bit patterns and interestingly some sets of bit positions that dominated the clustering process were recognized. for example, the bit status of the blocks labeled "240" in figure combinatorially split the conformers into four super-clusters of mmp- since the information regarding the contact relationship between 3d points and the residues per conformer has been stored, we are able to determine which residues correspond to the bit blocks and consequently are the most influential. if the clustering process were to reflect the real dissimilarity in the pocket shape of the conformers, its result should satisfy the following criteria: the atomic rmsd within clusters should be less than that between clusters; the ligand-binding conformers observed in the known crystal structures should be found among the non-redundant set of conformers; the conformers similar in their conformation should be found in the same cluster and the ones with distinctive conformations should be in different clusters; the fitness or shape complementarity between a ligand and a conformer should be congruent with the clustering pattern. these points are addressed below. structural dissimilarity of shape clustering clustering of the conformers in the previous studies has been based on the dissimilarity in atomic coordinates. these results are not necessarily identical to those of clustering by pocket shape dissimilarity. on the other hand, if the latter yields irrelevant outcomes compared to those from the former, it would be hard to accept these results. we calculated the rmsd between the flexible atoms of the binding site side-chains. the results are presented as boxplots for mmp- mmp-13d, and mmp-13p. in all three cases, the atomic rmsd's within a cluster were consistently less than those between clusters. this indicates that the clustering by pocket shape is structurally sound, despite the conceptual difference from the conventional rmsd-based clustering. coverage of the conformational space we have performed an exhaustive search of the conformational space and retained all the sterically allowed conformers in the subsequent bit string representation step. consequently all the conformers observed in the ligand-bound or apo crystal structures should be mapped into the catalog of the predicted conformers, as long as the known structures did not involve substantial backbone movements. furthermore, it is likely that some part of the predicted conformational space may not be covered by the known conformers. we, then, asked the following questions: how many of the clusters corresponded to the observed conformers and were there any clusters distinct from the known conformers. in order to map each known conformer to one of the predicted ones, the closest predicted rotamer was assigned for each binding site residue and their combination was examined among the pool of the predicted ones. the results are summarized in table for mmp- all the seven known conformers were mapped into two so-called "known" clusters, while the other ten clusters have not been observed in the crystal structures. among the seven known structures, four were in ligand-bound forms. in the heat map showing the contact status of the ccrs with the 3d points, the more bit positions that were set, the less the pocket volume. compared to the "known" clusters, the "unknown" clusters showed diminished pocket volumes. their pocket shapes were examined visually. it appears that the "unknown" clusters exhibit a somewhat collapsed ligand-binding pocket that is also distinct from the apo form. on the other hand, the known conformers belonged to the clusters that were the widest open as far as ccrs were concerned. the collapsed pocket without the concomitant adjustment of the backbone atoms may result in energetically unfavorable loose packing of the side chain atoms. we may heuristically conclude that a cluster having severely diminished pocket volume is unrealistic. the pocket shapes of the four known ligand-bound crystal structures are shown in figure the most distinctive difference between the two "known" clusters was in the region that protruded downward. only in 966c was the pocket deep enough to accommodate rs in the other three structures, the pocket residues occupied this region. 1mmp-13d 2mmp-13p we have identified eight clusters for mmp-13d from the mds plot. pc separated the four "known" and the other four "unknown" clusters. similar to mmp- the "known" clusters displayed bigger pockets than the "unknown" ones. within the "known" cluster group, the clusters and were separated from the clusters and by pc. among the eight clusters identified from the mds plot for mmp-13p, the cluster had the largest volume and included all the seven known conformers. it should be noted that the "known" conformers shown in table included both ligand-bound and ligand-free forms. in fact all the halo forms except one belonged to the same cluster as the apo forms in mmp- on the other hand, the apo form belonged to a cluster distinct from those of halo forms in mmp-13d. as long as the difference between apo and halo forms is in side chain conformation with fixed backbone, we can use one form as the template and can recover the others among the clusters. shape clustering and ligand incompatibility having established that the known pocket conformers of similar shapes fall into the same cluster, we next determined whether these clusters can distinguish different ligands or not. the ligand binding pocket of a conformer may easily accommodate some ligands, but not others. if we measure such shape incompatibility between a conformer and a ligand, its profile over a series of ligands should show a uniform pattern for all the member conformers in a given cluster. we define the shape incompatibility between a ligand and a pocket as the volume of the ligand sticking out of the volume encompassed by the pocket. we applied the following algorithm to estimate it. we calculate the distance from every ligand atom to the pocket grid points we have generated based on the template structure. the grid points that satisfy equation are marked as belonging to the ligand, constituting the volume occupied by the ligand. since they are mapped on the same lattice, their shapes can be easily compared using bit strings. let the bit strings describing the ligand volume and the pocket l and p, respectively. the incompatibility is then calculated as l \ p, the relative complement of p with respect to l. as shown in the heat map, all members of a cluster had very similar profile of shape incompatibility with the known ligands of mmp- the "unknown" clusters 1~ displayed closed pockets that could not accommodate any of the known ligands. although the conformers in the clusters 10~ have not been observed in the known crystal structures, it appeared that their shapes were compatible with that of rs since the relatively small rs binds deep inside the pocket, there was little discrimination against the "unknown" clusters. the "known" clusters and were compatible with their respective known ligands. the "unknown" cluster showed an incompatible profile similar to those of the clusters and as the former had a pocket shape similar to those of latter. similar heat maps were plotted for mmp-13d and mmp-13p, separately. the two groups of the "known" clusters of mmp-13d separated by pc showed different preferences for the known ligands. our analysis of the bit patterns showed the variation in pc was modulated by the rotameric status of leu. apparently, the wide-open pocket in the clusters and can accommodate all the known ligands, while the narrow-necked pocket in the clusters and preferred o and rs. in mmp-13p, cluster showed very similar patterns of shape incompatibility over the six ligands. feasibility of the representative conformers we have shown that the conformers of the ligand-binding residues were clustered based on their pocket shapes and the clustering pattern reflected the shape incompatibility between a conformer and a ligand. for follow-up applications such as virtual screening or structural analyses, one would need a representative conformer for each cluster. since the shape incompatibility profile for the known ligands was uniform over a cluster, any member of the cluster could be used to represent the entire cluster. we chose the medoid string as the representative of each cluster of methods). since the medoid is one of the members, the pocket shape and conformer corresponding to the medoid string can be retrieved from the stored mapping. see additional file 1: supplementary table for the shape incompatibility between the medoid pockets and the known ligands. in mmp- all the known ligands including rs showed minimal bumping with the medoid of the cluster to which its ostensible binding site conformer mapped. the medoid of cluster was also compatible with the three known ligands excluding rs as expected. the compatibility patterns between the cluster medoids and the corresponding known ligands of mmp- were consistent with the cluster mapping results. identification of key pocket residues the two-way clustering heat map of the bit patterns depicting the contacts between 3d points and the pocket residues implied that some sets of clustered bits were more influential than others in clustering the conformers. if those influential bits were in contact with a few residues only, the latter may be considered the key pocket residues. in order to identify such residues, we ran through the residue list and colored the conformers in the mds plot by the residue rotamer status. we visually inspected each colored plot to see whether the coloring pattern was segregated along the major principal component axes. as shown in figure for mmp- the variances along pc and pc can be explained by the rotameric status of the tyr and arg residues, respectively. similarly, the key residues of mmp-13d were identified as phe leu and lys while those of mmp-13p were tyr glu and ile. it should be noted that the ability to discern the key binding site residue is an advantage of the rotaimage algorithm, which maps the binding pocket by 3d points. other approaches that are based only on energy calculations of the binding site residues would pinpoint which residue contribute the most to the overall energetics of the conformer, but would not be able to define which residue most affect the shape of the binding pocket. calculations of the accessible surface area may provide similar information, but it is not necessarily true that more exposed residues influence the binding pocket shape more.  the rotaimage algorithm thoroughly surveys the sterically allowed conformational space and reduces the conformational complexity by partitioning the conformers into a reasonable number of groups, as previously proposed. these approaches are different from the traditional ones, which attempt to search for the global minimum-energy conformation through energy minimization of the conformers. instead we propose a method to extract a list of representative conformers from the exhaustive set of pocket conformers. since each one is nearby a distinct local minimum, gmec can be sought later by exploring the representative conformers in parallel flexible ligand docking exercises. on the other hand, rotaimage is novel and distinct from dynasite in that the former compares and clusters the shapes of the pocket as opposed to the latter that handles the binding site conformers. considering that a ligand should fit in the pocket volume, focusing on the shape of the pocket may provide a strong filter for ligand screening. the rotaimage algorithm creates a 3d shape using a bit string, which is widely used in the field of image recognition in computer science, and is an efficient way to allow easy manipulation of the conformers. judiciary application of the standard clustering technologies to the bit patterns can partition the conformers into groups that are structurally sensible. bit representation offers the ability to examine the conformation context of the rotamers in that the most influential residues are determined from analysis of the bit pattern. rotaimage may find wide acceptance and use in the area of ligand binding pocket modelling. authors' contributions es carried out the computational analysis to test the rotaimage algorithm, helped with the analysis of the results and helped to draft the paper. sk helped with the design of the study, analysed the results, and drafted the paper. ws helped with the design of the study and helped to draft the paper. all authors read and approved the final manuscript. supplementary material additional file 1 supplementary figures and table. this file contains additional figures illustrating the results for the mds scatterplots, heat maps, and rotameric status. furthermore a supplementary table is shown for shape incompatibility in mmp mmp-13d, and mmp-13p. click here for file additional file 2 supplementary note. this file contains additional description of comparative features of our rotaimage and dynasite or kalblad et al.. click here for file acknowledgements this work was supported by grants from the center for biological modulators of the 21st century frontier r&d program and the national research foundation of korea grant, funded by the korea government.
at this level of clustering, the conformational space spanned by the known crystal structures was well covered. rotaimage is a novel algorithm that was efficient in exploring the conformational space of the ligand binding site. here we propose a new method, rotaimage, for modelling the plausible conformers for the ligand binding site given a fixed backbone structure. identification of residues that influenced the shape of the pocket is an interesting feature unique to the rotaimage algorithm. prior to the clustering, the list of conformers generated by exhaustive search can be reduced by pruning the conformers that have near identical pocket shapes, which is done using simple bit operations. we tested our approach by modelling the active-site inhibitor binding pockets of matrix metalloproteinase- and - for both cases, analyzing the conformers based on their pocket shapes substantially reduced the'computational complexity'. even if the side chains are restricted to rotamers, a set of commonly-observed low-energy conformations, the exhaustive combinatorial search of ligand binding site conformers is known as np-hard. the subsequent clustering revealed that the pocket shapes of both proteins could be grouped into approximately distinct clusters. rotaimage includes a procedure of selecting ligand binding site residues, exhaustively searching rotameric conformers, clustering them by dissimilarities in pocket shape, and suggesting a representative conformer per cluster. its ability to identify'key' pocket residues also provides further insight into conformational flexibility with specific implications for protein-ligand interactions. heatmap analysis identified a few bit blocks that combinatorially dictated the clustering pattern. using this analytical approach, we demonstrated that each of the bit blocks was associated with a specific pocket residue.
 modelling the ligand binding site of a protein is an important component of understanding protein-ligand interactions and is being actively studied. even if the side chains are restricted to rotamers, a set of commonly-observed low-energy conformations, the exhaustive combinatorial search of ligand binding site conformers is known as np-hard. here we propose a new method, rotaimage, for modelling the plausible conformers for the ligand binding site given a fixed backbone structure.  rotaimage includes a procedure of selecting ligand binding site residues, exhaustively searching rotameric conformers, clustering them by dissimilarities in pocket shape, and suggesting a representative conformer per cluster. prior to the clustering, the list of conformers generated by exhaustive search can be reduced by pruning the conformers that have near identical pocket shapes, which is done using simple bit operations. we tested our approach by modelling the active-site inhibitor binding pockets of matrix metalloproteinase- and - for both cases, analyzing the conformers based on their pocket shapes substantially reduced the'computational complexity'. the subsequent clustering revealed that the pocket shapes of both proteins could be grouped into approximately distinct clusters. at this level of clustering, the conformational space spanned by the known crystal structures was well covered. heatmap analysis identified a few bit blocks that combinatorially dictated the clustering pattern. using this analytical approach, we demonstrated that each of the bit blocks was associated with a specific pocket residue. identification of residues that influenced the shape of the pocket is an interesting feature unique to the rotaimage algorithm.  rotaimage is a novel algorithm that was efficient in exploring the conformational space of the ligand binding site. its ability to identify'key' pocket residues also provides further insight into conformational flexibility with specific implications for protein-ligand interactions. 