BACKGROUND
molecular shape comparison  has been playing an increasingly important role in computer aided molecular design, rational drug design, molecular docking and function prediction.
the goal of msc is to find the spatial properties common to two or more molecules.
especially in computer aided drug design, a critical problem of virtual screening, aimed at identifying the drug-like molecules likely to have beneficial biological properties, is comparing molecular shapes.
an alternative virtual screening technique consists of searching a molecular database for compounds that most closely resemble a given query molecule  <cit> .
the underlying assumption is that the molecules similar to the active query molecule are likely to share similar properties.
this similarity can be in terms of molecular geometrical shapes or descriptors.
a number of previous studies have concerned shape comparison of molecules  <cit> .
most existing msc methods are only effective for comparing 3d rigid objects, but they can not handle the deformed shapes of flexible objects well.
nevertheless, many molecules of interest are flexible and undergo significant shape deformation as part of their function.
when flexible molecules in different conformations are compared to each other as rigid bodies, strong shape similarities might be missed.
to address the issue we developed a new method for comparing molecular shapes, which is insensitive to molecular shape deformation compared to previously rigid methods.
methods of molecular shape comparison
the molecular shape has been widely acknowledged as a key factor for biological activity and it is directly related to the design of selective ligands for protein and dna binding.
to exploit the shape similarity of molecules in the shape-based molecular design, a useful tool is msc that compares the shapes of two or more molecules and identifies common spatial features  <cit> .
such comparison can lead to some alternative models in the process of drug design.
an additional advantage of msc is that no specification of chemical structure is made and therefore the molecules with shape similarity, but with different chemical structure, can be found  <cit> .
however, the efficient msc is currently a challenge  <cit>  due to the high complexity of 3d molecular shapes.
ballester et al.
<cit>  divided the msc methods into two categories: superposition and descriptor  methods.
the former relies on finding an optimal superposition of molecules, and the later  is independent of molecular orientation and position.
superposition msc
the superposition methods are a popular family of msc methods based on the optimal superposition/alignment of two or more molecules.
the early superposition method was developed by meyer and richards  <cit>  to measure the similarity of molecular shape.
masek et al.
<cit>  compared molecular shapes by optimizing the intersection of molecular surfaces.
rocs  is an available superposition method  <cit>  and it performs shape-based overlays of two molecules by a local optimization process.
the algorithm is based on the earlier implementations of molecular shape comparison described by masek et al.
<cit> , which quickly finds and quantifies the maximum overlap of the volume of two molecules  <cit> .
rush et al.
<cit>  described a shape-based 3d scaffold hopping method, which is an application of rocs to a bacterial protein-protein interaction.
recently, natarajan et al.
<cit>  compared rigid components of molecules by segmenting their surfaces based on morse theory.
the superposition msc methods require a priori superposition/alignment of molecular shapes into a coordinate system, which is difficult to achieve robustly.
the reader may consult refs.
<cit>  for a review of many available methods of superposition msc.
descriptor/signature msc
another category of shape comparison methods uses descriptor/signature to represent the shape of molecule.
the kind of methods is non-superposition that computes the similarity score by comparing the corresponding descriptors between two molecular shapes.
a 3d shape descriptor, or called signature, is a compact representation for some essence of the shape.
the shape descriptor is usually used as an index in a database of shapes and enables fast queries and retrieval.
the descriptor methods are simpler than the traditional superposition methods that require shape superposition/alignment, feature correspondence, or model fitting  <cit> .
an early molecular shape description is developed by bemis et al.
<cit>  by considering each molecule as a collection of its 3-atom submolecules.
nilakantan et al.
<cit>  also introduced a method for the rapid quantitative shape match between two molecules or a molecule and a template, using atom triplets as descriptors.
several recent works related to molecular shape comparison using shape descriptors have been developed including shape distribution descriptor, spherical harmonic signature, 3d zernike descriptor, etc  <cit> .
these descriptors are rigid-body-transformation invariant, and they are effective for matching rigid objects.
nevertheless, none of these methods is deformation invariant and they can not support flexible molecular shape comparison.
deformation invariant representation of nonrigid or flexible shape like articulated objects is a challenging problem in the field of shape analysis.
several recent works focus on this problem  <cit> .
one class of approaches focuses on topology or graph comparison for determining the deformation  <cit> , but the graph extraction process is often very sensitive to local shape changes.
furthermore, graph comparison cost increases proportionally with the graph size, resulting in relatively slow comparison and retrieval times.
in  <cit> , elad and kimmel presented a bending invariant representation for a pitch of surface based on multidimensional scaling, but the geodesic distance is sensitive to shape changing  <cit>  and therefore it is not appropriate for protein comparison.
jain et al.
<cit>  presented a spectral approach to shape-based retrieval of deformation 3d models, but this method is not appropriate for protein models with many holes.
recently, gal et al.
<cit>  proposed the local diameter shape signature by computing the distance from surface to medial axis.
other methods take into account local features on the boundary surface of the shape in the neighborhood of points  <cit> .
usually, these local techniques are based on matching local descriptors.
however, many times they do not perform well on global shape matching because of their local nature they do not provide a good signature of the overall shape  <cit> .
these existing descriptors can not perform well for flexible molecules due to their complex shape deformation.
distance signatures
in 3d shape retrieval, the simplest and most widely used shape signatures is the distance signature between sampling point pairs on shape surfaces.
our work also belongs to this category.
we introduce three representative distance signatures: euclidean distance , geodesic distance  and inner distance .
the ed signature  <cit>  usually is represented by a histogram of distance values and it is formed by three steps: 1) sampling uniformly random points from the shape surface, 2) computing the ed between the sampled point pairs, and 3) building the histogram of corresponding distance values.
after finishing computation of the signature histogram, the similarity scores of shapes are defined as the distance between their histograms.
a histogram is actually a one-dimensional vector.
however, the ed histogram between pair of points on a shape surface is sensitive to shape deformation.
an alternative distance signature is to replace ed by geodesic distance   <cit> .
the gd between any pair of points on a surface is defined as the length of the shortest path on the surface between them.
since the gd is invariant to surface bending, the stretched surface forms a bending invariant signature of the original surface.
although the gd is insensitive to surface stretch, it is sensitive to shape deformation, as shown by  <cit> .
the gd does not work well for our purpose.
the work most related to ours is  <cit> , in which a novel 2d inner distance measurement is presented for building 2d shape signatures.
the id signature is robust to articulated deformation and it is more effective at capturing shape structures than both ed and gd.
in 2d case, the id is defined as the length of the shortest path between landmark points within the 2d silhouette.
however, no algorithm for id computation of 3d shapes is given due to the complexity of 3d shapes so far.
RESULTS
overview of approach
here we introduce a new technique, called inner distance shape signature , for describing the 3d shapes of flexible molecules.
our work can be regarded as an extension of inner distance from 2d to 3d for computing the deformation invariant shape signatures of flexible molecules.
the procedure of computing the idss of molecular is given as follows.
first, we obtain a set of points sampled uniformly from a molecular surface using lloyd's algorithm of k-means clustering.
then a new algorithm is presented for checking the inside visibility between sample point pairs; based on their inside visibility, we define a graph and compute the inner distances using a shortest path algorithm in the graph.
finally, we build a signature of inner distances for measuring the global geometric properties of the molecule.
the core procedure can be divided into three steps: sampling, calculating inner distance and building signatures .
these techniques have been implemented in a software package called the idss program.
figure  <dig> illustrates the comparison between idss and rigid methods.
the source molecule comes from drosophila sp.
, where 2spca has one long helix and one short helix.
the four artificial molecules  are formed by fixing the long helix of 2spca and rotating the short helix about  <dig>   <dig>   <dig> and  <dig> degrees round x-axis, respectively.
the input four artificial molecules have the same main chain orientation but with different surface shapes, where the idss is computed with surface shapes of molecules.
note that our inner distance signatures remain largely consistent for the four deformed molecular shapes of the same protein, while the previous rigid descriptor  <cit>  is strongly sensitive to shape deformation.
definition of inner distance
first, we extend the definition of inner distance  in 2d objects  <cit>  to 3d shapes.
let o be a 3d shape as a connected and closed subset of ℝ <dig>  we denote the boundary surface of o by ∂o.
given two points x, y ∈ ∂o, the id between x and y, denoted as d, is defined as the length of the shortest path connecting x and y within o.
articulated deformation and hinge-bending movement
ling and jacobs  <cit>  have proven that the id is insensitive to the shape articulated deformation by decomposing the shape into some rigid parts connected by junctions.
an articulated shape o is described with the following conditions: 1) o can be decomposed into several parts that are connected by junctions ; 2) the junctions between parts are very small compared to the parts they connect; 3) the articulation of o as a transformation is rigid when limited to any part but can be non-rigid at the junctions.
the relative id change is very small for the articulated objects, so id is insensitive to articulations.
molecules are flexible and can be regarded as an articulated shape.
many molecules contain flexible structures such as loops and hinge domains.
some recent studies demonstrated that the activity of many molecules induces conformational transitions by hinge-bending, which involves the movement of relatively rigid parts of a molecule about flexible joints  <cit> .
in hinge-bending, parts of the molecule rotate with respect to each other as relatively rigid bodies, on a common hinge.
the hinge-bending of molecules can be treated as a special shape articulated deformation.
in figure  <dig>  each molecule contains two domains  that are rigid regions and also contains one hinge  that is a flexible region.
data set of molecules
a molecule is represented by a set of overlapping spherical atoms.
the exposed surface of these spheres represents a molecular surface that defines the boundary of a single molecule' volume.
in this paper, we consider the input data as a volumetric/voxelized representation of molecular shape.
there have been numerous works on this representation, such as for binding sites determination  <cit> , molecular shape comparison  <cit> , the cryo-electron microscopy  data  <cit> , and 3d shape searching  <cit> .
we consider a volumetric model as a uniform 3d lattice consisting of object points o and background points .
we represent the  <dig> ×  <dig> ×  <dig> neighborhood of each lattice point x by n, which is a set of  <dig> points and each point  that share a common grid edge, face, and cell with x. the boundary surface of o is defined as
in the preprocessing stage, the molecular shape is built.
the molecular shape in the mrc file format is directly used for our program as the default input.
the mrc volumetric data can be generated by using a way described by  <cit> .
first, the msroll  <cit>  program in molecular surface package is used to compute the connolly surface  of the molecule using default parameters.
next, the triangle mesh is placed in a 3d cubic grid of n <dig> , compactly fitting a molecule to the grid.
each lattice point is assigned either  <dig> or 0;  <dig> for object points o and  <dig> for background points .
alternatively, the users may use some commercial softwares for getting the mrc files of molecular models, such as chimera  <cit>  and eman  <cit> .
we have implemented the technique presented in the previous section and tested it on a set of molecules.
the algorithm described above is implemented in c++.
to show the ability of the idss approximating the molecular shapes, we first select a couple of complicated examples for visualizing their idss.
to demonstrate the utility of deformation invariant signatures, we develop a shape search system of flexible molecules and test this system for a benchmark containing abundant conformational changes of molecules.
examples of simulated data
the ability of inner distance to represent deformation invariant shape signatures of flexible molecules is first tested on some unrelated proteins .
previously, these structures are used in the assessment of structure recognition in cryo-em  <cit> .
four protein models with the simulated  <dig> Å resolution density maps are shown in figure  <dig>  the computed inner distances approximate well the global shapes of four proteins.
note how the inner distances capture the holes for 1b7t and 1irk.
this apparent differences of the global surface shapes are also reflected by distinctive inner distance signatures shown in figure  <dig>
articulated deformation insensitivity
as described above in this paper, the most attractive one of advantages of idss is deformation insensitivity for 3d articulated shapes in contrast with the traditional rigid descriptors.
in addition, the idss also captures some global geometric properties which are scale, translation and rotation invariant.
however, in practice the idsss of deformation shapes of one same protein are not exactly identical.
this error is caused by two reasons.
one is that the molecular surface shape o is discretized into the volumetric format, where m sample points on the boundary surface ∂o of o are only used for approximating the global inner distances.
smaller m does not sufficiently approximate ∂o, while larger m requires more computation time and space.
in our implementation, we typically choose m =  <dig> for both a small approximation error and little computation time.
the second reason is that the size of the loop and hinge regions of deformations affects the idss computation.
intuitively, for smaller the loop and hinge change compared to the overall size of the molecular shape, the inner distance changes are smaller.
figure  <dig> shows an example of articulated deformation insensitivity of the idss.
here, the two molecules used are two conformations of the same protein , and the relative change of the loop  on the left top are large.
this results in some errors in the idss, but the two idsss are still very close with the similar histogram.
in contrast, the traditional rigid descriptors fail in deformation detection .
a search system of flexible molecules
to assess the efficacy of the proposed signature, we have incorporated the new method into a system of molecular shape comparison.
we have chosen to test our method on a benchmark set of molecules found in the database of macromolecular movements   <cit> .
molmovdb presents a diverse set of molecules that display large conformational changes in proteins and other macromolecules, which can be found at: .
the benchmark data set is classified  <dig> groups with the total  <dig>  pdb files, where each is named the corresponding group id.
the number of conformations in different group may be different.
this benchmark has been used in predicting protein structures and hinge predictor  <cit> .
the developed search system of flexible molecules provides a tool with which users can retrieve molecules from the benchmark based on their shape attributes.
in our current program, the user selects a query molecule from the database and the program computes the similarity scores for all molecules in the database using the methods described in this paper.
the program then shows the query molecule and the similar molecules in the database.
in the molmovdb benchmark we have pre-calculated all inner distance signatures of queries on the database and display molecules using images in the dialog box of retrieved results.
the inner distance signatures allow rapid search on the system because a molecular shape is compactly represented by a 1d vector.
if a query molecule is already transformed into the inner distance signature, a search to the current benchmark data set takes less than half a second.
comparison with existing methods
the id shape signature is first compared with two other distance signatures: euclidean distance  and geodesic distance  in terms of the performance on retrieving similar molecular structures.
we use standard evaluation procedures from information retrieval, namely precision-recall curves, for evaluating the various shape distance signatures  <cit> .
precision-recall  curves describe the relationship between precision and recall for an information retrieval method.
precision is the ratio of the relevant models retrieved to the retrieval size.
recall is the fraction of the relevant models retrieved for a given retrieval size.
a perfect retrieval retrieves all relevant models consistently at each recall level, producing a horizontal line at precision =  <dig> .
however, in practice, precision decreases with increasing recall.
the closer a pr curve tends to the horizontal line at precision =  <dig> , the better the information retrieval method.
figure  <dig> shows the pr curves of three distance signatures for the molmovdb database.
the results show that the id method performs better than ed and gd at average level for flexible molecules.
as we discussed previously, although the gd is insensitive to surface stretch, it is sensitive to 3d shape deformation  <cit> .
gd is sensitive to 3d shape deformation.
from our experiments we also found that some molecules with one domain are often judged as similarity to some ones with two or three domains when using gd signatures.
in the molmovdb database, gd can not give good searching results as well as ed.
furthermore, we compared our signatures with three known rigid descriptors: the spherical harmonic descriptor, the solid angle histogram and the eigen value model  <cit> .
the all three methods have been developed and used for searching of rigid shapes in computer graphics, engineering domain, and molecular shape comparison.
one recent work  <cit>  has compared the differences between shape descriptors with the cleaned scop protein classification database.
in their paper, the 3d zernike descriptor retrieved the better results than the above rigid methods based on the consistency of the rigid shapes.
however, protein are flexible molecules that undergo significant structural changes and shape deformations as part of their function, and the existing rigid descriptors all fail on deformation detection .
discussion
in this section, we present several potential applications for idss by replacing the conventional rigid shape descriptors in molecular shape comparison and also discuss some limitations of our approach.
searching molecular databases for drug design
in rational drug design, a unifying principle is the use of either shape similarity or complementarity to identify compounds expected to be active against a given target  <cit> .
shape similarity is the underlying foundation of ligand-based methods that seek compounds with structure similar to known actives.
shape complementarity is the basis of most receptor-based design methods, which identify compounds complementary in shape to a given receptor.
one of the future works is to apply the idss method to some large and diverse molecular databases for both ligand- and receptor-based molecular design.
there are some methods that have focused on searching diverse molecular databases based on the descriptor msc methods.
for instance, nilakantan et al.
<cit>  searched the ten molecules with the highest shape similarity score in a database consisted of  <dig>  compounds derived from the cambridge crystal file.
their technique can be used to screen large databases to eliminate those candidates which have a low shape similarity with the template.
hahn  <cit>  described a three-phase database searching strategy for rapidly finding compounds similar in shape to a given shape query.
this used database contained  <dig>  compounds and  <dig> , <dig> total conformations.
zauhar et al.
<cit>  tested their shape signature method to the tripos fragment database and the nci database  under two different metrics.
recently, ballester et al.
<cit>  presented ultrafast shape recognition to search several compound databases for similar molecular shapes.
the tested databases include the vendor database  and an independent benchmark from drugbank.
our idss may replace the existing shape descriptors used in the above molecular databases.
searching molecular databases for drug design will be the subject of a separate publication.
protein structure retrieval
with the rapidly increasing number of known protein structure data, fast structural comparisons and retrieval methods are necessary to protein structure databases.
many structural comparison methods of proteins have been proposed for computing the similarity scores, and most of them are based on protein structure alignment, such as dali  <cit>  and ce  <cit> .
structural alignment aims to compare a pair of structures, where the alignment between equivalent residues is not given prior.
therefore, an optimal sequence alignment needs to be identified, which has been shown to be np-complete  <cit> .
in addition, several methods consider the hinge regions for aligning the protein rigid subparts  <cit> .
recently, we also presented a structural comparison method for flexible proteins using least median of squares  <cit> .
the reader may consult  <cit>  for comprehensive evaluation of protein structure alignment methods.
our idss method can be used as a search for similar protein structures.
one main advantage is that the shape-based protein searching method does not produce an alignment between two proteins .
the standard benchmark data sets used to demonstrate the effectiveness of a similarity search are scop and cath at various homology thresholds.
it is expected that the presented idss method can be considered as an alternative and complementary tool for the existing methods for protein structure comparison and rigid molecular shape comparison.
discovery of high resolution structural homologues from cryo-em maps
computer reconstruction of cryo-em images approximates the overall shape and topology of 3d volumetric object of macromolecular complexes  <cit> , where it is not a trivial task to determine the structure information due to the low resolution.
the obtained cryo-em data is a 3d grid, called cryo-em map, in which every voxel is assigned a density value.
only the overall shape and possible component boundaries are visible at low resolution; individual components become apparent at intermediate resolution.
many works have been presented for fitting high resolution structures of individual subunits into a cryo-em map of a protein complex.
lasker et al.
<cit>  divided the different approaches into two categories.
one class of approaches assumes that the input is a cryo-em map of a complex and an atomic resolution structure of one of its components, and the aim is to fit the given component into its location in the cryo-em map.
in many cases, only the cryo-em map is available, whereas the atomic structures of individual components in a complex are unknown.
another class of approaches looks for closely related atomic structures of the complex's components and fits them into the map, which is a challenge.
the previous methods search for structural homologues of the complex's domains based on sequence alignment or correlation scores, and then fit them into the map.
to align atomic resolution subunits into cryo-em maps, ematch method  <cit>  first identifies helices in an input cryo-em map.
it then uses the spatial arrangements of the helices to query a data set of high resolution folds and finds structures that can be aligned into the cryo-em map.
one key step in ematch is to detect helices in cryo-em.
however, identification of secondary structure elements in low or intermediate resolution density maps still is a difficult open problem  <cit> .
in addition, baker et al.
<cit>  discussed a framework for simultaneous identification of both α helices and β sheets in intermediate resolution density maps.
in the spirit similar to searching a data set used in ematch, one possible solution is to first convert all proteins of the database into the density maps in the same resolution.
then we may search the converted database of protein surfaces for compounds that most closely resemble the input query cryo-em.
one main advantage of the strategy is to avoiding detecting α helices and β sheets for the input croy-em.
most existing rigid msc methods can work on the above searching step.
our idss method can also be directly used for searching for the most related proteins of the complex's components as an alternative method by considering the deformation of flexible proteins.
combining other characteristics into the signature
the idss algorithm presented in this paper belongs on molecular shape comparison.
the current implementations only take advantage of geometry information of molecular shapes without chemical features.
however, in many applications, such as matching in protein-protein or protein-ligand  docking/design, chemistry is also very useful  <cit> .
in fact, our current signature can be directly combined with some chemistry information.
specifically, other characteristics of a molecular surface, such as electrostatic potentials, might be naturally incorporated into the inner distance signature by considering a high dimensional sample point coordinate.
for example, a molecular boundary surface ∂o in eq.
<dig> can also be described as a set of 4d points ∂o = {pi = }, where xi, yi, and zi are three geometry coordinates of the sample point pi and ci denotes its value of charge.
the inner distance can be computed as the length of the shortest path between four-dimensional points.
in the future, we intend to consider adding other chemical features into our signature.
limitation
a limitation of our approach is that the calculation of the id is sensitive to the topology changes in shape.
figure  <dig> shows two examples of protein conformation pairs but with different topology structures.
in figure  <dig>  two molecules are two conformations of groel , where the intermediate domain of 1kp <dig> swings down towards the equatorial domain and the central channel so that the surfaces of two domains intersect in 1aon.
in figure  <dig>  two molecules are two conformations of diptheria toxin , where 1ddt has several domains but 1mdt shrinks together.
the inner distance signatures will be very different between conformations in the term of the shape topology changes.
however, the special cases with shape topology changes are not very usual in protein deformations.
our method can work well for most molecular shape deformation without topology changes.
in many ways the definition of a signature which is both effective and highly robust to the object representation remains a challenge  <cit> .
another limitation of molecular shape comparison is that the shapes with similar descriptors perhaps have no evolutionary relationship.
figure  <dig> shows a pair of proteins 1bara and 1rro, which is provided in ref.
<cit> .
the two proteins have very similar geometry shape descriptors, but they have very different main chain orientation.
most molecular comparison methods based on their shapes are not available for distinguishing the special cases.
in particular, idss can be combined with classical structure alignment algorithms for protein shape retrieval.
for example, idss first can be used to retrieve an initial small subset for a query protein, and then some conventional structure comparison methods, such as ce and dali, can compute main-chain similarity in the small subset.
CONCLUSIONS
a new method for molecular shape comparison , called idss , has been presented.
idss does not require previous alignment of the molecules being compared.
we show that the idss is deformation insensitive and is good for approximating the complicated shapes of flexible molecules.
in contrast, most existing msc methods are effective for only comparing rigid objects and they can not handle shape deformation of flexible objects well.
we have evaluated and demonstrated the effectiveness of idss within a molecular search engine application for a benchmark on molmovdb.
the new signature achieves good performance and retrieval results for different classes of flexible molecules with the efficiency of comparing histogram signatures.
the presented idss method can also be applied to the molecular surface representation, such as the connolly surface, by verifying whether a segment is inside the molecular surface.
moreover, we also showed several potential applications for idss by replacing the conventional rigid shape descriptors in molecular shape comparison, including searching molecular databases for drug design and protein structure retrieval.

 molecular shape comparison has been playing an increasingly important role in computer aided molecular design, rational drug design, molecular docking and function prediction. the goal of msc is to find the spatial properties common to two or more molecules. especially in computer aided drug design, a critical problem of virtual screening, aimed at identifying the drug-like molecules likely to have beneficial biological properties, is comparing molecular shapes. an alternative virtual screening technique consists of searching a molecular database for compounds that most closely resemble a given query molecule. the underlying assumption is that the molecules similar to the active query molecule are likely to share similar properties. this similarity can be in terms of molecular geometrical shapes or descriptors. a number of previous studies have concerned shape comparison of molecules. most existing msc methods are only effective for comparing 3d rigid objects, but they can not handle the deformed shapes of flexible objects well. nevertheless, many molecules of interest are flexible and undergo significant shape deformation as part of their function. when flexible molecules in different conformations are compared to each other as rigid bodies, strong shape similarities might be missed. to address the issue we developed a new method for comparing molecular shapes, which is insensitive to molecular shape deformation compared to previously rigid methods. methods of molecular shape comparison the molecular shape has been widely acknowledged as a key factor for biological activity and it is directly related to the design of selective ligands for protein and dna binding. to exploit the shape similarity of molecules in the shape-based molecular design, a useful tool is msc that compares the shapes of two or more molecules and identifies common spatial features. such comparison can lead to some alternative models in the process of drug design. an additional advantage of msc is that no specification of chemical structure is made and therefore the molecules with shape similarity, but with different chemical structure, can be found. however, the efficient msc is currently a challenge due to the high complexity of 3d molecular shapes. ballester et al. divided the msc methods into two categories: superposition and descriptor methods. the former relies on finding an optimal superposition of molecules, and the later is independent of molecular orientation and position. superposition msc the superposition methods are a popular family of msc methods based on the optimal superposition/alignment of two or more molecules. the early superposition method was developed by meyer and richards to measure the similarity of molecular shape. masek et al. compared molecular shapes by optimizing the intersection of molecular surfaces. rocs is an available superposition method and it performs shape-based overlays of two molecules by a local optimization process. the algorithm is based on the earlier implementations of molecular shape comparison described by masek et al., which quickly finds and quantifies the maximum overlap of the volume of two molecules. rush et al. described a shape-based 3d scaffold hopping method, which is an application of rocs to a bacterial protein-protein interaction. recently, natarajan et al. compared rigid components of molecules by segmenting their surfaces based on morse theory. the superposition msc methods require a priori superposition/alignment of molecular shapes into a coordinate system, which is difficult to achieve robustly. the reader may consult refs. for a review of many available methods of superposition msc. descriptor/signature msc another category of shape comparison methods uses descriptor/signature to represent the shape of molecule. the kind of methods is non-superposition that computes the similarity score by comparing the corresponding descriptors between two molecular shapes. a 3d shape descriptor, or called signature, is a compact representation for some essence of the shape. the shape descriptor is usually used as an index in a database of shapes and enables fast queries and retrieval. the descriptor methods are simpler than the traditional superposition methods that require shape superposition/alignment, feature correspondence, or model fitting. an early molecular shape description is developed by bemis et al. by considering each molecule as a collection of its 3-atom submolecules. nilakantan et al. also introduced a method for the rapid quantitative shape match between two molecules or a molecule and a template, using atom triplets as descriptors. several recent works related to molecular shape comparison using shape descriptors have been developed including shape distribution descriptor, spherical harmonic signature, 3d zernike descriptor, etc. these descriptors are rigid-body-transformation invariant, and they are effective for matching rigid objects. nevertheless, none of these methods is deformation invariant and they can not support flexible molecular shape comparison. deformation invariant representation of nonrigid or flexible shape like articulated objects is a challenging problem in the field of shape analysis. several recent works focus on this problem. one class of approaches focuses on topology or graph comparison for determining the deformation, but the graph extraction process is often very sensitive to local shape changes. furthermore, graph comparison cost increases proportionally with the graph size, resulting in relatively slow comparison and retrieval times. in, elad and kimmel presented a bending invariant representation for a pitch of surface based on multidimensional scaling, but the geodesic distance is sensitive to shape changing and therefore it is not appropriate for protein comparison. jain et al. presented a spectral approach to shape-based retrieval of deformation 3d models, but this method is not appropriate for protein models with many holes. recently, gal et al. proposed the local diameter shape signature by computing the distance from surface to medial axis. other methods take into account local features on the boundary surface of the shape in the neighborhood of points. usually, these local techniques are based on matching local descriptors. however, many times they do not perform well on global shape matching because of their local nature they do not provide a good signature of the overall shape. these existing descriptors can not perform well for flexible molecules due to their complex shape deformation. distance signatures in 3d shape retrieval, the simplest and most widely used shape signatures is the distance signature between sampling point pairs on shape surfaces. our work also belongs to this category. we introduce three representative distance signatures: euclidean distance, geodesic distance and inner distance. the ed signature usually is represented by a histogram of distance values and it is formed by three steps: 1) sampling uniformly random points from the shape surface, 2) computing the ed between the sampled point pairs, and 3) building the histogram of corresponding distance values. after finishing computation of the signature histogram, the similarity scores of shapes are defined as the distance between their histograms. a histogram is actually a one-dimensional vector. however, the ed histogram between pair of points on a shape surface is sensitive to shape deformation. an alternative distance signature is to replace ed by geodesic distance. the gd between any pair of points on a surface is defined as the length of the shortest path on the surface between them. since the gd is invariant to surface bending, the stretched surface forms a bending invariant signature of the original surface. although the gd is insensitive to surface stretch, it is sensitive to shape deformation, as shown by. the gd does not work well for our purpose. the work most related to ours is, in which a novel 2d inner distance measurement is presented for building 2d shape signatures. the id signature is robust to articulated deformation and it is more effective at capturing shape structures than both ed and gd. in 2d case, the id is defined as the length of the shortest path between landmark points within the 2d silhouette. however, no algorithm for id computation of 3d shapes is given due to the complexity of 3d shapes so far.  overview of approach here we introduce a new technique, called inner distance shape signature, for describing the 3d shapes of flexible molecules. our work can be regarded as an extension of inner distance from 2d to 3d for computing the deformation invariant shape signatures of flexible molecules. the procedure of computing the idss of molecular is given as follows. first, we obtain a set of points sampled uniformly from a molecular surface using lloyd's algorithm of k-means clustering. then a new algorithm is presented for checking the inside visibility between sample point pairs; based on their inside visibility, we define a graph and compute the inner distances using a shortest path algorithm in the graph. finally, we build a signature of inner distances for measuring the global geometric properties of the molecule. the core procedure can be divided into three steps: sampling, calculating inner distance and building signatures. these techniques have been implemented in a software package called the idss program. figure illustrates the comparison between idss and rigid methods. the source molecule comes from drosophila sp., where 2spca has one long helix and one short helix. the four artificial molecules are formed by fixing the long helix of 2spca and rotating the short helix about and degrees round x-axis, respectively. the input four artificial molecules have the same main chain orientation but with different surface shapes, where the idss is computed with surface shapes of molecules. note that our inner distance signatures remain largely consistent for the four deformed molecular shapes of the same protein, while the previous rigid descriptor is strongly sensitive to shape deformation. definition of inner distance first, we extend the definition of inner distance in 2d objects to 3d shapes. let o be a 3d shape as a connected and closed subset of ℝ we denote the boundary surface of o by ∂o. given two points x, y ∈ ∂o, the id between x and y, denoted as d, is defined as the length of the shortest path connecting x and y within o. articulated deformation and hinge-bending movement ling and jacobs have proven that the id is insensitive to the shape articulated deformation by decomposing the shape into some rigid parts connected by junctions. an articulated shape o is described with the following conditions: 1) o can be decomposed into several parts that are connected by junctions; 2) the junctions between parts are very small compared to the parts they connect; 3) the articulation of o as a transformation is rigid when limited to any part but can be non-rigid at the junctions. the relative id change is very small for the articulated objects, so id is insensitive to articulations. molecules are flexible and can be regarded as an articulated shape. many molecules contain flexible structures such as loops and hinge domains. some recent studies demonstrated that the activity of many molecules induces conformational transitions by hinge-bending, which involves the movement of relatively rigid parts of a molecule about flexible joints. in hinge-bending, parts of the molecule rotate with respect to each other as relatively rigid bodies, on a common hinge. the hinge-bending of molecules can be treated as a special shape articulated deformation. in figure each molecule contains two domains that are rigid regions and also contains one hinge that is a flexible region. data set of molecules a molecule is represented by a set of overlapping spherical atoms. the exposed surface of these spheres represents a molecular surface that defines the boundary of a single molecule' volume. in this paper, we consider the input data as a volumetric/voxelized representation of molecular shape. there have been numerous works on this representation, such as for binding sites determination, molecular shape comparison, the cryo-electron microscopy data, and 3d shape searching. we consider a volumetric model as a uniform 3d lattice consisting of object points o and background points. we represent the × × neighborhood of each lattice point x by n, which is a set of points and each point that share a common grid edge, face, and cell with x. the boundary surface of o is defined as in the preprocessing stage, the molecular shape is built. the molecular shape in the mrc file format is directly used for our program as the default input. the mrc volumetric data can be generated by using a way described by. first, the msroll program in molecular surface package is used to compute the connolly surface of the molecule using default parameters. next, the triangle mesh is placed in a 3d cubic grid of n, compactly fitting a molecule to the grid. each lattice point is assigned either or 0; for object points o and for background points. alternatively, the users may use some commercial softwares for getting the mrc files of molecular models, such as chimera and eman. we have implemented the technique presented in the previous section and tested it on a set of molecules. the algorithm described above is implemented in c++. to show the ability of the idss approximating the molecular shapes, we first select a couple of complicated examples for visualizing their idss. to demonstrate the utility of deformation invariant signatures, we develop a shape search system of flexible molecules and test this system for a benchmark containing abundant conformational changes of molecules. examples of simulated data the ability of inner distance to represent deformation invariant shape signatures of flexible molecules is first tested on some unrelated proteins. previously, these structures are used in the assessment of structure recognition in cryo-em. four protein models with the simulated Å resolution density maps are shown in figure the computed inner distances approximate well the global shapes of four proteins. note how the inner distances capture the holes for 1b7t and 1irk. this apparent differences of the global surface shapes are also reflected by distinctive inner distance signatures shown in figure articulated deformation insensitivity as described above in this paper, the most attractive one of advantages of idss is deformation insensitivity for 3d articulated shapes in contrast with the traditional rigid descriptors. in addition, the idss also captures some global geometric properties which are scale, translation and rotation invariant. however, in practice the idsss of deformation shapes of one same protein are not exactly identical. this error is caused by two reasons. one is that the molecular surface shape o is discretized into the volumetric format, where m sample points on the boundary surface ∂o of o are only used for approximating the global inner distances. smaller m does not sufficiently approximate ∂o, while larger m requires more computation time and space. in our implementation, we typically choose m = for both a small approximation error and little computation time. the second reason is that the size of the loop and hinge regions of deformations affects the idss computation. intuitively, for smaller the loop and hinge change compared to the overall size of the molecular shape, the inner distance changes are smaller. figure shows an example of articulated deformation insensitivity of the idss. here, the two molecules used are two conformations of the same protein, and the relative change of the loop on the left top are large. this results in some errors in the idss, but the two idsss are still very close with the similar histogram. in contrast, the traditional rigid descriptors fail in deformation detection. a search system of flexible molecules to assess the efficacy of the proposed signature, we have incorporated the new method into a system of molecular shape comparison. we have chosen to test our method on a benchmark set of molecules found in the database of macromolecular movements. molmovdb presents a diverse set of molecules that display large conformational changes in proteins and other macromolecules, which can be found at:. the benchmark data set is classified groups with the total pdb files, where each is named the corresponding group id. the number of conformations in different group may be different. this benchmark has been used in predicting protein structures and hinge predictor. the developed search system of flexible molecules provides a tool with which users can retrieve molecules from the benchmark based on their shape attributes. in our current program, the user selects a query molecule from the database and the program computes the similarity scores for all molecules in the database using the methods described in this paper. the program then shows the query molecule and the similar molecules in the database. in the molmovdb benchmark we have pre-calculated all inner distance signatures of queries on the database and display molecules using images in the dialog box of retrieved results. the inner distance signatures allow rapid search on the system because a molecular shape is compactly represented by a 1d vector. if a query molecule is already transformed into the inner distance signature, a search to the current benchmark data set takes less than half a second. comparison with existing methods the id shape signature is first compared with two other distance signatures: euclidean distance and geodesic distance in terms of the performance on retrieving similar molecular structures. we use standard evaluation procedures from information retrieval, namely precision-recall curves, for evaluating the various shape distance signatures. precision-recall curves describe the relationship between precision and recall for an information retrieval method. precision is the ratio of the relevant models retrieved to the retrieval size. recall is the fraction of the relevant models retrieved for a given retrieval size. a perfect retrieval retrieves all relevant models consistently at each recall level, producing a horizontal line at precision =. however, in practice, precision decreases with increasing recall. the closer a pr curve tends to the horizontal line at precision =, the better the information retrieval method. figure shows the pr curves of three distance signatures for the molmovdb database. the results show that the id method performs better than ed and gd at average level for flexible molecules. as we discussed previously, although the gd is insensitive to surface stretch, it is sensitive to 3d shape deformation. gd is sensitive to 3d shape deformation. from our experiments we also found that some molecules with one domain are often judged as similarity to some ones with two or three domains when using gd signatures. in the molmovdb database, gd can not give good searching results as well as ed. furthermore, we compared our signatures with three known rigid descriptors: the spherical harmonic descriptor, the solid angle histogram and the eigen value model. the all three methods have been developed and used for searching of rigid shapes in computer graphics, engineering domain, and molecular shape comparison. one recent work has compared the differences between shape descriptors with the cleaned scop protein classification database. in their paper, the 3d zernike descriptor retrieved the better results than the above rigid methods based on the consistency of the rigid shapes. however, protein are flexible molecules that undergo significant structural changes and shape deformations as part of their function, and the existing rigid descriptors all fail on deformation detection. discussion in this section, we present several potential applications for idss by replacing the conventional rigid shape descriptors in molecular shape comparison and also discuss some limitations of our approach. searching molecular databases for drug design in rational drug design, a unifying principle is the use of either shape similarity or complementarity to identify compounds expected to be active against a given target. shape similarity is the underlying foundation of ligand-based methods that seek compounds with structure similar to known actives. shape complementarity is the basis of most receptor-based design methods, which identify compounds complementary in shape to a given receptor. one of the future works is to apply the idss method to some large and diverse molecular databases for both ligand- and receptor-based molecular design. there are some methods that have focused on searching diverse molecular databases based on the descriptor msc methods. for instance, nilakantan et al. searched the ten molecules with the highest shape similarity score in a database consisted of compounds derived from the cambridge crystal file. their technique can be used to screen large databases to eliminate those candidates which have a low shape similarity with the template. hahn described a three-phase database searching strategy for rapidly finding compounds similar in shape to a given shape query. this used database contained compounds and, total conformations. zauhar et al. tested their shape signature method to the tripos fragment database and the nci database under two different metrics. recently, ballester et al. presented ultrafast shape recognition to search several compound databases for similar molecular shapes. the tested databases include the vendor database and an independent benchmark from drugbank. our idss may replace the existing shape descriptors used in the above molecular databases. searching molecular databases for drug design will be the subject of a separate publication. protein structure retrieval with the rapidly increasing number of known protein structure data, fast structural comparisons and retrieval methods are necessary to protein structure databases. many structural comparison methods of proteins have been proposed for computing the similarity scores, and most of them are based on protein structure alignment, such as dali and ce. structural alignment aims to compare a pair of structures, where the alignment between equivalent residues is not given prior. therefore, an optimal sequence alignment needs to be identified, which has been shown to be np-complete. in addition, several methods consider the hinge regions for aligning the protein rigid subparts. recently, we also presented a structural comparison method for flexible proteins using least median of squares. the reader may consult for comprehensive evaluation of protein structure alignment methods. our idss method can be used as a search for similar protein structures. one main advantage is that the shape-based protein searching method does not produce an alignment between two proteins. the standard benchmark data sets used to demonstrate the effectiveness of a similarity search are scop and cath at various homology thresholds. it is expected that the presented idss method can be considered as an alternative and complementary tool for the existing methods for protein structure comparison and rigid molecular shape comparison. discovery of high resolution structural homologues from cryo-em maps computer reconstruction of cryo-em images approximates the overall shape and topology of 3d volumetric object of macromolecular complexes, where it is not a trivial task to determine the structure information due to the low resolution. the obtained cryo-em data is a 3d grid, called cryo-em map, in which every voxel is assigned a density value. only the overall shape and possible component boundaries are visible at low resolution; individual components become apparent at intermediate resolution. many works have been presented for fitting high resolution structures of individual subunits into a cryo-em map of a protein complex. lasker et al. divided the different approaches into two categories. one class of approaches assumes that the input is a cryo-em map of a complex and an atomic resolution structure of one of its components, and the aim is to fit the given component into its location in the cryo-em map. in many cases, only the cryo-em map is available, whereas the atomic structures of individual components in a complex are unknown. another class of approaches looks for closely related atomic structures of the complex's components and fits them into the map, which is a challenge. the previous methods search for structural homologues of the complex's domains based on sequence alignment or correlation scores, and then fit them into the map. to align atomic resolution subunits into cryo-em maps, ematch method first identifies helices in an input cryo-em map. it then uses the spatial arrangements of the helices to query a data set of high resolution folds and finds structures that can be aligned into the cryo-em map. one key step in ematch is to detect helices in cryo-em. however, identification of secondary structure elements in low or intermediate resolution density maps still is a difficult open problem. in addition, baker et al. discussed a framework for simultaneous identification of both α helices and β sheets in intermediate resolution density maps. in the spirit similar to searching a data set used in ematch, one possible solution is to first convert all proteins of the database into the density maps in the same resolution. then we may search the converted database of protein surfaces for compounds that most closely resemble the input query cryo-em. one main advantage of the strategy is to avoiding detecting α helices and β sheets for the input croy-em. most existing rigid msc methods can work on the above searching step. our idss method can also be directly used for searching for the most related proteins of the complex's components as an alternative method by considering the deformation of flexible proteins. combining other characteristics into the signature the idss algorithm presented in this paper belongs on molecular shape comparison. the current implementations only take advantage of geometry information of molecular shapes without chemical features. however, in many applications, such as matching in protein-protein or protein-ligand docking/design, chemistry is also very useful. in fact, our current signature can be directly combined with some chemistry information. specifically, other characteristics of a molecular surface, such as electrostatic potentials, might be naturally incorporated into the inner distance signature by considering a high dimensional sample point coordinate. for example, a molecular boundary surface ∂o in eq. can also be described as a set of 4d points ∂o = {pi = }, where xi, yi, and zi are three geometry coordinates of the sample point pi and ci denotes its value of charge. the inner distance can be computed as the length of the shortest path between four-dimensional points. in the future, we intend to consider adding other chemical features into our signature. limitation a limitation of our approach is that the calculation of the id is sensitive to the topology changes in shape. figure shows two examples of protein conformation pairs but with different topology structures. in figure two molecules are two conformations of groel, where the intermediate domain of 1kp swings down towards the equatorial domain and the central channel so that the surfaces of two domains intersect in 1aon. in figure two molecules are two conformations of diptheria toxin, where 1ddt has several domains but 1mdt shrinks together. the inner distance signatures will be very different between conformations in the term of the shape topology changes. however, the special cases with shape topology changes are not very usual in protein deformations. our method can work well for most molecular shape deformation without topology changes. in many ways the definition of a signature which is both effective and highly robust to the object representation remains a challenge. another limitation of molecular shape comparison is that the shapes with similar descriptors perhaps have no evolutionary relationship. figure shows a pair of proteins 1bara and 1rro, which is provided in ref.. the two proteins have very similar geometry shape descriptors, but they have very different main chain orientation. most molecular comparison methods based on their shapes are not available for distinguishing the special cases. in particular, idss can be combined with classical structure alignment algorithms for protein shape retrieval. for example, idss first can be used to retrieve an initial small subset for a query protein, and then some conventional structure comparison methods, such as ce and dali, can compute main-chain similarity in the small subset.  a new method for molecular shape comparison, called idss, has been presented. idss does not require previous alignment of the molecules being compared. we show that the idss is deformation insensitive and is good for approximating the complicated shapes of flexible molecules. in contrast, most existing msc methods are effective for only comparing rigid objects and they can not handle shape deformation of flexible objects well. we have evaluated and demonstrated the effectiveness of idss within a molecular search engine application for a benchmark on molmovdb. the new signature achieves good performance and retrieval results for different classes of flexible molecules with the efficiency of comparing histogram signatures. the presented idss method can also be applied to the molecular surface representation, such as the connolly surface, by verifying whether a segment is inside the molecular surface. moreover, we also showed several potential applications for idss by replacing the conventional rigid shape descriptors in molecular shape comparison, including searching molecular databases for drug design and protein structure retrieval. 
