BACKGROUND
in the context of drug discovery research, it is challenging but of great importance to be able to determine which 3-dimensional  shapes  of a given molecule are responsible for its observed biological activity.
due to structural flexibility, a molecule may adopt a wide range of conformers and the identification of the bioactive conformers is extremely important in order to understand the recognition mechanism between small molecules and proteins, which is crucial in drug discovery and development.
until now, the most reliable approach to obtain the bioactive conformer is to use the x-ray crystal structure of a ligand-protein complex; however, the number of such structures is limited because of the experimental difficulty in obtaining the crystals, especially for transmembrane proteins, such as g protein-coupled receptors   <cit>  and membrane transporters.
we were interested to apply to this problem a machine-learning approach which does not require crystal structures, named multiple-instance learning  via embedded instance selection .
miles has been demonstrated as an efficient and accurate approach to solve different multiple-instance problems  <cit> , in particular, to predict drug activity using musk data sets.
in the context of drug activity prediction, miles enables the construction of a quantitative structure-activity relationship  model, and subsequently the identification of bioactive conformers.
mil is a variant of supervised learning, and it has been applied for a variety of learning problems including drug activity prediction  <cit> , image database retrieval  <cit> , text categorization  <cit> , and natural scene classification  <cit> .
in the context of drug activity prediction, the observed biological activity is associated with a single molecule  without knowing which conformer or conformers  are responsible.
furthermore, a molecule is biologically active if and only if at least one of its conformers is responsible for the observed bioactivity; and the molecule is inactive if none of its conformers is responsible .
a difficulty in implementation arises from the fact that different molecules have a different number of conformers, since some molecules having multiple rotatable bonds are highly flexible and others with rigid structures only have a small numbers of conformers.
the overall strategy for structural and data mining using miles  is summarized here.
first of all, a complete sampling of conformational space provides a large number of conformers for each molecule.
the molecules are themselves each already labelled as either positive or negative.
however, the labels for the conformers are unavailable during the model generation.
each conformer is denoted by a unique pharmacophore fingerprint which is a superior feature-based 3d descriptor unveiling structural similarity and diversity  <cit> .
the pharmacophore fingerprint is encoded into a binary string which indicates the presence or absence of a match to individual pharmacophore models.
since the exhaustively enumerated fingerprints have millions of bits, which may be beyond computational limits, a significance analysis of pharmacophore models  <cit>  is employed to determine the optimal subset of bits of the fingerprint.
subsequently, miles converts the mil to a standard supervised learning problem by embedding bags  into an instance-based  feature space via structural dissimilarity measures  <cit> .
finally, 1-norm svm is applied to select the most important features, identifying the highly significant conformers which help the most to distinguish active and inactive molecules, and, simultaneously, to construct a predictive classification model.
in the present work, miles has been applied to study the biological activities of several sets of molecules interacting with different receptor targets including glycogen synthase kinase- <dig> , cannabinoid receptors , and p-glycoprotein .
all of these receptors have been emerging as increasingly important therapeutic targets.
gsk- <dig> is a multifunctional serine/threonine protein kinase involved in the regulation of a wide range of cellular functions, including glucose metabolism, neuronal processes, chronic inflammation, cell proliferation and apoptosis  <cit> .
cbrs are a class of gpcrs and have been targeted for various disease conditions such as obesity, drug abuse disorders, inflammatory diseases, anorexia and vomiting  <cit> .
p-gp, a membrane transporter, is responsible for drug efflux and multidrug resistance, especially to cancer drugs  <cit> .
except for gsk- <dig>  the other proteins are membrane-associated and there is no available crystal structure for them.
the identification of bioactive conformers for the molecules targeting membrane-associated proteins using miles could be highly informative and desirable.
identified conformers can be used in various drug discovery approaches such as scaffold hopping, target fishing, and 3d structural alignment for 3d quantitative structure-activity relationship  studies.
based on our calculations, miles is highly competitive with the classical qsar approaches which do not include instance-based feature mapping in terms of predictive abilities.
meanwhile, we have validated that miles has the ability to identify a subset of highly relevant conformers, including the bioactive conformers, which contribute to the classification of active and inactive molecules.
methods
data set preparation
four different data sets were compiled through extensive literature search.
data set i includes all molecules exhibiting inhibitory activities for human gsk- <dig>  data sets ii and iii contain molecules modulating the intracellular activities of human cbrs.
since there are two identified cbr subtypes, cb <dig> and cb <dig>  two different data sets were prepared to study the protein-small molecule interactions of the receptors separately.
some of the molecules which have reported binding affinities for both cb subtypes were included in both data sets ii and iii.
data set iv contained compounds which had been tested as substrates of p-gp.
the molecules collected for each data set were labelled as either positive or negative.
a positive molecule has a high binding affinity with the target protein, whereas a negative molecule has a low binding affinity.
a single cutoff value has been widely used in the development of classification models.
however, it is inaccurate to use a single cutoff value for the separation of continuous biological activities in the context of drug activity prediction.
the biological activities are represented by continuous numbers, and the small differences between the values above and below the cutoff value cannot imply the distinct nature of binding affinity.
furthermore, the small difference in the bioassay results may arise from systematic errors introduced by different experimental protocols used in different labs, so it cannot be used as solid evidence for the classification of molecules.
therefore, multiple cutoff values were employed to separate molecules into positive and negative classes.
for data set i, the molecules were categorized into positive and negative molecules using cutoff values of ic <dig> ≤  <dig> nm and ic <dig> ≥  <dig> nm, respectively.
the molecules having inhibitory activities between the two cutoff values were considered as moderately active molecules, and were discarded from the data set.
the wide margin between the two cutoff values was used to account for the variances in biological assays.
for data set ii and iii, the molecules were classified as positive if the ki ≤  <dig> nm or ic <dig> ≤  <dig> nm or ec <dig> ≤  <dig> nm ; and the molecules were classified as negative if the ki ≥  <dig> nm or ic <dig> ≥  <dig> nm or ec <dig> ≥  <dig> nm.
the labels for the molecules in data set iv indicated whether or not the molecule is a substrate for the target protein.
they were obtained from the literature  <cit> .
division of training and test set
external validation was achieved using an independent test set.
the split of the data set into training and test sets was carried out using kohonen self-organizing maps  in canvas  <dig>  from schrödinger suite  <dig>  the som is trained using unsupervised learning to produce a square 2d grid map from the high dimensional input space.
each grid cell  contains a cluster of structurally similar molecules defined by the input vectors.
the som takes advantage of clustering capabilities so that the selected training set can represent the independent test set in terms of the input space and chemical domains.
molecular pharmacophore fingerprints were used to describe the relevant structural information of the molecules and were used as input variables to build the som.
the grid size of the map depends on the number of molecules in the data set.
for data sets i, ii, and iii, the kohonen maps built included  <dig> ×  <dig> neurons and  <dig> epochs.
for the data set iv, a kohonen map consisting of  <dig> ×  <dig> neurons and  <dig> epochs was built.
the molecules were then stratified and sampled from each neuron to select the training and test set molecules.
preprocessing and conformational sampling
the molecules  can be represented by mi, i =  <dig>  ⋯, l where l is the total number of molecules.
the 3d molecular structures were generated using the ligprep module from schrödinger suite  <dig>  and then subjected to preprocessing to enumerate all the possible tautomers.
the protonation states of ionizable groups were set to match ph =  <dig> , and the stereochemistry was retained from the original 3d structures.
in order to explore the conformational space exhaustively, the mixed torsional/low mode sampling method was employed, using macromodel from schrödinger suite  <dig>  the torsional sampling involves multiple monte carlo minimum searches for global exploration, and the low mode conformational search allows for automatic local exploration.
the torsional increment for each rotatable bond was set to 15° and the maximum number of total steps for torsional sampling was  <dig> .
the energy window for saving structures was set to  <dig>  kj/mol .
the small torsional increment and wide energy window were employed to provide a reasonable coverage of the conformational space.
each enumerated conformer was energy minimized to eliminate unreasonable geometries and reduce internal steric clashes, using the polak-ribière conjugate gradient method with a gradient convergence threshold of  <dig>  and a maximum of  <dig> iterations.
to remove redundant conformations, the maximum atom deviation cutoff was set to  <dig>  Å. as a result, each molecule mi has several possible conformers cij, j =  <dig>  ⋯, ni, where ni is the number of conformers  for molecule i.
in order to validate that miles can identify the bioactive conformers, we seeded  <dig> co-crystallized conformers, one for each of  <dig> molecules, in the set of sampled conformers for data set i. the validation process will be described in the following sections.
generation of pharmacophore fingerprints
the pharmacophore fingerprint as a measure of molecular similarity and diversity based on 3d pharmacophoric shape was enumerated using canvas  <dig>  from schrödinger suite  <dig>  each pharmacophore fingerprint associated with a unique conformer can be represented by a binary string, such as pij = {p <dig>  ⋯, pk, ⋯, pm} and encodes quantitative structural information for conformer cij, where each bit value pk, k =  <dig>  ⋯, m indicates the presence or absence of a match to a single pharmacophore model, representing a unique 3d arrangement of a number of pharmacophore features.
if the conformer fits the pharmacophore model for a particular k, in other words if the functional groups of the conformer fully overlap on all the pharmacophore features in the model, pk equals 1; otherwise, pk equals  <dig>  as a result, each conformer is associated with a unique pharmacophore fingerprint as a conformational signature, which enables us to describe quantitatively the 3d structural information.
the pharmacophore features employed in the models consist of hydrogen bond donor , hydrogen bond acceptor , hydrophobic group , negatively charged group , positively charged group , and aromatic ring .
in the present study, only four-feature based models were employed in order to allow a reasonable description of 3d orientation of the structures and retain information about molecular chirality, which is lost in three-feature based models.
different combinations of four out of six pharmacophore features were exhaustively enumerated and inter-feature distances were varied from  <dig>  Å to  <dig>  Å to form the different pharmacophore models.
each pharmacophore feature was treated as a bin with width  <dig>  Å, and the bin overlap threshold was  <dig>  Å. to fit to a model the conformer must fit to each of the four features in the model.
the maximum distance between pharmacophore features was set to  <dig>  Å in order to be able to cover the largest molecular structures in the databases.
the originally enumerated fingerprints were subject to occurrence-based filtering to remove the pharmacophore models present in less than 5% of the total number of molecules, since the pharmacophore models with a very low occurrence are not useful for discriminating between positive and negative classes.
significance analysis of pharmacophore models
the post-filtered pharmacophore fingerprints still have too many bits that lack information content, as indicated by too many '0' values.
therefore a nonparametric supervised learning approach, motivated by the significance analysis of microarrays  algorithm proposed by tibshirani et al.
<cit> , was applied to elucidate a consistent pattern from the numerous bits of pharmacophore fingerprints.
the detailed implementation and customization of the relevant procedures has been described in  <cit> .
the ranking score for each pharmacophore model was computed based on a two-class t-statistic, which calculates the ratio of the difference of occurrences of that model in positive and negative classes and compares to the standard deviation of occurrence measures.
pharmacophore models with ranking scores greater than a threshold have statistical significance, where the threshold was computed at the 90th percentile among  <dig> random permutations of the class labels across all the molecules.
in order to distinguish truly significant and falsely significant pharmacophore models, that ranking score serving as a true score was then compared with a reference score computed from the same set of random permutations.
if the difference between the true score and the reference score exceeds a cutoff threshold  then the pharmacophore model is truly significant; otherwise it is falsely significant.
instance-based feature mapping
miles provides a framework to convert a mil problem to a standard supervised learning problem via instance-based embedding.
all the conformers  belong to the instance-based feature space.
for convenience, all conformers in all molecules were lined up together, and were re-indexed in the embedded feature space as cr, r =  <dig>  ⋯, n where n= ∑i=1lni.
instance-based feature mapping can be accomplished using calculated structural dissimilarities.
different binary string distance measures were tested, including the soergel distance, dice distance, manhattan distance, and rogers-tanimoto distance .
the range of each dissimilarity measure was normalized to be  <cit>  by definition.
given a conformer cij denoted by a binary string pij, the dissimilarity measure, denoted as d, is calculated based on the number of occurrences of bit matches.
since one molecule is defined as a bag of multiple conformers , the dissimilarity measure for a molecule, denoted as d, is calculated based on the minimum distance using the closest instance in the bag for mi:
a
a let p <dig> and p <dig> be two pharmacophore fingerprints, a be the count of bits which are set to  <dig> in both p <dig> and p <dig>  b be the count of bits which are set to  <dig> in p <dig> but not in p <dig>  c be the count of bits which are set to  <dig> in p <dig> but not in p <dig>  and d be the count of bits which are set to  <dig> in both p <dig> and p <dig>  so a is called the number of total matches, b and c are called the number of single matches, and d is called the number of no matches.
dmi,cr=minjdcij,cr
the minimum distance calculation  extends the idea of the diverse density framework proposed for instance-based learning  <cit> .
joint feature selection and classification
since the molecules in the training sets are highly flexible, instance-based embedding, which provides a framework to convert a mil problem to a traditional supervised learning problem, may produce a very high dimensional feature space.
but many features are redundant or irrelevant, and do not play an important role in the classification of molecules as positive or negative.
so an efficient feature selection model is required for selection of an optimal subset of instance-based features.
considering its excellent performance in many applications  <cit> , the 1-norm svm method was chosen as a joint approach to construct classifiers and to select important features simultaneously.
the prediction model can be formulated as a linear classifier,
y=signωtm+b
where y denotes the class label as either positive or negative; ω and b are model parameters which are optimized during model generation; and m corresponds to a molecule , which is defined by an n-dimensional vector of dissimilarities calculated using , i.e., dissimilarities with respect to all conformers in all molecules.
the domain to  is therefore the space of rn, where n is the sum of all conformers in all molecules.
the svm approach constructs classifiers based on hyperplanes by minimizing a regularized training error, ξtraining,
λp•+ξtraining
where p is a regularizer, and λ is the regularization parameter, the only tuning parameter to be optimized by the user.
in 1-norm svm, the regularizer is chosen to be the 1-norm of the weight vector,
ω1= ∑rωr.
1-norm regularization favors sparse solutions, i.e., it drives many components of ω to zero.
once the optimal solution, with values ω* and b*, is obtained, the magnitude of its component ωr* indicates the significance of the r-th feature  in the instance-based feature space.
the features corresponding to non-zero entries in ω* are selected as important features, which are given as a set Γ=r:ωr*>0).
they are needed for the classification problem of interest
y=sign∑r∈Γωr*dmi,cr+b*.
note that  is equivalent to  where all weights with  <dig> values are ignored.
the domain of  is r|Γ|, a subspace of rn, defined by conformers whose weights are nonzero.
the features selected as important are called prototype conformers.
the plus or minus sign of ωr* indicates the positive or negative contribution, respectively, of the r-th prototype conformer to the putative bioactive conformers for each individual molecule.
our formulation of miles works directly on a dissimilarity mapping, which is different from a similarity mapping described by chen, et al.
<cit> .
one can transform a dissimilarity mapping to a similarity mapping via an exponential function.
however, this would introduce an additional super parameter, σ. although, a proper choice of σ could improve the performance of a model, the selection of a proper value for σ increases the computational cost significantly.
hence we use a dissimilarity mapping to reduce the computational cost.
identification of bioactive conformers
one appealing advantage of the miles algorithm is that it can identify the most significant instances in a bag according to their contributions to the classification of that bag.
in the context of drug activity prediction, we can identify the most significant conformers, called the bioactive conformers, for each molecule.
the putative bioactive conformers are the conformers that contributed the most to the classification of positive and negative molecules.
the identification of bioactive conformers can be accomplished with the assistance of the prototype conformers mentioned above .
given a molecule mi with its conformers cij, j =  <dig>  ⋯, ni, we define an index set ∑ = {j*: j* = argminj d, r ∈ Γ}), which includes the index for conformers closest to each prototype conformer.
hence, Σ defines a minimal set of conformers, called significant conformers, which are responsible for the classification of mi.
by definition, each prototype conformer in set Γ has a single conformer in set Σ closest to it, but each significant conformer in set Σ may have multiple prototype conformers in set Γ closest to it.
so we need to define an index set for each significant conformer in set Σ that includes the index for the prototype conformers closest to it, which is given as Γj*=r:r∈Γ,j*=argminjdcij,cr).
as a result, the contribution of each significant conformer to the classification of molecule can be calculated as
fcij*= ∑r∈Γj*ωr*dcij*,cr
wherefcij* denotes the contribution of the conformer cij* to the classification of the molecule mi.
the conformer in set Σ making the highest contribution is selected as a bioactive conformer.
in order to validate the ability of miles to identify the bioactive conformers, the contributions fcij* for the  <dig> seeded conformers, which were taken directly from co-crystallized complex structures, were calculated and ranked among all the conformers sampled for those  <dig> molecules.
classical qsar methods without instance-based embedding
in order to examine the predictive performance of miles, conventional classification approaches based on classical qsar principles without instance-based embedding were tested for comparison.
since one molecule is defined as a bag of multiple conformers , the pharmacophore fingerprint associated with a single molecule was obtained from the binary union of all of the pharmacophore fingerprints associated with the conformers of that molecule.
the same occurrence-based filtering and significance analysis of pharmacophore fingerprints were performed to select the optimal subsets of the fingerprints which constituted the feature space for the classical qsar studies.
three widely used classification algorithms including decision tree   <cit> , 1-norm svm  <cit> , and random forest  <cit>  were employed for comparison with miles-svm.
the decision tree is a greedy method based on a recursive partitioning algorithm.
the classification trees were constructed using the 'classregtree' function implemented in matlab r2011b.
the tree-based classification method can account well for multiple binding mechanisms  <cit> .
gini's diversity index was used for recursive partitioning, and the minimal number of molecules per tree leaf was set as  <dig> to terminate tree growing.
the 1-norm svm model is a statistical learning theory derived from the structural risk minimization principle and vapnik-chervonenkis  dimension  <cit> .
it is different from the tree-based method and served as an alternative comparison.
since the major drawback of dt is its low prediction caused by the overfitted tree-based structure, the ensemble learning method, random forests  <cit> , can deliver improved prediction while retaining the appealing properties of tree-based methods.
it is a collection of decision trees which are grown from bootstrapping samples of the original data without tree pruning, and has been demonstrated as one of the most powerful tools available for data exploration  <cit> .
the matlab implementation  was used with default parameters.
RESULTS
data set preparation and division
according to the criteria used to label positive and negative molecules, the number of molecules in each of two classes was balanced for four data sets.
data set i has  <dig> molecules as positive and  <dig> molecules as negative; data set ii has  <dig> molecules as positive and  <dig> molecules as negative; data set iii has  <dig> molecules as positive and  <dig> molecules as negative; and data set iv has  <dig> molecules as positive and  <dig> molecules as negative.
in terms of division of training and test sets, a stratified sampling was used to partition all four data sets into training and test sets at ratios around 3: <dig>  respectively .
conformational sampling
the molecules in different data sets had various conformational flexibilities, so the average number of conformers for each molecule was distinct for the four data sets .
the average number of conformers for each molecule was  <dig> in data set i,  <dig> in data set ii,  <dig> in data set iii, and  <dig> in data set iv.
so the molecules in data set iv had the highest conformational flexibility.
the feature space constructed through instance-based embedding only consisted of the instances from training bags, in other words, the conformers from the molecules in the training set.
the molecules in the test set were not used in the construction of the instance-based feature space.
so ntraining in table  <dig> indicates the number of instance-based features used for embedding.
n
training
a
n
test
b
m
pre-filtering
c
m
post-filtering
d
m
significant
e
*f
a the number of conformers in the training set; b the number of conformers in the test set; c the number of pharmacophore bits in the fingerprint originally enumerated; d the number of pharmacophore bits in the fingerprint after filtering; e the number of bits in the optimal subset of the pharmacophore fingerprint; f the optimal threshold value to select truly significant pharmacophore bits.
significance analysis of pharmacophore models
millions of pharmacophore models were originally enumerated for each data set, and the largest number of pharmacophore models was generated for data set iv.
this correlated with the observation that the molecules in data set iv have the highest conformational flexibility.
after occurrence-based filtering, only a small portion of the pharmacophore models was retained for each data set.
for instance, 13% was retained for data set i, 9% for both data sets ii and iii, and 1% for data set iv .
significance analysis was subsequently performed upon those retained pharmacophore models.
the threshold values were set to  <dig> equally spaced intervals from  <dig> to the largest difference between the ranking scores and reference scores.
as the threshold value increases in a bottom-up manner, the number of falsely significant pharmacophore models decreases, and the number of truly significant models remains roughly constant.
so the optimal threshold values  for each data set can be obtained when the number of falsely significant pharmacophore models drops to zero .
subsequently, the optimal subsets of the pharmacophore fingerprint bits were obtained for four data sets .
only a very small portion of the fingerprint bits were significant for classification, namely 1% in data set i, 9% in data set ii, 1% in data set iii, and 2% in data set iv.
in the context of mil, the optimal subsets of the binary strings were used to calculate the dissimilarity between two conformers for instance-based feature mapping.
for the classical qsar methods, the optimal subsets of the fingerprints were used as the 3d descriptors in the pharmacophore-based feature space for building classification models.
predictive performance of miles and classical qsar methods
in the miles model, the only tuning parameter λ was determined by a grid search.
five replications of 5-fold cross-validation were performed to assess the classification accuracies at each point over a fixed grid which ranged from 2- <dig> to  <dig> with exponential increment in base  <dig>  the median values for the  <dig> replications were used to find the optimal tuning parameters.
during the cross-validation, the instance-based feature space was dynamically defined, which means that the conformers from the molecules in the internal test set, after random split of the training set, were excluded from the feature space.
as a result, the optimal tuning parameters as well as the number of prototype conformers were obtained for four dissimilarity measures .
nb
a the median classification accuracy for  <dig> replications of 5-fold cross-validation; b the number of prototype conformers selected in the set Γ; c the model selected based on the number of prototype conformers.
based on the internal validation, the classification accuracies were similar within each data set using four different dissimilarity measures.
however, the numbers of prototype conformers selected were much different.
for instance, in data set i and ii, manhattan distance yielded the smallest subset of selected prototype conformers, but in data set iii and iv, rogers-tanimoto yielded the smallest subset.
furthermore, soergel distance yielded the largest subset for all the four data sets.
the dissimilarity measure which yielded the smallest number of selected prototype conformers was chosen as the best miles model and used later for comparison with classical qsar models without instance-based embedding.
after finding the optimal λ, a miles model was identified from the training set and applied to the test set.
in addition to comparing classification accuracy, denoted as the proportion of correct predictions, matthews correlation coefficient   <cit>  was also employed as a complementary indicator for the predictive performance.
mcc is defined as:
mcc=tp×tn-fp×fntp+fptp+fntn+fptn+fn
where tp is true positive, tn is true negative, fp is false positive, and fn is false negative.
mcc not only takes into account true positives and true negatives as classification accuracy does, but also false positives and false negatives.
thus it is considered as a balanced measure of the performance of binary classification .
a the model selected based on the number of prototype conformers.
in accordance to classification accuracy and mcc, the performance of different dissimilarity measures was dataset-specific.
for data set i, both the manhattan and rogers-tanimoto distances were top-ranked and performed equally well on the test set, whereas on the training set, the soergel and dice distances performed much better than the rogers-tanimoto and manhattan distances, and the rogers-tanimoto distance performed slightly better than the manhattan distance.
in addition, the results did not change after removing the  <dig> seeded conformers which were used for the validation of identifying bioactive conformers.
for data set ii, the manhattan distance was top-ranked on both training set and test set.
for data set iii, the dice distance was top-ranked on both training and test sets.
for data set iv, the rogers-tanimoto distance performed much better on the test set, but on the training set it was not the top-ranked dissimilarity measure.
it is interesting that for data sets i, ii, and iii the differences in the predictive performances of the four dissimilarity measures were very small, whereas for data set iv the differences were much larger.
this may be caused by the high structural diversity in data set iv.
the small difference in dissimilarity measures had a big impact on the predictive performance.
the other interesting observation was that the classification accuracy and mcc provided the same indications for the predictive performance, which means that the data sets in the present work were highly balanced and good for benchmark studies.
after comparing the predictive performance of different dissimilarity measures in the miles model, the predictive performance of miles models was compared with that of conventional classification approaches, which are based on classical qsar principles without instance-based embedding.
to find the optimal λ for 1-norm svm on the basis of classical qsar principles, the same procedure was employed, which resulted in the minimal subset of the most important pharmacophore models .
nb
a the median classification accuracy for  <dig> replications of 5-fold cross-validation; b the number of important pharmacophore bits.
for data set i, the 1-norm svm without instance-based embedding overfit the training set, producing perfect prediction on the training set and poor prediction on the test set.
however, miles performed fairly well on both the training and test sets without overfitting.
miles performed much better than decision trees and slightly worse than random forests in terms of the predictive power on the test set.
for data set ii, miles was highly competitive with the other classical qsar methods, yielding the second best prediction on both training and test sets, while 1-norm svm without embedding provided the best prediction on the training set but suffered from overfitting and decision trees produced the best prediction on the test set.
for data set iii, miles performed slightly worse than random forests, but better than the other two methods, based on the predictions on the test set.
although miles using dice distance was not selected, since it yielded a large number of selected prototype conformers, it performed equally as well as random forests on the test set.
for data set iv, miles significantly outperformed the other approaches based on the predictions on the test set.
for all the data sets, 1-norm svm without embedding overfit the training set, yielding the best predictions on the training sets and relatively low predictions on the test sets.
however, after instance-based embedding, miles performed fairly well on both training and test sets without overfitting, and its predictive power was highly comparable with other conventional qsar approaches .
it was interesting that the classification accuracy and mcc provided the same indications again, even for the comparison of different qsar approaches.
a manhattan dissimilarity measure; b rogers-tanimoto dissimilarity measure.
identification of bioactive conformers
after examining the predictive ability of miles, we tested the ability of miles in the pursuit of the bioactive conformers.
due to the lack of experimental data, the validation can only be made for the molecules in data set i. we made use of  <dig> co-crystallized structures of gsk- <dig> with bound small molecules, which adopt bioactive conformers in the complex structures .
see additional file  <dig> for the chemical structures of  <dig> small molecules.
the direct comparison between the structures of the co-crystallized conformers and the ones from conformational sampling is difficult and sometimes impossible, since the conformational sampling plus structural minimization may not provide the exact same conformations found in the co-crystallized complex, due to the lack of protein environment in the conformational search process.
so we adopted an indirect validation method.
we seeded the  <dig> co-crystallized conformers in the set of sampled conformers generated through extensive exploration of conformational space.
then we calculated their contributions fcij* to the classification of the relevant positive molecules as described above .
n
i
f
a molecule index in the data set; b molecular name in the data set; c protein data bank index for the protein structure from which the experimental conformer was extracted; d contribution fcij* calculated using equation 6; e the rank in the set of contributions; f the number of conformers for each molecule; g the rank cannot be determined and the conformer was predicted to be irrelevant to classification based on the miles method.
three out of  <dig> molecules are highly flexible, adopting more than  <dig> conformers.
for these three, miles only correctly predicted one co-crystallized conformer as the third most significant conformer contributing to the classification of the molecule named ar.
it incorrectly predicted the other two co-crystallized conformers as irrelevant conformers in terms of the contribution to the classification of benzoimidazole- <dig> and maleimide.
but for the molecules adopting less than  <dig> conformers, which had relatively rigid structures, miles correctly predicted all the co-crystallized conformers as significant conformers for the classification of positive molecules.
five co-crystallized conformers were predicted to be the most significant conformers, i.e., the bioactive conformers; three co-crystallized conformers were predicted to be the second most significant conformers; and one co-crystallized conformer was predicted to be the sixth most significant conformer, based on the calculations of fcij*.
so the pursuit of bioactive conformers is easy for relatively rigid molecules and relatively more difficult for the highly flexible ones.
CONCLUSIONS
we have successfully implemented a multiple-instance learning  framework, multiple-instance learning via embedded instance selection , for drug activity prediction.
the molecules and relevant conformers were described using superior 3d descriptors, pharmacophore fingerprints, encoded as binary strings.
the instance-based embedding was accomplished using dissimilarity measures designed for calculations on binary strings.
the joint feature selection and classification was accomplished using a wrapper model based on 1-norm svm.
we have used the approach for the prediction of the labels of molecules interacting with four therapeutic targets, including gsk- <dig>  cbrs, and p-gp.
based on the predictive performance, our proposed approach was highly competitive with conventional classification approaches based on classical qsar principle.
however, the proposed method, unlike conventional classification approaches, can also predict the contributions of individual conformers for each molecule and further can identify the putative bioactive conformer.
these unique characteristics make the proposed method very useful for the pursuit of biologically significant conformers.
finally, we have validated that the proposed approach is highly useful in the pursuit of bioactive conformers.
list of abbreviations used
mil: multiple-instance learning; miles: multiple-instance learning via embedded instance selection; svm: support vector machine; qsar: quantitative structure-activity relationship; gsk-3: glycogen synthase kinase-3; gpcr: g protein-coupled receptor; p-gp: p-glycoprotein; som: self-organizing map; mcc: mathews correlation coefficient.
competing interests
the authors declare that they have no competing interests.
authors' contributions
gf, yc, dew, and rjd planned the research.
gf prepared the gsk <dig> and p-gp data sets.
hl, ryp and prd prepared the cb data sets and used preliminary machine learning methods for classification of cb compounds.
gf prepared the computer code and ran the calculations with the assistance of xn.
gf, yc, dew, and rjd analyzed the results.
gf wrote the manuscript with assistance from yc and rjd.
all authors carefully reviewed the manuscript before submission.
supplementary material
additional file 1
this file contains the chemical structures of  <dig> co-crystallized molecules  in pdb database, associated with the id number, names, and pdb id.
click here for file
acknowledgements
this material is based on work supported by the national science foundation under grant no.
nsf eps- <dig> and the national institutes of health  ncrr grant number 5p20rr <dig> and c <dig> rr-14503- <dig>  the content is solely the responsibility of the authors and does not necessarily represent the official views of ncrr or nih.
this article has been published as part of bmc bioinformatics volume  <dig> supplement  <dig>  2012: proceedings of the ninth annual mcbios conference.
dealing with the omics data deluge.
the full contents of the supplement are available online at http://www.biomedcentral.com/bmcbioinformatics/supplements/13/s15

 in the context of drug discovery research, it is challenging but of great importance to be able to determine which 3-dimensional shapes of a given molecule are responsible for its observed biological activity. due to structural flexibility, a molecule may adopt a wide range of conformers and the identification of the bioactive conformers is extremely important in order to understand the recognition mechanism between small molecules and proteins, which is crucial in drug discovery and development. until now, the most reliable approach to obtain the bioactive conformer is to use the x-ray crystal structure of a ligand-protein complex; however, the number of such structures is limited because of the experimental difficulty in obtaining the crystals, especially for transmembrane proteins, such as g protein-coupled receptors and membrane transporters. we were interested to apply to this problem a machine-learning approach which does not require crystal structures, named multiple-instance learning via embedded instance selection. miles has been demonstrated as an efficient and accurate approach to solve different multiple-instance problems, in particular, to predict drug activity using musk data sets. in the context of drug activity prediction, miles enables the construction of a quantitative structure-activity relationship model, and subsequently the identification of bioactive conformers. mil is a variant of supervised learning, and it has been applied for a variety of learning problems including drug activity prediction, image database retrieval, text categorization, and natural scene classification. in the context of drug activity prediction, the observed biological activity is associated with a single molecule without knowing which conformer or conformers are responsible. furthermore, a molecule is biologically active if and only if at least one of its conformers is responsible for the observed bioactivity; and the molecule is inactive if none of its conformers is responsible. a difficulty in implementation arises from the fact that different molecules have a different number of conformers, since some molecules having multiple rotatable bonds are highly flexible and others with rigid structures only have a small numbers of conformers. the overall strategy for structural and data mining using miles is summarized here. first of all, a complete sampling of conformational space provides a large number of conformers for each molecule. the molecules are themselves each already labelled as either positive or negative. however, the labels for the conformers are unavailable during the model generation. each conformer is denoted by a unique pharmacophore fingerprint which is a superior feature-based 3d descriptor unveiling structural similarity and diversity. the pharmacophore fingerprint is encoded into a binary string which indicates the presence or absence of a match to individual pharmacophore models. since the exhaustively enumerated fingerprints have millions of bits, which may be beyond computational limits, a significance analysis of pharmacophore models is employed to determine the optimal subset of bits of the fingerprint. subsequently, miles converts the mil to a standard supervised learning problem by embedding bags into an instance-based feature space via structural dissimilarity measures. finally, 1-norm svm is applied to select the most important features, identifying the highly significant conformers which help the most to distinguish active and inactive molecules, and, simultaneously, to construct a predictive classification model. in the present work, miles has been applied to study the biological activities of several sets of molecules interacting with different receptor targets including glycogen synthase kinase-, cannabinoid receptors, and p-glycoprotein. all of these receptors have been emerging as increasingly important therapeutic targets. gsk- is a multifunctional serine/threonine protein kinase involved in the regulation of a wide range of cellular functions, including glucose metabolism, neuronal processes, chronic inflammation, cell proliferation and apoptosis. cbrs are a class of gpcrs and have been targeted for various disease conditions such as obesity, drug abuse disorders, inflammatory diseases, anorexia and vomiting. p-gp, a membrane transporter, is responsible for drug efflux and multidrug resistance, especially to cancer drugs. except for gsk- the other proteins are membrane-associated and there is no available crystal structure for them. the identification of bioactive conformers for the molecules targeting membrane-associated proteins using miles could be highly informative and desirable. identified conformers can be used in various drug discovery approaches such as scaffold hopping, target fishing, and 3d structural alignment for 3d quantitative structure-activity relationship studies. based on our calculations, miles is highly competitive with the classical qsar approaches which do not include instance-based feature mapping in terms of predictive abilities. meanwhile, we have validated that miles has the ability to identify a subset of highly relevant conformers, including the bioactive conformers, which contribute to the classification of active and inactive molecules. methods data set preparation four different data sets were compiled through extensive literature search. data set i includes all molecules exhibiting inhibitory activities for human gsk- data sets ii and iii contain molecules modulating the intracellular activities of human cbrs. since there are two identified cbr subtypes, cb and cb two different data sets were prepared to study the protein-small molecule interactions of the receptors separately. some of the molecules which have reported binding affinities for both cb subtypes were included in both data sets ii and iii. data set iv contained compounds which had been tested as substrates of p-gp. the molecules collected for each data set were labelled as either positive or negative. a positive molecule has a high binding affinity with the target protein, whereas a negative molecule has a low binding affinity. a single cutoff value has been widely used in the development of classification models. however, it is inaccurate to use a single cutoff value for the separation of continuous biological activities in the context of drug activity prediction. the biological activities are represented by continuous numbers, and the small differences between the values above and below the cutoff value cannot imply the distinct nature of binding affinity. furthermore, the small difference in the bioassay results may arise from systematic errors introduced by different experimental protocols used in different labs, so it cannot be used as solid evidence for the classification of molecules. therefore, multiple cutoff values were employed to separate molecules into positive and negative classes. for data set i, the molecules were categorized into positive and negative molecules using cutoff values of ic ≤ nm and ic ≥ nm, respectively. the molecules having inhibitory activities between the two cutoff values were considered as moderately active molecules, and were discarded from the data set. the wide margin between the two cutoff values was used to account for the variances in biological assays. for data set ii and iii, the molecules were classified as positive if the ki ≤ nm or ic ≤ nm or ec ≤ nm; and the molecules were classified as negative if the ki ≥ nm or ic ≥ nm or ec ≥ nm. the labels for the molecules in data set iv indicated whether or not the molecule is a substrate for the target protein. they were obtained from the literature. division of training and test set external validation was achieved using an independent test set. the split of the data set into training and test sets was carried out using kohonen self-organizing maps in canvas from schrödinger suite the som is trained using unsupervised learning to produce a square 2d grid map from the high dimensional input space. each grid cell contains a cluster of structurally similar molecules defined by the input vectors. the som takes advantage of clustering capabilities so that the selected training set can represent the independent test set in terms of the input space and chemical domains. molecular pharmacophore fingerprints were used to describe the relevant structural information of the molecules and were used as input variables to build the som. the grid size of the map depends on the number of molecules in the data set. for data sets i, ii, and iii, the kohonen maps built included × neurons and epochs. for the data set iv, a kohonen map consisting of × neurons and epochs was built. the molecules were then stratified and sampled from each neuron to select the training and test set molecules. preprocessing and conformational sampling the molecules can be represented by mi, i = ⋯, l where l is the total number of molecules. the 3d molecular structures were generated using the ligprep module from schrödinger suite and then subjected to preprocessing to enumerate all the possible tautomers. the protonation states of ionizable groups were set to match ph =, and the stereochemistry was retained from the original 3d structures. in order to explore the conformational space exhaustively, the mixed torsional/low mode sampling method was employed, using macromodel from schrödinger suite the torsional sampling involves multiple monte carlo minimum searches for global exploration, and the low mode conformational search allows for automatic local exploration. the torsional increment for each rotatable bond was set to 15° and the maximum number of total steps for torsional sampling was. the energy window for saving structures was set to kj/mol. the small torsional increment and wide energy window were employed to provide a reasonable coverage of the conformational space. each enumerated conformer was energy minimized to eliminate unreasonable geometries and reduce internal steric clashes, using the polak-ribière conjugate gradient method with a gradient convergence threshold of and a maximum of iterations. to remove redundant conformations, the maximum atom deviation cutoff was set to Å. as a result, each molecule mi has several possible conformers cij, j = ⋯, ni, where ni is the number of conformers for molecule i. in order to validate that miles can identify the bioactive conformers, we seeded co-crystallized conformers, one for each of molecules, in the set of sampled conformers for data set i. the validation process will be described in the following sections. generation of pharmacophore fingerprints the pharmacophore fingerprint as a measure of molecular similarity and diversity based on 3d pharmacophoric shape was enumerated using canvas from schrödinger suite each pharmacophore fingerprint associated with a unique conformer can be represented by a binary string, such as pij = {p ⋯, pk, ⋯, pm} and encodes quantitative structural information for conformer cij, where each bit value pk, k = ⋯, m indicates the presence or absence of a match to a single pharmacophore model, representing a unique 3d arrangement of a number of pharmacophore features. if the conformer fits the pharmacophore model for a particular k, in other words if the functional groups of the conformer fully overlap on all the pharmacophore features in the model, pk equals 1; otherwise, pk equals as a result, each conformer is associated with a unique pharmacophore fingerprint as a conformational signature, which enables us to describe quantitatively the 3d structural information. the pharmacophore features employed in the models consist of hydrogen bond donor, hydrogen bond acceptor, hydrophobic group, negatively charged group, positively charged group, and aromatic ring. in the present study, only four-feature based models were employed in order to allow a reasonable description of 3d orientation of the structures and retain information about molecular chirality, which is lost in three-feature based models. different combinations of four out of six pharmacophore features were exhaustively enumerated and inter-feature distances were varied from Å to Å to form the different pharmacophore models. each pharmacophore feature was treated as a bin with width Å, and the bin overlap threshold was Å. to fit to a model the conformer must fit to each of the four features in the model. the maximum distance between pharmacophore features was set to Å in order to be able to cover the largest molecular structures in the databases. the originally enumerated fingerprints were subject to occurrence-based filtering to remove the pharmacophore models present in less than 5% of the total number of molecules, since the pharmacophore models with a very low occurrence are not useful for discriminating between positive and negative classes. significance analysis of pharmacophore models the post-filtered pharmacophore fingerprints still have too many bits that lack information content, as indicated by too many'0' values. therefore a nonparametric supervised learning approach, motivated by the significance analysis of microarrays algorithm proposed by tibshirani et al., was applied to elucidate a consistent pattern from the numerous bits of pharmacophore fingerprints. the detailed implementation and customization of the relevant procedures has been described in. the ranking score for each pharmacophore model was computed based on a two-class t-statistic, which calculates the ratio of the difference of occurrences of that model in positive and negative classes and compares to the standard deviation of occurrence measures. pharmacophore models with ranking scores greater than a threshold have statistical significance, where the threshold was computed at the 90th percentile among random permutations of the class labels across all the molecules. in order to distinguish truly significant and falsely significant pharmacophore models, that ranking score serving as a true score was then compared with a reference score computed from the same set of random permutations. if the difference between the true score and the reference score exceeds a cutoff threshold then the pharmacophore model is truly significant; otherwise it is falsely significant. instance-based feature mapping miles provides a framework to convert a mil problem to a standard supervised learning problem via instance-based embedding. all the conformers belong to the instance-based feature space. for convenience, all conformers in all molecules were lined up together, and were re-indexed in the embedded feature space as cr, r = ⋯, n where n= ∑i=1lni. instance-based feature mapping can be accomplished using calculated structural dissimilarities. different binary string distance measures were tested, including the soergel distance, dice distance, manhattan distance, and rogers-tanimoto distance. the range of each dissimilarity measure was normalized to be by definition. given a conformer cij denoted by a binary string pij, the dissimilarity measure, denoted as d, is calculated based on the number of occurrences of bit matches. since one molecule is defined as a bag of multiple conformers, the dissimilarity measure for a molecule, denoted as d, is calculated based on the minimum distance using the closest instance in the bag for mi: a a let p and p be two pharmacophore fingerprints, a be the count of bits which are set to in both p and p b be the count of bits which are set to in p but not in p c be the count of bits which are set to in p but not in p and d be the count of bits which are set to in both p and p so a is called the number of total matches, b and c are called the number of single matches, and d is called the number of no matches. dmi,cr=minjdcij,cr the minimum distance calculation extends the idea of the diverse density framework proposed for instance-based learning. joint feature selection and classification since the molecules in the training sets are highly flexible, instance-based embedding, which provides a framework to convert a mil problem to a traditional supervised learning problem, may produce a very high dimensional feature space. but many features are redundant or irrelevant, and do not play an important role in the classification of molecules as positive or negative. so an efficient feature selection model is required for selection of an optimal subset of instance-based features. considering its excellent performance in many applications, the 1-norm svm method was chosen as a joint approach to construct classifiers and to select important features simultaneously. the prediction model can be formulated as a linear classifier, y=signωtm+b where y denotes the class label as either positive or negative; ω and b are model parameters which are optimized during model generation; and m corresponds to a molecule, which is defined by an n-dimensional vector of dissimilarities calculated using, i.e., dissimilarities with respect to all conformers in all molecules. the domain to is therefore the space of rn, where n is the sum of all conformers in all molecules. the svm approach constructs classifiers based on hyperplanes by minimizing a regularized training error, ξtraining, λp•+ξtraining where p is a regularizer, and λ is the regularization parameter, the only tuning parameter to be optimized by the user. in 1-norm svm, the regularizer is chosen to be the 1-norm of the weight vector, ω1= ∑rωr. 1-norm regularization favors sparse solutions, i.e., it drives many components of ω to zero. once the optimal solution, with values ω* and b*, is obtained, the magnitude of its component ωr* indicates the significance of the r-th feature in the instance-based feature space. the features corresponding to non-zero entries in ω* are selected as important features, which are given as a set Γ=r:ωr*>0). they are needed for the classification problem of interest y=sign∑r∈Γωr*dmi,cr+b*. note that is equivalent to where all weights with values are ignored. the domain of is r|Γ|, a subspace of rn, defined by conformers whose weights are nonzero. the features selected as important are called prototype conformers. the plus or minus sign of ωr* indicates the positive or negative contribution, respectively, of the r-th prototype conformer to the putative bioactive conformers for each individual molecule. our formulation of miles works directly on a dissimilarity mapping, which is different from a similarity mapping described by chen, et al.. one can transform a dissimilarity mapping to a similarity mapping via an exponential function. however, this would introduce an additional super parameter, σ. although, a proper choice of σ could improve the performance of a model, the selection of a proper value for σ increases the computational cost significantly. hence we use a dissimilarity mapping to reduce the computational cost. identification of bioactive conformers one appealing advantage of the miles algorithm is that it can identify the most significant instances in a bag according to their contributions to the classification of that bag. in the context of drug activity prediction, we can identify the most significant conformers, called the bioactive conformers, for each molecule. the putative bioactive conformers are the conformers that contributed the most to the classification of positive and negative molecules. the identification of bioactive conformers can be accomplished with the assistance of the prototype conformers mentioned above. given a molecule mi with its conformers cij, j = ⋯, ni, we define an index set ∑ = {j*: j* = argminj d, r ∈ Γ}), which includes the index for conformers closest to each prototype conformer. hence, Σ defines a minimal set of conformers, called significant conformers, which are responsible for the classification of mi. by definition, each prototype conformer in set Γ has a single conformer in set Σ closest to it, but each significant conformer in set Σ may have multiple prototype conformers in set Γ closest to it. so we need to define an index set for each significant conformer in set Σ that includes the index for the prototype conformers closest to it, which is given as Γj*=r:r∈Γ,j*=argminjdcij,cr). as a result, the contribution of each significant conformer to the classification of molecule can be calculated as fcij*= ∑r∈Γj*ωr*dcij*,cr wherefcij* denotes the contribution of the conformer cij* to the classification of the molecule mi. the conformer in set Σ making the highest contribution is selected as a bioactive conformer. in order to validate the ability of miles to identify the bioactive conformers, the contributions fcij* for the seeded conformers, which were taken directly from co-crystallized complex structures, were calculated and ranked among all the conformers sampled for those molecules. classical qsar methods without instance-based embedding in order to examine the predictive performance of miles, conventional classification approaches based on classical qsar principles without instance-based embedding were tested for comparison. since one molecule is defined as a bag of multiple conformers, the pharmacophore fingerprint associated with a single molecule was obtained from the binary union of all of the pharmacophore fingerprints associated with the conformers of that molecule. the same occurrence-based filtering and significance analysis of pharmacophore fingerprints were performed to select the optimal subsets of the fingerprints which constituted the feature space for the classical qsar studies. three widely used classification algorithms including decision tree, 1-norm svm, and random forest were employed for comparison with miles-svm. the decision tree is a greedy method based on a recursive partitioning algorithm. the classification trees were constructed using the'classregtree' function implemented in matlab r2011b. the tree-based classification method can account well for multiple binding mechanisms. gini's diversity index was used for recursive partitioning, and the minimal number of molecules per tree leaf was set as to terminate tree growing. the 1-norm svm model is a statistical learning theory derived from the structural risk minimization principle and vapnik-chervonenkis dimension. it is different from the tree-based method and served as an alternative comparison. since the major drawback of dt is its low prediction caused by the overfitted tree-based structure, the ensemble learning method, random forests, can deliver improved prediction while retaining the appealing properties of tree-based methods. it is a collection of decision trees which are grown from bootstrapping samples of the original data without tree pruning, and has been demonstrated as one of the most powerful tools available for data exploration. the matlab implementation was used with default parameters.  data set preparation and division according to the criteria used to label positive and negative molecules, the number of molecules in each of two classes was balanced for four data sets. data set i has molecules as positive and molecules as negative; data set ii has molecules as positive and molecules as negative; data set iii has molecules as positive and molecules as negative; and data set iv has molecules as positive and molecules as negative. in terms of division of training and test sets, a stratified sampling was used to partition all four data sets into training and test sets at ratios around 3: respectively. conformational sampling the molecules in different data sets had various conformational flexibilities, so the average number of conformers for each molecule was distinct for the four data sets. the average number of conformers for each molecule was in data set i, in data set ii, in data set iii, and in data set iv. so the molecules in data set iv had the highest conformational flexibility. the feature space constructed through instance-based embedding only consisted of the instances from training bags, in other words, the conformers from the molecules in the training set. the molecules in the test set were not used in the construction of the instance-based feature space. so ntraining in table indicates the number of instance-based features used for embedding. n training a n test b m pre-filtering c m post-filtering d m significant e *f a the number of conformers in the training set; b the number of conformers in the test set; c the number of pharmacophore bits in the fingerprint originally enumerated; d the number of pharmacophore bits in the fingerprint after filtering; e the number of bits in the optimal subset of the pharmacophore fingerprint; f the optimal threshold value to select truly significant pharmacophore bits. significance analysis of pharmacophore models millions of pharmacophore models were originally enumerated for each data set, and the largest number of pharmacophore models was generated for data set iv. this correlated with the observation that the molecules in data set iv have the highest conformational flexibility. after occurrence-based filtering, only a small portion of the pharmacophore models was retained for each data set. for instance, 13% was retained for data set i, 9% for both data sets ii and iii, and 1% for data set iv. significance analysis was subsequently performed upon those retained pharmacophore models. the threshold values were set to equally spaced intervals from to the largest difference between the ranking scores and reference scores. as the threshold value increases in a bottom-up manner, the number of falsely significant pharmacophore models decreases, and the number of truly significant models remains roughly constant. so the optimal threshold values for each data set can be obtained when the number of falsely significant pharmacophore models drops to zero. subsequently, the optimal subsets of the pharmacophore fingerprint bits were obtained for four data sets. only a very small portion of the fingerprint bits were significant for classification, namely 1% in data set i, 9% in data set ii, 1% in data set iii, and 2% in data set iv. in the context of mil, the optimal subsets of the binary strings were used to calculate the dissimilarity between two conformers for instance-based feature mapping. for the classical qsar methods, the optimal subsets of the fingerprints were used as the 3d descriptors in the pharmacophore-based feature space for building classification models. predictive performance of miles and classical qsar methods in the miles model, the only tuning parameter λ was determined by a grid search. five replications of 5-fold cross-validation were performed to assess the classification accuracies at each point over a fixed grid which ranged from 2- to with exponential increment in base the median values for the replications were used to find the optimal tuning parameters. during the cross-validation, the instance-based feature space was dynamically defined, which means that the conformers from the molecules in the internal test set, after random split of the training set, were excluded from the feature space. as a result, the optimal tuning parameters as well as the number of prototype conformers were obtained for four dissimilarity measures. nb a the median classification accuracy for replications of 5-fold cross-validation; b the number of prototype conformers selected in the set Γ; c the model selected based on the number of prototype conformers. based on the internal validation, the classification accuracies were similar within each data set using four different dissimilarity measures. however, the numbers of prototype conformers selected were much different. for instance, in data set i and ii, manhattan distance yielded the smallest subset of selected prototype conformers, but in data set iii and iv, rogers-tanimoto yielded the smallest subset. furthermore, soergel distance yielded the largest subset for all the four data sets. the dissimilarity measure which yielded the smallest number of selected prototype conformers was chosen as the best miles model and used later for comparison with classical qsar models without instance-based embedding. after finding the optimal λ, a miles model was identified from the training set and applied to the test set. in addition to comparing classification accuracy, denoted as the proportion of correct predictions, matthews correlation coefficient was also employed as a complementary indicator for the predictive performance. mcc is defined as: mcc=tp×tn-fp×fntp+fptp+fntn+fptn+fn where tp is true positive, tn is true negative, fp is false positive, and fn is false negative. mcc not only takes into account true positives and true negatives as classification accuracy does, but also false positives and false negatives. thus it is considered as a balanced measure of the performance of binary classification. a the model selected based on the number of prototype conformers. in accordance to classification accuracy and mcc, the performance of different dissimilarity measures was dataset-specific. for data set i, both the manhattan and rogers-tanimoto distances were top-ranked and performed equally well on the test set, whereas on the training set, the soergel and dice distances performed much better than the rogers-tanimoto and manhattan distances, and the rogers-tanimoto distance performed slightly better than the manhattan distance. in addition, the results did not change after removing the seeded conformers which were used for the validation of identifying bioactive conformers. for data set ii, the manhattan distance was top-ranked on both training set and test set. for data set iii, the dice distance was top-ranked on both training and test sets. for data set iv, the rogers-tanimoto distance performed much better on the test set, but on the training set it was not the top-ranked dissimilarity measure. it is interesting that for data sets i, ii, and iii the differences in the predictive performances of the four dissimilarity measures were very small, whereas for data set iv the differences were much larger. this may be caused by the high structural diversity in data set iv. the small difference in dissimilarity measures had a big impact on the predictive performance. the other interesting observation was that the classification accuracy and mcc provided the same indications for the predictive performance, which means that the data sets in the present work were highly balanced and good for benchmark studies. after comparing the predictive performance of different dissimilarity measures in the miles model, the predictive performance of miles models was compared with that of conventional classification approaches, which are based on classical qsar principles without instance-based embedding. to find the optimal λ for 1-norm svm on the basis of classical qsar principles, the same procedure was employed, which resulted in the minimal subset of the most important pharmacophore models. nb a the median classification accuracy for replications of 5-fold cross-validation; b the number of important pharmacophore bits. for data set i, the 1-norm svm without instance-based embedding overfit the training set, producing perfect prediction on the training set and poor prediction on the test set. however, miles performed fairly well on both the training and test sets without overfitting. miles performed much better than decision trees and slightly worse than random forests in terms of the predictive power on the test set. for data set ii, miles was highly competitive with the other classical qsar methods, yielding the second best prediction on both training and test sets, while 1-norm svm without embedding provided the best prediction on the training set but suffered from overfitting and decision trees produced the best prediction on the test set. for data set iii, miles performed slightly worse than random forests, but better than the other two methods, based on the predictions on the test set. although miles using dice distance was not selected, since it yielded a large number of selected prototype conformers, it performed equally as well as random forests on the test set. for data set iv, miles significantly outperformed the other approaches based on the predictions on the test set. for all the data sets, 1-norm svm without embedding overfit the training set, yielding the best predictions on the training sets and relatively low predictions on the test sets. however, after instance-based embedding, miles performed fairly well on both training and test sets without overfitting, and its predictive power was highly comparable with other conventional qsar approaches. it was interesting that the classification accuracy and mcc provided the same indications again, even for the comparison of different qsar approaches. a manhattan dissimilarity measure; b rogers-tanimoto dissimilarity measure. identification of bioactive conformers after examining the predictive ability of miles, we tested the ability of miles in the pursuit of the bioactive conformers. due to the lack of experimental data, the validation can only be made for the molecules in data set i. we made use of co-crystallized structures of gsk- with bound small molecules, which adopt bioactive conformers in the complex structures. see additional file for the chemical structures of small molecules. the direct comparison between the structures of the co-crystallized conformers and the ones from conformational sampling is difficult and sometimes impossible, since the conformational sampling plus structural minimization may not provide the exact same conformations found in the co-crystallized complex, due to the lack of protein environment in the conformational search process. so we adopted an indirect validation method. we seeded the co-crystallized conformers in the set of sampled conformers generated through extensive exploration of conformational space. then we calculated their contributions fcij* to the classification of the relevant positive molecules as described above. n i f a molecule index in the data set; b molecular name in the data set; c protein data bank index for the protein structure from which the experimental conformer was extracted; d contribution fcij* calculated using equation 6; e the rank in the set of contributions; f the number of conformers for each molecule; g the rank cannot be determined and the conformer was predicted to be irrelevant to classification based on the miles method. three out of molecules are highly flexible, adopting more than conformers. for these three, miles only correctly predicted one co-crystallized conformer as the third most significant conformer contributing to the classification of the molecule named ar. it incorrectly predicted the other two co-crystallized conformers as irrelevant conformers in terms of the contribution to the classification of benzoimidazole- and maleimide. but for the molecules adopting less than conformers, which had relatively rigid structures, miles correctly predicted all the co-crystallized conformers as significant conformers for the classification of positive molecules. five co-crystallized conformers were predicted to be the most significant conformers, i.e., the bioactive conformers; three co-crystallized conformers were predicted to be the second most significant conformers; and one co-crystallized conformer was predicted to be the sixth most significant conformer, based on the calculations of fcij*. so the pursuit of bioactive conformers is easy for relatively rigid molecules and relatively more difficult for the highly flexible ones.  we have successfully implemented a multiple-instance learning framework, multiple-instance learning via embedded instance selection, for drug activity prediction. the molecules and relevant conformers were described using superior 3d descriptors, pharmacophore fingerprints, encoded as binary strings. the instance-based embedding was accomplished using dissimilarity measures designed for calculations on binary strings. the joint feature selection and classification was accomplished using a wrapper model based on 1-norm svm. we have used the approach for the prediction of the labels of molecules interacting with four therapeutic targets, including gsk- cbrs, and p-gp. based on the predictive performance, our proposed approach was highly competitive with conventional classification approaches based on classical qsar principle. however, the proposed method, unlike conventional classification approaches, can also predict the contributions of individual conformers for each molecule and further can identify the putative bioactive conformer. these unique characteristics make the proposed method very useful for the pursuit of biologically significant conformers. finally, we have validated that the proposed approach is highly useful in the pursuit of bioactive conformers. list of abbreviations used mil: multiple-instance learning; miles: multiple-instance learning via embedded instance selection; svm: support vector machine; qsar: quantitative structure-activity relationship; gsk-3: glycogen synthase kinase-3; gpcr: g protein-coupled receptor; p-gp: p-glycoprotein; som: self-organizing map; mcc: mathews correlation coefficient. competing interests the authors declare that they have no competing interests. authors' contributions gf, yc, dew, and rjd planned the research. gf prepared the gsk and p-gp data sets. hl, ryp and prd prepared the cb data sets and used preliminary machine learning methods for classification of cb compounds. gf prepared the computer code and ran the calculations with the assistance of xn. gf, yc, dew, and rjd analyzed the results. gf wrote the manuscript with assistance from yc and rjd. all authors carefully reviewed the manuscript before submission. supplementary material additional file 1 this file contains the chemical structures of co-crystallized molecules in pdb database, associated with the id number, names, and pdb id. click here for file acknowledgements this material is based on work supported by the national science foundation under grant no. nsf eps- and the national institutes of health ncrr grant number 5p20rr and c rr-14503- the content is solely the responsibility of the authors and does not necessarily represent the official views of ncrr or nih. this article has been published as part of bmc bioinformatics volume supplement 2012: proceedings of the ninth annual mcbios conference. dealing with the omics data deluge. the full contents of the supplement are available online at http://www.biomedcentral.com/bmcbioinformatics/supplements/13/s15
