BACKGROUND
across all biological and pharmaceutical investigations, the discovery  of molecules with desired biological activity is an important goal.
efforts to attain this goal are strongly driven by the notion of molecular similarity because in general similar molecules tend to behave similarly  <cit> .
effective determination of molecular similarity requires accounting for both structural and physicochemical characteristics of molecules  <cit> .
it is therefore closely related to the notions of molecular representation and molecular descriptors.
we begin this section with a review of techniques for molecular representation and molecular descriptors.
next, we outline and discuss different formulations of the molecular query-retrieval problem.
this is followed by a review of the prior research in this area.
the last subsection introduces the problems associated with determining molecular similarity using complex 3d surface-based descriptors
introduction to molecular representations and descriptors
in their simplest form, molecules can be represented using chemical formulae.
however, different structures may yield the same formula even though they possess dissimilar physical or biochemical properties .
therefore, commonly employed representation frameworks tend to emphasize a more explicit characterization of the molecular structure and include :  one-dimensional string-based descriptors, such as smiles obtained by ordered traversal of the molecular graph,  vector-space representation of  attributes of a molecule called structure keys that encode presence/absence of predefined sub-structural motifs in the molecule in a binary string,  two-dimensional and three-dimensional graphscharacterizing molecular connectivity and inter-atomic distances, and  three-dimensional surface based representations, such as the connolly surface.
the connolly surface is obtained by rolling a probe-atom over the molecule and is defined as the set of points where the surface of the probe atom touches the van der walls surfaces of the atoms in the molecule.
it may be noted that the complexity of representations is directly correlated with their fidelity in describing biochemical characteristics of molecules.
for example, simple characteristics of molecules such as their atomic weight or connectivity can be derived from smile strings.
however, more complex biochemical properties like molecule-molecule interactions or permeation through membranes are more accurately modelled using surface-based representations  <cit> .
molecular descriptors are computationally determinable characteristics of a molecule that describe specific molecular properties.
examples include physical-chemical descriptors such as the number of rotatable bonds, polar surface area, electronegativity, descriptors of molecular connectivity such as the wiener number  <cit> , the randic index  <cit> , structure keys and molecular fingerprints, eigenvalue-based descriptors  <cit> , molecular moment-based descriptors such as comma  <cit> , and surface and field-based descriptors  <cit> .
other descriptors include donor-acceptor atoms  <cit>  and those based on the molecular wave/density functions  <cit> .
modern approaches to correlating molecular structure with biological activity emphasize the use of molecular fields ; given any molecular property p that can be calculated at an arbitrary point around a molecule, a field can be created by integrating p with respect to volume.
field-based descriptors typically are superposition-based, in that their value at any particular point, takes into account the influence of multiple atoms of the molecule at that point.
it is also straightforward to define field-based descriptors at the molecular surface, thereby incorporating both physicochemical and physically-relevant structural attributes in a single framework.
formulations for molecular query-retrieval and analysis of prior research
the problem of molecular query-retrieval can be approached from two primary and interrelated perspectives:
• query formulation
two main forms of formulating the query can be distinguished:  sub-structure-based query, where the query-structure is constrained to be a proper subset of each of the retrieved structures.
whole-molecule query, where molecules are retrieved in terms of their overall similarity, as defined using appropriate similarity functions, to the query molecule.
it is important to note that sub-structure searching requires the user to have a clear picture of the structures which are to be retrieved prior to issuing the query  <cit> .
typically such detailed knowledge is available only when the mechanism of action of the molecule is established in terms of its activity as determined by specific structural fragments.
in contrast, "whole molecule" similarity is suitable for exploring structural space  <cit> , generating hypotheses, or querying chemical databases when detailed structure-activity information, at the level necessary for sub-structure querying is unavailable.
• molecular representation
molecular representations have varying capabilities in terms of modelling biochemical characteristics of molecules.
as noted earlier, surface-based representations/descriptors are more faithful to the actual physics of molecules than molecular graphs-based approaches  <cit> .
at the same time, graph-based representations, owing to their graphical similarity to chemical notations, tend to be highly intuitive and are also computationally easier to characterize.
early attempts at determining molecular similarity, like  <cit> , used variations on the sum of inter-atomic distances.
later approaches have looked at schemes for atom re-labelling to minimize a difference-distance matrix or decomposing the molecular distance and connectivity graphs into sub-graphs which are numerically characterized and compared  <cit> .
other efforts have tried to characterize similarity of molecular graphs, using edit distances, frequent sub-graphs  <cit> , or maximal common sub-graphs  <cit> .
these techniques either focus on building structure-property models  or do not efficaciously scale up with repository size.
with our research goals in mind, at the state-of-the-art, two classes of techniques merit discussion:
<dig>  matching techniques using fixed-size representation vectors: have been amongst the most efficient and are employed almost in all small molecule repositories of significant size.
in this approach a molecule is represented using a fixed size vector.
each element of the vector encodes for the presence  of a predefined attribute, for example, specific structural motifs  <cit>  or the unique labelled paths obtained during a traversal  <cit> .
the vectors are then compared using well established dissimilarity measures such as the hamming, euclidean, and tanimoto measures.
<dig>  matching techniques using 3d molecular graphs: depend on super-positioning the 3d graphs of the molecules being compared.
significant research in this context has been done of aligning structures of large  molecules leading to techniques such as dali  <cit> , ssm  <cit> , ssap  <cit> , structal  <cit> , ce  <cit> , lock  <cit> , and lsqman  <cit> .
other efforts include the application of geometric hashing and its variations  <cit> .
in  <cit> , molecular similarity is defined using surface and field characteristics: first, the field-effects around a molecule are estimated.
then, the orientation of the query/model molecule , is varied to minimize an rms error between the field values.
the use of fixed-size representation vectors has lead to practical solutions for querying large molecular repositories.
however, such approaches have several severe drawbacks:  they are limited to 2d information and incapable of being used for complex bio-chemically relevant representations/descriptors.
they are incapable of representing bioisosteres .
such representations are predefined rather than being data-driven.
therefore, they are incapable of capturing specificities of molecules which were not preconceived.
on the other hand current approaches to 3d matching simply don't scale with respect to repository size and time constraints typical to modern query-retrieval formulations.
moreover, such approaches, even when they seek to compare surface-based descriptors, do so indirectly.
that is, the 3d graphs are superimposed and only then are the respective surfaces compared.
such an approach can miss molecules which have similar surface/field-based properties, but whose 3d structures do not necessarily superimpose well.
problem characteristics and challenges
the problem of determining the similarity of molecules when they are represented using complex 3d surface-based descriptors presents some unique challenges which include:
<dig>  definition of a standard coordinate system for surface-based molecular representations: to compare molecules using their surface-based descriptions, it is necessary to have a way of representing the shape of their surfaces.
the complexity lies in defining an intrinsic  coordinate system over the curved molecular surface that maps a point on the curved surface to a point on a standard coordinate system.
additionally, such a mapping should be one-to-one between points on the molecular surface and the standard coordinate system.
<dig>  multi-modal nature of molecular properties: molecular properties like geometry and donor/acceptor fields have entirely different characteristics.
for example, while the geometric representation of a molecule is unique, donor/acceptor fields are superposition-based.
representation frameworks need to account for such issues.
<dig>  query efficiency: it is typical to conduct molecular similarity queries over large sets ranging from thousands to millions of molecules.
the latter order of magnitude is especially common in pharmaceutical settings.
it is therefore imperative for similarity determination approaches to be computationally efficient.
RESULTS
three different types of experiments were conducted to study the efficacy of the proposed method:  investigation of the method's accuracy in query-retrieval settings,  evaluation of its performance , and  validation through applications in structure-activity modelling problems.
each experiment incorporated two stages: the first stage involved a direct application of the method on a data set with subsequent analysis of the results.
in the second stage, a comparative study was performed by applying a state-of-the-art research or commercial technique on the same data set.
subsequently the results were analysed to evaluate the proposed approach.
accuracy in query-retrieval settings
the method was tested in a query-retrieval setting on a subset of  <dig> molecules randomly selected from the mddr collection  <cit> .
the mddr collection consists of molecules that are either marketed drugs or have reached advanced stages in a drug discovery process.
each of the  <dig> molecules was successively used as a query against the rest of the molecules.
the query and model molecules were each represented by  <dig> conformers, i.e.
<dig> distinct molecular conformers were used per similarity computation.
since the proposed method does not require super-positioning of the underlying structures, to distinguish its performance from approaches that do so, a variation of the experiment was performed where the query was represented by  <dig> novel  conformers.
it may be noted, that for some molecules,  <dig> novel energetically stable conformers could not be obtained.
in such cases, as many novel conformers as could be derived for each specific structure were used.
in the second stage of this experiment, for purposes of comparison, the query-retrieval experiments were performed using isis  <cit> , a widely used commercial 2d chemical database.
isis uses structure-keys in conjunction with indexing for answering queries.
however, molecular similarity using isis is strictly 2d-substructure-based and can not incorporate issues like conformations.
the consolidated results from these two stages are presented in table  <dig>  the first row of the table shows results obtained with isis.
the second row presents the results obtained with  <dig> conformers for each of the query and model molecules.
the final row shows the accuracy of the retrieval process when distinct conformers  were employed.
here, the asterisk denotes the aforementioned fact that for some molecules  <dig> distinct stable conformers were not obtained.
in this setting, of the  <dig> molecules,  <dig> were correctly identified.
an analysis of the results obtained in this step indicates that the accuracy of the proposed approach during query-retrieval is comparable to that of isis, even though the proposed method addresses the query-retrieval problem in a setting that involves molecular conformations, surface-properties, and superposition-based effects and is therefore much more complex than the 2d structural motif-based search used in isis.
performance evaluation
the computational performance of the proposed approach was tested with respect to the molecular hashkeys algorithm  <cit> , which builds on the compass algorithm  <cit> .
this selection was based on the fact that both the proposed approach and molecular hashkeys  seek to define the surface-based similarity between molecules.
the distinctions of our approach from these methods lie in how the modelling of molecular shape and field-effects are accomplished as well as in how the similarity is computed.
furthermore, our selection was also motivated by the fact that compass along with its derivatives have been extensively applied in pharmaceutical research settings and the published results  <cit>  as well as our own investigations show it to be amongst the most efficient approaches currently available for determining surface-based molecular similarity.
in our experiment,  <dig> molecules from the mddr collection were compared against each other, with  <dig> conformers for the model and one for the query.
both the systems reported a 100% recognition rate on this subset of molecules.
however, the time requirements were significantly different.
a graph plotting the time required for the similarity computation with the proposed technique is shown in figure  <dig> .
figure  <dig>  shows a comparison of the performance with the molecular hashkeys method .
on an average, with the proposed technique  <dig> conformers were processed  every second, while with molecular hashkeys, one conformer was matched every two seconds.
both results were obtained on an sgi indigo <dig> machine.
another recent commercially available method  <cit>  reports matching speed of  <dig> minutes per molecule .
it should be noted that descriptor generation  in both the methods took similar time, averaging around  <dig> seconds per conformer and was done offline.
however, in the current implementation of our approach, histogram generation is done online.
therefore, further speedups are possible by making histogram generation part of the one-time off-line computation.
for a given molecular property and its corresponding property-histogram having n bins, computing the similarity of a pair of conformers using the proposed technique  involves determining the histogram intersection scores for matching the spatial distribution of points corresponding to the each of the aforementioned n bins.
for each bin, this score is then used to weight the intersection score of the property-histogram.
for an encapsulating sphere of circumference c, characterizing the spatial distribution requires o bins.
since histogram intersection is linear in the number of bins, the matching complexity is therefore o.
given the size of molecular repositories, a key technical problem is the design of indexing techniques.
this is due to the fact that even highly efficient matching techniques, such as the one presented, require distance comparisons which grow linearly with the number of molecules in the database.
indexing techniques can be broadly classified as  spatial access methods, such as quadtree  <cit> , r-tree  <cit> , and kd-tree  <cit> , which are applicable when items in the repository are represented by a finite set of attributes or features and euclidean distance between a pair of features/attributes can be defined.
such methods function by using the euclidean structure of the embedding space to divide repository entities into clusters and avoiding the search of some clusters during retrieval.
distance-based indexing methods, such as gnat-tree  <cit>  and vp-tree  <cit> , which rely only on pair-wise distances for data retrieval and employ the triangle-inequality for pruning the search space.
while a detailed analysis of indexing techniques is beyond the scope of this paper, it is important to note that the performance of spatial access methods is very good for small number of attributes and rapidly degrades as the number of features increase.
on the other hand, the efficiency of distance-based indexing is not good for large data collections.
this underlines the necessity for developing indexing techniques, such as  <cit> , which utilize specificities of structural data in the design of the indexing strategy.
validation through application in structure-activity models
a structure-property model captures the relationship between the bio-chemical properties of a molecule and its physicochemical description  <cit>  by envisaging the biochemical property Φ of a molecule mi as the function of its "chemical constitution":
Φ = f
the basic elements needed for the development of a structure-property model are:  assay results describing the bio-chemical property of interest,  a set of parameters describing the molecular structure and its physicochemical attributes, and  the learning formulation along with a statistical or machine learning technique.
as part of the validation experiments, similarity information derived using the proposed technique was used to model absorption through an in-vitro cell line.
the data set consisted of  <dig> compounds that were tested using the caco- <dig> assay.
the caco- <dig>  provides a close approximation of in vivo absorption and can be used to model the epithelial cell layer barrier and absorption from the intestinal lumen to the blood stream.
the assay protocol used in this experiment was designed to measure uni-directional flux and all compounds were analysed at identical initial concentrations.
the range of measured values was between  <dig> %  to  <dig> %  flux units.
the set of parameters describing the molecular structure consisted of a 31-dimensional descriptor vector.
the first element of this vector was the computed octanol-water partition coefficient .
the remaining thirty elements of the vector were obtained by computing the similarity  of the molecules tested in the assay to a predefined set of thirty molecules that represented a maximally diverse set of the mddr collection.
the central idea behind such form of molecular description relates to the concept of vector quantization  <cit>  and implicit dimensionality reduction  <cit> .
a backpropagation-based neural network with one hidden layer was then used to estimate the unknown continuous relationship between the molecules and caco- <dig> permeation.
two measures were used for evaluation of the results.
the first is a ratio-scale measure called cross-validated r <dig> and shows how well the model predicts data that was not used during model construction.
this measure is defined as ):
r2=1−∑i2∑i2
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgybgcdaahaawcbeqaaiabikdayaaakiabg2da9iabigdaxiabgkhitmaalaaabawaaabuaeaacqggoaakcqwgwbgvdawgaawcbagaemyaakgabeaakiabgkhitiabdcfaqnaabaaaleaacqwgpbqaaeqaaogaeiykakyaawbaasqabeaacqaiyagmaaaabagaemyaakgabeqdcqghris5aagcbawaaabuaeaacqggoaakcqwgwbgvdawgaawcbagaemyaakgabeaakiabgkhitiqbdafawzaaragaeiykakyaawbaasqabeaacqaiyagmaaaabagaemyaakgabeqdcqghris5aaaaaaa@4a34@
here, vi is the experimentally determined property of the molecule mi, pi is its predicted property, and v¯
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgwbgvgaqeaaaa@2df9@ is the mean experimental property value.
the second measure is an ordinal measure called kendall's τ, which shows how well the ordering of the data is preserved during prediction by the model.
this measure, computed for n molecules, is defined as:
τ=|correctly orderd pairs|−|incorrectly ordered pairs|n/2
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaiigacqwfepadcqgh9aqpdawcaaqaaiabcyha8jabbogajjabb+gavjabbkhayjabbkhayjabbwgaljabbogajjabbsha0jabbygasjabbmha5jabbccagiabb+gavjabbkhayjabbsgakjabbwgaljabbkhayjabbsgakjabbccagiabbchawjabbggahjabbmgapjabbkhayjabbohazjabcyha8jabgkhitiabcyha8jabbmgapjabb6gaujabbogajjabb+gavjabbkhayjabbkhayjabbwgaljabbogajjabbsha0jabbygasjabbmha5jabbccagiabb+gavjabbkhayjabbsgakjabbwgaljabbkhayjabbwgaljabbsgakjabbccagiabbchawjabbggahjabbmgapjabbkhayjabbohazjabcyha8bqaaiabd6gaujabcicaoiabd6gaujabgkhitiabigdaxiabcmcapiabc+caviabikdayaaaaaa@7cc5@
kendall's τ is determined by considering all pairs of predicted absorption values and the corresponding actual absorption values .
a pair of predicted values is deemed to be correctly ordered if the ordering coincides with that of the experimentally derived values.
the numerator in eq.
<dig> is the difference between the numbers of correctly and incorrectly ordered pairs.
the denominator denotes the number of all possible pairs.
thus, if all pairs are correctly ordered, the maximum value of τ =  <dig> is obtained.
on the other hand, the minimum value of τ = - <dig> is obtained if none of the pairs of predicted values retain the experimentally derived ordering.
an ordinal measure, such as kendall's τ, reflects how well the model can predict the ordering  of the molecules.
this provides an alternate way to assess the model as compared to measuring the numeric predictive accuracy.
therefore, using a combination of the above measures allows a multifaceted approach to model evaluation.
the assay values for twenty of the thirty compounds were made available for model construction and constituted the learning phase for the neural network.
as part of the model construction step, the complete cross-correlation matrix of the descriptors was computed and the top eight least correlated descriptors used to learn the  mapping between the molecules and their permeability values.
learning was stopped when the cross-validated error became lower than a predefined threshold.
we begin by presenting the analysis of the method's performance in a leave-one-out cross-validated setting on the training set.
in this setting, one compound was randomly excluded from the training set and the remaining compounds used to learn a model that predicted the permeability for the excluded compound.
the results are shown in figures  <dig> and  <dig>  the numbers on the x-axis identify each of the molecules in the test set and the y-axis shows the permeation values in terms of flux-units.
figure  <dig> shows the predictive performance of the model constructed with the proposed similarity measure.
in this case the cross-validated r <dig> equalled  <dig>  and the value for kendall's τ was  <dig> .
in figure  <dig>  results are shown for the identical problem setting, where the only exception was the use of the molecular hashkeys algorithm for computing the similarity of the molecules.
for the best model learnt based on descriptors generated using molecular hashkeys, the value for cross-validated r <dig> equalled  <dig>  and kendall's τ equalled  <dig> .
it should be emphasized that in both experiments an identical learning algorithm  was used and the only distinction was in the similarity values .
we also note that the relatively low value for kendall's τ  occurred because the original data had compounds showing no absorption.
the models that were derived typically assigned very low  absorption values to these molecules, thus leading to lower values for kendall's τ .
the model based on similarity values derived using molecular hashkeys also exhibited ordering inconsistencies across the entire range of absorption values.
finally, figure  <dig> shows the performance of the structure-activity model obtained using the proposed method, on the test set of  <dig> molecules.
here, the x-axis identifies each of the ten molecules in the test set, while the y-axis corresponds to the permeation values.
in figure  <dig> – , we present an analysis of the method's performance in a leave-n-out cross-validated setting.
the goal of this experiment was to examine the robustness of the model under conditions where a significant number of samples get left out during the model construction stage.
during each iteration of the experiment,  <dig> of the  <dig> molecules were randomly excluded.
the remaining  <dig> molecules were then used for model construction and for predicting the absorption values of the  <dig> excluded molecules.
the results are based on the performance of the model in  <dig> iterations of the leave-n-out experiment.
the number of iterations is arbitrarily selected.
to help visualize the results, the absorption values and predictions are grouped into three bins: bin  <dig> corresponds to molecules exhibiting poor absorption , bin  <dig> corresponds to molecules that exhibited medium absorption , and bin  <dig> corresponds to molecules that showed high permeation .
the bar-chart in figure  <dig> shows the number of incorrect bin assignments that were made: over the  <dig> iterations, 85% of the overall bin assignments were correct and in 15% of the assignments, an error of one adjacent bin was observed .
however, in none of the iterations, was a poorly absorbed compound predicted to be a highly absorbed one or a highly absorbed compound predicted to be a poorly absorbed one.
figure  <dig>  presents the distribution of the prediction results across the  <dig> iterations of the leave-n-out cross-validation experiment:  <dig> of the  <dig> iterations resulted in perfect bin assignments and  <dig> of the  <dig> iterations had 83% correct bin assignments.
further,  <dig> of the iterations had 67% accurate assignments and only one of the  <dig> iterations had 50% accuracy in bin assignments.
these statistics indicate the high consistency in the prediction performance of the model across variations in the training set.
CONCLUSIONS
in this paper, we considered the problem of defining similarity between molecules based on complex surface-based representations.
such representations capture the physics of the molecules better than commonly used molecular-graph-based approaches and can therefore have significant relevance in molecular query-retrieval, similarity-based exploration of structural space, and structure-activity modelling.
we have presented a novel approach for defining a standard coordinate system for describing complex surface-based molecular descriptions.
for computing the similarity of molecules, we propose a novel formulation of histogram intersection which can take into account the distribution of surface properties in 3d space.
experimental results indicate that the similarity formulation can be used for highly-accurate query-retrieval and outperforms, in terms of computational speed, both existing research and commercially available solutions.
the proposed approach was also validated by applying it in building structure-activity models for complex bio-chemical properties.
the efficacy and computational efficiency of the proposed approach underline the important role it can play in querying and exploration of large molecular repositories.

 across all biological and pharmaceutical investigations, the discovery of molecules with desired biological activity is an important goal. efforts to attain this goal are strongly driven by the notion of molecular similarity because in general similar molecules tend to behave similarly. effective determination of molecular similarity requires accounting for both structural and physicochemical characteristics of molecules. it is therefore closely related to the notions of molecular representation and molecular descriptors. we begin this section with a review of techniques for molecular representation and molecular descriptors. next, we outline and discuss different formulations of the molecular query-retrieval problem. this is followed by a review of the prior research in this area. the last subsection introduces the problems associated with determining molecular similarity using complex 3d surface-based descriptors introduction to molecular representations and descriptors in their simplest form, molecules can be represented using chemical formulae. however, different structures may yield the same formula even though they possess dissimilar physical or biochemical properties. therefore, commonly employed representation frameworks tend to emphasize a more explicit characterization of the molecular structure and include: one-dimensional string-based descriptors, such as smiles obtained by ordered traversal of the molecular graph, vector-space representation of attributes of a molecule called structure keys that encode presence/absence of predefined sub-structural motifs in the molecule in a binary string, two-dimensional and three-dimensional graphscharacterizing molecular connectivity and inter-atomic distances, and three-dimensional surface based representations, such as the connolly surface. the connolly surface is obtained by rolling a probe-atom over the molecule and is defined as the set of points where the surface of the probe atom touches the van der walls surfaces of the atoms in the molecule. it may be noted that the complexity of representations is directly correlated with their fidelity in describing biochemical characteristics of molecules. for example, simple characteristics of molecules such as their atomic weight or connectivity can be derived from smile strings. however, more complex biochemical properties like molecule-molecule interactions or permeation through membranes are more accurately modelled using surface-based representations. molecular descriptors are computationally determinable characteristics of a molecule that describe specific molecular properties. examples include physical-chemical descriptors such as the number of rotatable bonds, polar surface area, electronegativity, descriptors of molecular connectivity such as the wiener number, the randic index, structure keys and molecular fingerprints, eigenvalue-based descriptors, molecular moment-based descriptors such as comma, and surface and field-based descriptors. other descriptors include donor-acceptor atoms and those based on the molecular wave/density functions. modern approaches to correlating molecular structure with biological activity emphasize the use of molecular fields; given any molecular property p that can be calculated at an arbitrary point around a molecule, a field can be created by integrating p with respect to volume. field-based descriptors typically are superposition-based, in that their value at any particular point, takes into account the influence of multiple atoms of the molecule at that point. it is also straightforward to define field-based descriptors at the molecular surface, thereby incorporating both physicochemical and physically-relevant structural attributes in a single framework. formulations for molecular query-retrieval and analysis of prior research the problem of molecular query-retrieval can be approached from two primary and interrelated perspectives: • query formulation two main forms of formulating the query can be distinguished: sub-structure-based query, where the query-structure is constrained to be a proper subset of each of the retrieved structures. whole-molecule query, where molecules are retrieved in terms of their overall similarity, as defined using appropriate similarity functions, to the query molecule. it is important to note that sub-structure searching requires the user to have a clear picture of the structures which are to be retrieved prior to issuing the query. typically such detailed knowledge is available only when the mechanism of action of the molecule is established in terms of its activity as determined by specific structural fragments. in contrast, "whole molecule" similarity is suitable for exploring structural space, generating hypotheses, or querying chemical databases when detailed structure-activity information, at the level necessary for sub-structure querying is unavailable. • molecular representation molecular representations have varying capabilities in terms of modelling biochemical characteristics of molecules. as noted earlier, surface-based representations/descriptors are more faithful to the actual physics of molecules than molecular graphs-based approaches. at the same time, graph-based representations, owing to their graphical similarity to chemical notations, tend to be highly intuitive and are also computationally easier to characterize. early attempts at determining molecular similarity, like, used variations on the sum of inter-atomic distances. later approaches have looked at schemes for atom re-labelling to minimize a difference-distance matrix or decomposing the molecular distance and connectivity graphs into sub-graphs which are numerically characterized and compared. other efforts have tried to characterize similarity of molecular graphs, using edit distances, frequent sub-graphs, or maximal common sub-graphs. these techniques either focus on building structure-property models or do not efficaciously scale up with repository size. with our research goals in mind, at the state-of-the-art, two classes of techniques merit discussion: matching techniques using fixed-size representation vectors: have been amongst the most efficient and are employed almost in all small molecule repositories of significant size. in this approach a molecule is represented using a fixed size vector. each element of the vector encodes for the presence of a predefined attribute, for example, specific structural motifs or the unique labelled paths obtained during a traversal. the vectors are then compared using well established dissimilarity measures such as the hamming, euclidean, and tanimoto measures. matching techniques using 3d molecular graphs: depend on super-positioning the 3d graphs of the molecules being compared. significant research in this context has been done of aligning structures of large molecules leading to techniques such as dali, ssm, ssap, structal, ce, lock, and lsqman. other efforts include the application of geometric hashing and its variations. in, molecular similarity is defined using surface and field characteristics: first, the field-effects around a molecule are estimated. then, the orientation of the query/model molecule, is varied to minimize an rms error between the field values. the use of fixed-size representation vectors has lead to practical solutions for querying large molecular repositories. however, such approaches have several severe drawbacks: they are limited to 2d information and incapable of being used for complex bio-chemically relevant representations/descriptors. they are incapable of representing bioisosteres. such representations are predefined rather than being data-driven. therefore, they are incapable of capturing specificities of molecules which were not preconceived. on the other hand current approaches to 3d matching simply don't scale with respect to repository size and time constraints typical to modern query-retrieval formulations. moreover, such approaches, even when they seek to compare surface-based descriptors, do so indirectly. that is, the 3d graphs are superimposed and only then are the respective surfaces compared. such an approach can miss molecules which have similar surface/field-based properties, but whose 3d structures do not necessarily superimpose well. problem characteristics and challenges the problem of determining the similarity of molecules when they are represented using complex 3d surface-based descriptors presents some unique challenges which include: definition of a standard coordinate system for surface-based molecular representations: to compare molecules using their surface-based descriptions, it is necessary to have a way of representing the shape of their surfaces. the complexity lies in defining an intrinsic coordinate system over the curved molecular surface that maps a point on the curved surface to a point on a standard coordinate system. additionally, such a mapping should be one-to-one between points on the molecular surface and the standard coordinate system. multi-modal nature of molecular properties: molecular properties like geometry and donor/acceptor fields have entirely different characteristics. for example, while the geometric representation of a molecule is unique, donor/acceptor fields are superposition-based. representation frameworks need to account for such issues. query efficiency: it is typical to conduct molecular similarity queries over large sets ranging from thousands to millions of molecules. the latter order of magnitude is especially common in pharmaceutical settings. it is therefore imperative for similarity determination approaches to be computationally efficient.  three different types of experiments were conducted to study the efficacy of the proposed method: investigation of the method's accuracy in query-retrieval settings, evaluation of its performance, and validation through applications in structure-activity modelling problems. each experiment incorporated two stages: the first stage involved a direct application of the method on a data set with subsequent analysis of the results. in the second stage, a comparative study was performed by applying a state-of-the-art research or commercial technique on the same data set. subsequently the results were analysed to evaluate the proposed approach. accuracy in query-retrieval settings the method was tested in a query-retrieval setting on a subset of molecules randomly selected from the mddr collection. the mddr collection consists of molecules that are either marketed drugs or have reached advanced stages in a drug discovery process. each of the molecules was successively used as a query against the rest of the molecules. the query and model molecules were each represented by conformers, i.e. distinct molecular conformers were used per similarity computation. since the proposed method does not require super-positioning of the underlying structures, to distinguish its performance from approaches that do so, a variation of the experiment was performed where the query was represented by novel conformers. it may be noted, that for some molecules, novel energetically stable conformers could not be obtained. in such cases, as many novel conformers as could be derived for each specific structure were used. in the second stage of this experiment, for purposes of comparison, the query-retrieval experiments were performed using isis, a widely used commercial 2d chemical database. isis uses structure-keys in conjunction with indexing for answering queries. however, molecular similarity using isis is strictly 2d-substructure-based and can not incorporate issues like conformations. the consolidated results from these two stages are presented in table the first row of the table shows results obtained with isis. the second row presents the results obtained with conformers for each of the query and model molecules. the final row shows the accuracy of the retrieval process when distinct conformers were employed. here, the asterisk denotes the aforementioned fact that for some molecules distinct stable conformers were not obtained. in this setting, of the molecules, were correctly identified. an analysis of the results obtained in this step indicates that the accuracy of the proposed approach during query-retrieval is comparable to that of isis, even though the proposed method addresses the query-retrieval problem in a setting that involves molecular conformations, surface-properties, and superposition-based effects and is therefore much more complex than the 2d structural motif-based search used in isis. performance evaluation the computational performance of the proposed approach was tested with respect to the molecular hashkeys algorithm, which builds on the compass algorithm. this selection was based on the fact that both the proposed approach and molecular hashkeys seek to define the surface-based similarity between molecules. the distinctions of our approach from these methods lie in how the modelling of molecular shape and field-effects are accomplished as well as in how the similarity is computed. furthermore, our selection was also motivated by the fact that compass along with its derivatives have been extensively applied in pharmaceutical research settings and the published results as well as our own investigations show it to be amongst the most efficient approaches currently available for determining surface-based molecular similarity. in our experiment, molecules from the mddr collection were compared against each other, with conformers for the model and one for the query. both the systems reported a 100% recognition rate on this subset of molecules. however, the time requirements were significantly different. a graph plotting the time required for the similarity computation with the proposed technique is shown in figure. figure shows a comparison of the performance with the molecular hashkeys method. on an average, with the proposed technique conformers were processed every second, while with molecular hashkeys, one conformer was matched every two seconds. both results were obtained on an sgi indigo machine. another recent commercially available method reports matching speed of minutes per molecule. it should be noted that descriptor generation in both the methods took similar time, averaging around seconds per conformer and was done offline. however, in the current implementation of our approach, histogram generation is done online. therefore, further speedups are possible by making histogram generation part of the one-time off-line computation. for a given molecular property and its corresponding property-histogram having n bins, computing the similarity of a pair of conformers using the proposed technique involves determining the histogram intersection scores for matching the spatial distribution of points corresponding to the each of the aforementioned n bins. for each bin, this score is then used to weight the intersection score of the property-histogram. for an encapsulating sphere of circumference c, characterizing the spatial distribution requires o bins. since histogram intersection is linear in the number of bins, the matching complexity is therefore o. given the size of molecular repositories, a key technical problem is the design of indexing techniques. this is due to the fact that even highly efficient matching techniques, such as the one presented, require distance comparisons which grow linearly with the number of molecules in the database. indexing techniques can be broadly classified as spatial access methods, such as quadtree, r-tree, and kd-tree, which are applicable when items in the repository are represented by a finite set of attributes or features and euclidean distance between a pair of features/attributes can be defined. such methods function by using the euclidean structure of the embedding space to divide repository entities into clusters and avoiding the search of some clusters during retrieval. distance-based indexing methods, such as gnat-tree and vp-tree, which rely only on pair-wise distances for data retrieval and employ the triangle-inequality for pruning the search space. while a detailed analysis of indexing techniques is beyond the scope of this paper, it is important to note that the performance of spatial access methods is very good for small number of attributes and rapidly degrades as the number of features increase. on the other hand, the efficiency of distance-based indexing is not good for large data collections. this underlines the necessity for developing indexing techniques, such as, which utilize specificities of structural data in the design of the indexing strategy. validation through application in structure-activity models a structure-property model captures the relationship between the bio-chemical properties of a molecule and its physicochemical description by envisaging the biochemical property Φ of a molecule mi as the function of its "chemical constitution": Φ = f the basic elements needed for the development of a structure-property model are: assay results describing the bio-chemical property of interest, a set of parameters describing the molecular structure and its physicochemical attributes, and the learning formulation along with a statistical or machine learning technique. as part of the validation experiments, similarity information derived using the proposed technique was used to model absorption through an in-vitro cell line. the data set consisted of compounds that were tested using the caco- assay. the caco- provides a close approximation of in vivo absorption and can be used to model the epithelial cell layer barrier and absorption from the intestinal lumen to the blood stream. the assay protocol used in this experiment was designed to measure uni-directional flux and all compounds were analysed at identical initial concentrations. the range of measured values was between % to % flux units. the set of parameters describing the molecular structure consisted of a 31-dimensional descriptor vector. the first element of this vector was the computed octanol-water partition coefficient. the remaining thirty elements of the vector were obtained by computing the similarity of the molecules tested in the assay to a predefined set of thirty molecules that represented a maximally diverse set of the mddr collection. the central idea behind such form of molecular description relates to the concept of vector quantization and implicit dimensionality reduction. a backpropagation-based neural network with one hidden layer was then used to estimate the unknown continuous relationship between the molecules and caco- permeation. two measures were used for evaluation of the results. the first is a ratio-scale measure called cross-validated r and shows how well the model predicts data that was not used during model construction. this measure is defined as ): r2=1−∑i2∑i2 mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgybgcdaahaawcbeqaaiabikdayaaakiabg2da9iabigdaxiabgkhitmaalaaabawaaabuaeaacqggoaakcqwgwbgvdawgaawcbagaemyaakgabeaakiabgkhitiabdcfaqnaabaaaleaacqwgpbqaaeqaaogaeiykakyaawbaasqabeaacqaiyagmaaaabagaemyaakgabeqdcqghris5aagcbawaaabuaeaacqggoaakcqwgwbgvdawgaawcbagaemyaakgabeaakiabgkhitiqbdafawzaaragaeiykakyaawbaasqabeaacqaiyagmaaaabagaemyaakgabeqdcqghris5aaaaaaa@4a34@ here, vi is the experimentally determined property of the molecule mi, pi is its predicted property, and v¯ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgwbgvgaqeaaaa@2df9@ is the mean experimental property value. the second measure is an ordinal measure called kendall's τ, which shows how well the ordering of the data is preserved during prediction by the model. this measure, computed for n molecules, is defined as: τ=|correctly orderd pairs|−|incorrectly ordered pairs|n/2 mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaiigacqwfepadcqgh9aqpdawcaaqaaiabcyha8jabbogajjabb+gavjabbkhayjabbkhayjabbwgaljabbogajjabbsha0jabbygasjabbmha5jabbccagiabb+gavjabbkhayjabbsgakjabbwgaljabbkhayjabbsgakjabbccagiabbchawjabbggahjabbmgapjabbkhayjabbohazjabcyha8jabgkhitiabcyha8jabbmgapjabb6gaujabbogajjabb+gavjabbkhayjabbkhayjabbwgaljabbogajjabbsha0jabbygasjabbmha5jabbccagiabb+gavjabbkhayjabbsgakjabbwgaljabbkhayjabbwgaljabbsgakjabbccagiabbchawjabbggahjabbmgapjabbkhayjabbohazjabcyha8bqaaiabd6gaujabcicaoiabd6gaujabgkhitiabigdaxiabcmcapiabc+caviabikdayaaaaaa@7cc5@ kendall's τ is determined by considering all pairs of predicted absorption values and the corresponding actual absorption values. a pair of predicted values is deemed to be correctly ordered if the ordering coincides with that of the experimentally derived values. the numerator in eq. is the difference between the numbers of correctly and incorrectly ordered pairs. the denominator denotes the number of all possible pairs. thus, if all pairs are correctly ordered, the maximum value of τ = is obtained. on the other hand, the minimum value of τ = - is obtained if none of the pairs of predicted values retain the experimentally derived ordering. an ordinal measure, such as kendall's τ, reflects how well the model can predict the ordering of the molecules. this provides an alternate way to assess the model as compared to measuring the numeric predictive accuracy. therefore, using a combination of the above measures allows a multifaceted approach to model evaluation. the assay values for twenty of the thirty compounds were made available for model construction and constituted the learning phase for the neural network. as part of the model construction step, the complete cross-correlation matrix of the descriptors was computed and the top eight least correlated descriptors used to learn the mapping between the molecules and their permeability values. learning was stopped when the cross-validated error became lower than a predefined threshold. we begin by presenting the analysis of the method's performance in a leave-one-out cross-validated setting on the training set. in this setting, one compound was randomly excluded from the training set and the remaining compounds used to learn a model that predicted the permeability for the excluded compound. the results are shown in figures and the numbers on the x-axis identify each of the molecules in the test set and the y-axis shows the permeation values in terms of flux-units. figure shows the predictive performance of the model constructed with the proposed similarity measure. in this case the cross-validated r equalled and the value for kendall's τ was. in figure results are shown for the identical problem setting, where the only exception was the use of the molecular hashkeys algorithm for computing the similarity of the molecules. for the best model learnt based on descriptors generated using molecular hashkeys, the value for cross-validated r equalled and kendall's τ equalled. it should be emphasized that in both experiments an identical learning algorithm was used and the only distinction was in the similarity values. we also note that the relatively low value for kendall's τ occurred because the original data had compounds showing no absorption. the models that were derived typically assigned very low absorption values to these molecules, thus leading to lower values for kendall's τ. the model based on similarity values derived using molecular hashkeys also exhibited ordering inconsistencies across the entire range of absorption values. finally, figure shows the performance of the structure-activity model obtained using the proposed method, on the test set of molecules. here, the x-axis identifies each of the ten molecules in the test set, while the y-axis corresponds to the permeation values. in figure –, we present an analysis of the method's performance in a leave-n-out cross-validated setting. the goal of this experiment was to examine the robustness of the model under conditions where a significant number of samples get left out during the model construction stage. during each iteration of the experiment, of the molecules were randomly excluded. the remaining molecules were then used for model construction and for predicting the absorption values of the excluded molecules. the results are based on the performance of the model in iterations of the leave-n-out experiment. the number of iterations is arbitrarily selected. to help visualize the results, the absorption values and predictions are grouped into three bins: bin corresponds to molecules exhibiting poor absorption, bin corresponds to molecules that exhibited medium absorption, and bin corresponds to molecules that showed high permeation. the bar-chart in figure shows the number of incorrect bin assignments that were made: over the iterations, 85% of the overall bin assignments were correct and in 15% of the assignments, an error of one adjacent bin was observed. however, in none of the iterations, was a poorly absorbed compound predicted to be a highly absorbed one or a highly absorbed compound predicted to be a poorly absorbed one. figure presents the distribution of the prediction results across the iterations of the leave-n-out cross-validation experiment: of the iterations resulted in perfect bin assignments and of the iterations had 83% correct bin assignments. further, of the iterations had 67% accurate assignments and only one of the iterations had 50% accuracy in bin assignments. these statistics indicate the high consistency in the prediction performance of the model across variations in the training set.  in this paper, we considered the problem of defining similarity between molecules based on complex surface-based representations. such representations capture the physics of the molecules better than commonly used molecular-graph-based approaches and can therefore have significant relevance in molecular query-retrieval, similarity-based exploration of structural space, and structure-activity modelling. we have presented a novel approach for defining a standard coordinate system for describing complex surface-based molecular descriptions. for computing the similarity of molecules, we propose a novel formulation of histogram intersection which can take into account the distribution of surface properties in 3d space. experimental results indicate that the similarity formulation can be used for highly-accurate query-retrieval and outperforms, in terms of computational speed, both existing research and commercially available solutions. the proposed approach was also validated by applying it in building structure-activity models for complex bio-chemical properties. the efficacy and computational efficiency of the proposed approach underline the important role it can play in querying and exploration of large molecular repositories. 