to address the issue we introduce a new shape descriptor, called inner distance shape signature, for describing the 3d shapes of flexible molecules. the inner distance is defined as the length of the shortest path between landmark points within the molecular shape, and it reflects well the molecular structure and deformation without explicit decomposition. our idss is stored as a histogram which is a probability distribution of inner distances between all sample point pairs on the molecular surface. the presented idss method can be considered as an alternative and complementary tool for the existing methods for rigid msc. we demonstrate the effectiveness of idss within a molecular search engine application for a benchmark containing abundant conformational changes of molecules. many molecules of interest are flexible and undergo significant shape deformation as part of their function, but most existing methods of molecular shape comparison treat them as rigid bodies, which may lead to incorrect measure of the shape similarity of flexible molecules. we show that idss is insensitive to shape deformation of flexible molecules and more effective at capturing molecular structures than traditional shape descriptors.
 many molecules of interest are flexible and undergo significant shape deformation as part of their function, but most existing methods of molecular shape comparison treat them as rigid bodies, which may lead to incorrect measure of the shape similarity of flexible molecules.  to address the issue we introduce a new shape descriptor, called inner distance shape signature, for describing the 3d shapes of flexible molecules. the inner distance is defined as the length of the shortest path between landmark points within the molecular shape, and it reflects well the molecular structure and deformation without explicit decomposition. our idss is stored as a histogram which is a probability distribution of inner distances between all sample point pairs on the molecular surface. we show that idss is insensitive to shape deformation of flexible molecules and more effective at capturing molecular structures than traditional shape descriptors. our approach reduces the 3d shape comparison problem of flexible molecules to the comparison of idss histograms.  the proposed algorithm is robust and does not require any prior knowledge of the flexible regions. we demonstrate the effectiveness of idss within a molecular search engine application for a benchmark containing abundant conformational changes of molecules. such comparisons in several thousands per second can be carried out. the presented idss method can be considered as an alternative and complementary tool for the existing methods for rigid msc. the binary executable program for windows platform and database are available from. 