17- february proceedings of the ninth annual mcbios conference. we encoded the 3-dimensional structures using pharmacophore fingerprints which are binary strings, and accomplished instance-based embedding using calculated dissimilarity distances. in this work we aimed to predict bioactive conformers using a variant of supervised learning, named multiple-instance learning. the goal of the present project is to implement multiple-instance learning in drug activity prediction, and subsequently to identify the bioactive conformers for each molecule. to validate the ability of the proposed approach to find bioactive conformers, small molecules with co-crystallized structures were seeded in one data set. the approach was also validated as a useful method for pursuit of bioactive conformers. the proposed approach was proven not to suffer from overfitting and to be highly competitive with classical predictive models, so it is very powerful for drug activity prediction. 1-norm svm was used for joint feature selection and classification. the predictive abilities of the proposed approach were compared with three classical predictive models without instance-based embedding. in the context of drug discovery and development, much effort has been exerted to determine which conformers of a given molecule are responsible for the observed biological activity. out of co-crystallized structures were indeed identified as significant conformers using the proposed approach. four dissimilarity measures were employed and their performances were compared. the approach was applied to four data sets, and the best proposed model for each data set was determined by using the dissimilarity measure yielding the smallest number of selected features.
 in the context of drug discovery and development, much effort has been exerted to determine which conformers of a given molecule are responsible for the observed biological activity. in this work we aimed to predict bioactive conformers using a variant of supervised learning, named multiple-instance learning. a single molecule, treated as a bag of conformers, is biologically active if and only if at least one of its conformers, treated as an instance, is responsible for the observed bioactivity; and a molecule is inactive if none of its conformers is responsible for the observed bioactivity. the implementation requires instance-based embedding, and joint feature selection and classification. the goal of the present project is to implement multiple-instance learning in drug activity prediction, and subsequently to identify the bioactive conformers for each molecule. methods we encoded the 3-dimensional structures using pharmacophore fingerprints which are binary strings, and accomplished instance-based embedding using calculated dissimilarity distances. four dissimilarity measures were employed and their performances were compared. 1-norm svm was used for joint feature selection and classification. the approach was applied to four data sets, and the best proposed model for each data set was determined by using the dissimilarity measure yielding the smallest number of selected features.  the predictive abilities of the proposed approach were compared with three classical predictive models without instance-based embedding. the proposed approach produced the best predictive models for one data set and second best predictive models for the rest of the data sets, based on the external validations. to validate the ability of the proposed approach to find bioactive conformers, small molecules with co-crystallized structures were seeded in one data set. out of co-crystallized structures were indeed identified as significant conformers using the proposed approach.  the proposed approach was proven not to suffer from overfitting and to be highly competitive with classical predictive models, so it is very powerful for drug activity prediction. the approach was also validated as a useful method for pursuit of bioactive conformers. 17- february proceedings of the ninth annual mcbios conference. dealing with the omics data deluge oxford, ms, usa 