determining molecular similarity is related to the choice of molecular representation. therefore molecular similarity is a key notion in investigations targeting exploration of molecular structural space, query-retrieval in molecular databases, and structure-activity modelling. however, most techniques for determining molecular similarity tend to focus on idealized 2d graph-based descriptors due to the complexity that accompanies reasoning with more elaborate representations. surface-based molecular similarity is subsequently determined by computing the similarity of the surface-property distributions using a novel formulation of histogram-intersection. information from such representations is both surface-based and volumetric. the importance of this problem is due to the fact that the biochemical characteristics of a molecule are closely related to its structure. the similarity formulation is not only sensitive to the 3d distribution of the surface properties, but is also highly efficient to compute. it proposes an intrinsic, spherical representation that systematically maps points on a molecular surface to points on a standard coordinate system. molecular surface properties such as shape, field strengths, and effects due to field super-positioningcan then be captured as distributions on the surface of the sphere. the proposed method obviates the computationally expensive step of molecular pose-optimisation, can incorporate conformational variations, and facilitates highly efficient determination of similarity by directly comparing molecular surfaces and surface-based properties.
 discerning the similarity between molecules is a challenging problem in drug discovery as well as in molecular biology. the importance of this problem is due to the fact that the biochemical characteristics of a molecule are closely related to its structure. therefore molecular similarity is a key notion in investigations targeting exploration of molecular structural space, query-retrieval in molecular databases, and structure-activity modelling. determining molecular similarity is related to the choice of molecular representation. currently, representations with high descriptive power and physical relevance like 3d surface-based descriptors are available. information from such representations is both surface-based and volumetric. however, most techniques for determining molecular similarity tend to focus on idealized 2d graph-based descriptors due to the complexity that accompanies reasoning with more elaborate representations.  this paper addresses the problem of determining similarity when molecules are described using complex surface-based representations. it proposes an intrinsic, spherical representation that systematically maps points on a molecular surface to points on a standard coordinate system. molecular surface properties such as shape, field strengths, and effects due to field super-positioningcan then be captured as distributions on the surface of the sphere. surface-based molecular similarity is subsequently determined by computing the similarity of the surface-property distributions using a novel formulation of histogram-intersection. the similarity formulation is not only sensitive to the 3d distribution of the surface properties, but is also highly efficient to compute.  the proposed method obviates the computationally expensive step of molecular pose-optimisation, can incorporate conformational variations, and facilitates highly efficient determination of similarity by directly comparing molecular surfaces and surface-based properties. retrieval performance, applications in structure-activity modeling of complex biological properties, and comparisons with existing research and commercial methods demonstrate the validity and effectiveness of the approach. 7– september international workshop on multiscale biological imaging, data mining and informatics santa barbara, ca, usa 