virtual screening ( vs ) is a valuable hit 
 discovery tool with tremendous 
 potential to improve the efficiency and reduce the costs of modern 
 high throughput screens ( hts ) . despite the increasing trend toward 
 miniaturization and greater well plate density , reagents and other 
 consumables drive up hts costs , particularly when large corporate 
 or commercial databases are screened . rationally 
 prioritizing compounds for experimental testing can reduce costs . for example , during a virtual high throughput screen , a computational 
 model is developed and applied to rank compounds for testing . when paired with high quality compound libraries , this can result in novel , structurally diverse actives from which 
 several lead series can be selected . structural diversity ultimately 
 helps circumvent adme - tox and patent liabilities that can increase 
 lead optimization costs . computational 
 virtual screening models primarily fall into two 
 classes , ligand - based and structure based , 
 or docking methods . ligand - based methods 
 predict the activity of novel compounds by assessing their similarity 
 to known actives . docking methods , on the other hand , use predicted 
 interactions between a small molecule and a target receptor to predict 
 activity . numerous benchmarking studies have reported that ligand - based 
 methods yield greater hit rates than structure - based methods . however , a reliance on chemical 
 similarity may limit their ability to identify novel chemical matter . in contrast , the diversity of actives determined using docking methods 
 is only constrained by the shape of the receptor - binding pocket . in 
 principal , docking can enable the discovery of actives more novel 
 and diverse than ligand - based methods . consistently , numerous successful 
 examples of docking in early stage discovery can be found in the literature . despite these successes , docking has traditionally been to 
 a single 
 static representation of the target . a drug target is highly dynamic , and two notable 
 models have been advanced that suggest a tight coupling between protein 
 motion and small molecule binding . in 1958 , koshland proposed the 
 induced fit model , which suggests that ligand binding induces a conformational 
 change of the protein that enhances its affinity for the ligand . conformational selection is a more recent explanation 
 of small molecule binding that incorporates energy landscape theory . it proposes that binding stabilizes one of many 
 preexisting conformers of the unbound target . both models imply that the collection of low - energy receptor conformers 
 defining the bound state depend upon ligand identity ; by extension , 
 successful docking requires the receptor to be in , or at least near , 
 the appropriate ligand - dependent bound state . ensemble docking , in 
 which each ligand is docked to a set of receptor conformers , was introduced 
 in an effort to address this requirement . there are a variety of means to generate structures for ensemble 
 docking , including crystallography and 
 nmr techniques . however , while experimental 
 methods have shown promise , the materials , time , and expertise required 
 to determine multiple , high quality structures is a significant bottleneck . 
 in contrast , molecular dynamics ( md ) simulations offer a relatively 
 inexpensive alternative to generate diverse , realistic conformational 
 states . this is largely the result of the recent implementation of 
 md codes on commodity graphical processor units ( gpus ) and the dramatic speedup of simulation benchmarks . regardless 
 of whether structures are generated by experiment or 
 simulation , for ensemble docking to be successful , a subset of conformations 
 likely to offer the best vs performance must be identified . though 
 several studies have provided hints , others have been unable 
 to determine a meaningful relationship between observable receptor 
 characteristics and virtual screening performance . even with insights from a growing body of careful studies , it remains 
 difficult or impossible to know a priori which receptor 
 conformations will result in an ensemble with virtual screening utility . the difficulties of selecting effective virtual screening conformations 
 are compounded by the combinatorial nature of the ensemble selection 
 process . when the number of receptor conformations is large , the problem 
 results in a significant number of possibilities , and it can be difficult 
 or impossible to know which of these ensembles will produce the best 
 virtual screening performance . though systematic training and 
 data - fusion methods exist that address 
 similar issues in ligand - based vs , there is a relative paucity of 
 knowledge - based structural selection methods . despite this , other 
 knowledge - based ensemble selection methods have been described in 
 the literature . for example , yoon and welsh proposed an ensemble docking method in which ensemble members are 
 selected to maximize the correlation between the experimental and 
 predicted binding affinities . the combinatorial problem was addressed 
 by assigning each compound an ensemble score that consisted of a linear 
 combination of score weights to each receptor conformation using a 
 monte carlo scheme . using estrogen receptor , they demonstrated 
 that the approach leads to more accurate classification than docking 
 to the crystal structure alone . while yoon s and welsh s 
 method can produce stronger 
 correlation with experimental binding affinities and result in enhanced 
 vs performance , experimental binding measurements are required . this 
 precludes the use of single - point hts data and limits the method to 
 compounds whose binding affinities have been measured or to those 
 with dose  response curves , from which binding affinities may 
 be inferred . rather than optimizing the correlation with experimental 
 binding 
 affinities , selecting ensembles to maximize the value of a binary 
 classification metric offers greater flexibility . since binary classification 
 is categorical , once an appropriate activity threshold has been determined , 
 any assay that delivers an activity measurement can be used . this 
 opens the door to the use of single - point data , which is less expensive 
 to determine and typically can be found in greater abundance than 
 careful binding affinity measurements . for example , following 
 a slightly different approach , xu and lill 
 developed a knowledge - based ensemble selection technique that can 
 be used with any type of affinity measurement . in it , receptor conformers are first ranked by their ability 
 to separate the average docking scores of active and inactive compounds . 
 then , by assuming that effective ensembles must be constructed from 
 effective conformations , ensembles of successively larger size are 
 formed by aggregating conformers from highest to lowest rank . for example , does the procedure ignore ensembles with 
 significantly greater classification power ? while the underlying assumption 
 went unexamined , the approach appeared promising . when classification 
 ability was examined as a function of ensemble size , the performances 
 of the trained ensembles were comparable or better than the those 
 of ensembles selected by aggregating structurally diverse receptor 
 conforms . a final approach , developed and widely applied by 
 the cavasotto 
 and abagyan groups , utilizes virtual screening performance on a small 
 training set to select the most promising structure from an ensemble 
 generated using either monte carlo side - chain sampling or normal - mode 
 analysis . by including a ligand with 
 the desired properties , for example , a high affinity binder or a receptor 
 agonist / antagonist , the search may be biased toward structures that 
 enrich ligands with similar properties . during model generation , the 
 vs ability of each target conformer is evaluated , and conformational 
 sampling continues until vs performance converges . following convergence , 
 a single best performing structure can be derived and used for cross 
 docking , selectivity studies , or vs. alternatively , multiple conformers 
 may be extracted and combined into useful ensembles , and the methods 
 we introduce here may prove useful in such an approach . in this 
 work , we present three new training methods that select 
 structure - based ensembles for vs use . all three methods construct 
 ensembles by optimizing one of two binary classification metrics , 
 which makes them flexible and enables their use with single - point 
 data , competition assay data ( e.g. , ic50 values ) , or other 
 binding data . to address the combinatorial problem , the population 
 of ensembles is generated by complete enumeration , and two different 
 heuristics are designed to generate population samples biased to exclude 
 low performing ensembles . these approaches lead to different asymptotic 
 scaling as the number of receptor conformations becomes large , and 
 they allow us to examine the severity of the approximations underlying 
 each heuristic relative to the enumerative solution . each method 
 is evaluated on three different target proteins with 
 active and decoy molecules taken from the dud - e : the androgen nuclear hormone receptor ( ar ) , the cyclin - dependent 
 kinase 2 ( cdk2 ) , and the peroxisome proliferator - activated receptor 
  ( ppar- ) . target conformations were selected from a 
 range of sources , including rmsd and volumetric clustering of conventional 
 md simulations , as well as multiple crystal structures . the knowledge - based training 
 methods were tested on three protein targets : the androgen receptor , 
 the cyclin - dependent kinase 2 ( cdk2 ) , and the peroxisome proliferator - activated 
 receptor  ( ppar- ) . conformations generated by volumetric 
 clustering of conventional md trajectories along with the crystal 
 structure pdbid 2am9 were used to train androgen receptor ensembles . similarly , conformations 
 generated by rmsd clustering of md trajectories , along with the crystal 
 structure pdbid 4gcj , were used to train ensembles of cdk2 . clustering and simulation 
 details are provided in subsequent sections . for ppar- , ensemble 
 training was performed using 12 crystal structure conformations with 
 the following pdbids ( uniprot q03181 ) : 2awh , 2b50 , 2j14 , 2q5 g , 2xyj , 2znp , 3dy6 , 3et2 , 3gz9 , 3peq , 3sp9 , and 3tkm . structures were selected to ensure a 
 resolution of 3.0  or lower and to ensure that each ligand was 
 unique . additionally , all of the structures are antagonist bound , 
 which is consistent with the antagonists that make up the actives 
 of the training and test sets , as described below . active and 
 decoy ligand sets from the directory of useful decoys - ehanced ( dud - e ) were used to perform virtual screening for each 
 target . while a complete description of ligand set curation can be 
 found in the original reference , we briefly describe the process here . compounds in chembl whose affinities ( ic50 , ec50 , ki , kd ) 
 were less than or equal to 1 m were clustered by their bemis 
 murcko ( bm ) frameworks . compounds with 
 the highest affinity from each cluster were pooled and resulted in 
 sets of actives with unique bm frameworks . for each active , 50 decoys 
 were selected from the zinc database by matching the molecular weight , 
 logp , number of rotatable bonds , hydrogen bond donor and acceptor 
 counts , and net formal charge ( determined in a ph range from 6 to 
 8) of the active . to reduce the number of false negatives , only the 
 25% most dissimilar decoys , as judged by tanimoto scores using ecf4p 
 fingerprints , were retained . evaluating the classification performance 
 of a knowledge - based 
 model on the training set will generally provide an overly optimistic 
 estimate of the model s ability to correctly distinguish active 
 and inactive molecules . to provide a 
 more realistic estimate of the trained model s classification 
 ability , dud - e compounds were randomly split in half , while maintaining 
 the decoy - to - active ratio , forming training and test sets . the androgen 
 receptor training and test sets were composed of 7150 compounds , 133 
 of which were active compounds . the cdk2 training and test sets were 
 composed of 14,162 compounds , 237 of which were active compounds . the ppar- training and test sets were composed of 6245 compounds , 
 120 of which were active . simulations were initiated 
 from a crystal structure of either the androgen receptor ( pdbid 2am9 ) or cdk2 ( pdbid 4gcj ) . the sulfate ion , 
 glycerol , and the dithiotheritol molecule were deleted from 2am9 , while four molecules 
 of ethanediol were deleted from 4gcj . in 2am9 , e893 are far from 
 the receptor - binding pocket and have unresolved side - chain atoms . schrdinger s prime was used to 
 add them . in 4cgj , atoms from the following residues had multiple occupancy values : 
 d38 , s46 , d127 , k129 , r169 , l212 , m233 , k237 , k250 , s264 , and h268 . 
 in each case , the position with the larger value was retained . protonation 
 states for both 2am9 and 4gcj were 
 predicted at ph 7.0 using the program propka3 , and hydrogen 
 atom positions were assigned and optimized using schrdinger s 
 protein preparation wizard . following protonation , water molecules 
 with fewer than three hydrogen bonds to nonwater molecules were removed . the protonated crystal structures were built for md simulation using 
 the xleap program that accompanies amber14 . the cholesterol and rc-3 - 89 ligand parameters were generated using 
 the antechamber program in amber14 . ligand atomic partial charges 
 were determined from the crystallographic conformations using the 
 am1-bcc method , and all other force field 
 terms were assigned according to the generalized amber force field 
 ( gaff ) . each system was immersed in a 
 box of pre - equilibrated tip4pew water that provided a minimum 10  water pad between the protein 
 and the boundary of the periodic box in the x- , y- , and z - directions . each system was brought 
 to electric neutrality by the addition of an appropriate number of 
 chloride or sodium ions , modeled using the parameters developed by 
 joung and cheatham . the androgen receptor 
 system was comprised of 54,014 atoms , and the cdk2 system was composed 
 of 50,644 atoms . the potential energy was described by the amber14 
 force field with the stony brook correction . a 20,000-step minimization was performed with 2 kcal mol  heavy atom backbone restraint in two 
 stages . during the first step , following minimization , a 200 ps npt simulation was 
 carried out at 300 k and 1 atm . pressure was maintained with a monte 
 carlo barostat with 100 steps between volume changes and a pressure 
 relaxation time of 2 ps . following the npt simulation , 
 a 5 ns nvt simulation was conducted , and restart files were written 
 every 1 ns . these restart files were used to initiate five 20 ns nvt 
 simulations , and frames were written every 2000 fs . all 50,000 frames 
 were concatenated yielding a 100 ns trajectory . during npt and all 
 nvt simulations , hydrogen heavy atom bonds were constrained using 
 the shake algorithm , and a 2 fs time 
 step was used . temperature was maintained in all simulations using 
 a langevin thermostat with a collision frequency of 2 ps . the particle mesh ewald method was used to treat long - range electrostatics , and simulations were performed using pmemd.cuda 
 on a geforce gtx titan card from nvidia . during nvt production runs , the simulation setup resulted in an average timing of 30.29 ns / day 
 on the androgen receptor system and 31 ns / day on the cdk2 system . the 100 ns trajectories were 
 each subsampled at an interval of 40 ps , or every 20th frame , resulting 
 in a total of 2500 frames , which were then clustered . prior to clustering , 
 external translation and rotation were removed from each trajectory 
 by minimizing the rmsd distance of the c backbone atoms to 
 the equivalent atoms of the first sampled frame of the trajectory . for the androgen receptor trajectory , the binding site shape of 
 each sampled structure was determined using povme 2.0 . following binding site characterization , 
 the tanimoto volume overlap between all pairs of structures was calculated , 
 from which a normalized volume overlap matrix was generated . finally , 
 hierarchical clustering was applied to the overlap matrix , 10 clusters 
 were generated , and the structures corresponding to each of the cluster 
 centroids were retained for docking . ligand - based autodetection of 
 inclusion regions and hierarchical clustering are features that will 
 be released in the forthcoming version of povme . for the cdk2 
 trajectory , rmsd clustering was performed using the 
 algorithm described in daura et al . as 
 implemented in version 5.0.3 of the gromacs g_cluster program . clustering 
 was performed on the heavy atoms of all residues within 10  
 of the bound inhibitor rc-3 - 89 in the crystal structure pdbid 4gcj . a cutoff of 1.6 
  resulted in five clusters , and cluster centroids were retained 
 for docking . the glide sp algorithm , 
 from schrdinger , 
 was used to perform docking to all target conformations . relative to the protein receptor , each pose has a unique position 
 and orientation . following generation , all poses are independently subjected to a set 
 of hierarchical filters that utilize precomputed grids to estimate 
 ligand poses with the receptor are 
 computed using a grid - based version of chemscore . poses that pass 
 the initial filter are minimized in a grid - based approximation of 
 the opls pose  receptor interaction energy . following minimization , 
 emodel , an empirical scoring function optimized to compare pose energetics , 
 is used to identify the best pose for each ligand . the docking score is an 
 empirical ligand binding affinity estimate , which incorporates epik 
 state penalties that are based on the predicted populations of alternative 
 ligand protonation and tautomerization states . prior to docking , two - dimensional representations 
 of active and decoy molecules were downloaded from the dud - e in sdf 
 format . ligprep program was used to add hydrogen atoms and generate three - dimensional 
 ligand structures . alternative protonation and tautomer states were 
 determined at ph 7 using the epik program , with default settings . alternative ring conformations were not generated since these are 
 produced by glide during docking . input chiralities were retained , 
 and all other options were set to their default values . tip4pew 
 water and chloride ions were removed from the md trajectory . the resulting 
 trajectory , which consisted of either the androgen receptor and the 
 testosterone ligand or cdk2 and the inhibitor rc-3 - 89 were clustered 
 as described above , resulting in 10 and 6 cluster centroids , respectively . schrdinger s protein preparation wizard was used to 
 generate correct atom types for glide grid generation . protonation states from the md simulation 
 were retained , and neither hydrogen bond network optimization nor 
 structural minimizations were conducted . for each cluster centroid , 
 the grid center was positioned on the center of geometry of the ligand ; 
 all other options were set to their default values . docking was conducted 
 locally on a dell precision t7500n workstation with a dual six - core 
 intel x5680 processor , and each compound required roughly 15 s to 
 dock . receiver operating characteristic , 
 or roc , curves were used to evaluate the performance of each ensemble . roc curves provide two useful measures of binary classification performance : 
 the area under the curve ( auc ) and the roc enrichment factor ( ef ) . a roc curve is determined by successively moving a threshold through 
 compounds ranked by their docking scores . by assuming all compounds 
 with scores better than the threshold are active , a true positive 
 fraction ( tpf ) and false positive fraction ( fpf ) can be calculated 
 at each threshold . for example , the tpf is the fraction of active 
 compounds whose docking scores are equal to or better than the threshold , 
 gt . tpf can be calculated as an 
 average over an indicator function ,  , as described by eq 1.1 in eq 1 , na is the total number of active 
 compounds . for a given active , the indicator function  takes 
 a value of 1 if the value of the docking score , gi , is better than or identical to the 
 threshold and a value of 0 otherwise . similarly , the fpf is the fraction 
 of inactive compounds whose docking scores are equal to or better 
 than the threshold . it is also determined as an average of  , 
 but over the inactive compounds.2 in eq 2 , ni is the total number of inactive 
 compounds , and all other terms are defined identically to eq 1 . once the tpf and fpf 
 values have been calculated at each threshold , they are plotted along 
 the y - axis and x - axis , respectively , 
 resulting in a roc curve . the area under the roc curve ( auc ) 
 is equivalent to the probability 
 that a virtual screening protocol will rank a randomly selected active 
 compound ahead of a randomly selected inactive compound . an auc value of 0.5 corresponds to random selection , 
 or a method with no classification power , while a value of 1 indicates 
 perfect separation of active and inactive compounds . additionally , 
 the value of the auc is independent of the fraction of actives in 
 the database , it has no free parameters , and an analytic estimate 
 of its standard error is known . the auc 
 value can be estimated using a left - handed riemann sum , which is equivalent 
 to averaging the tpf values at each inactive compound of the ranked 
 list.3 while the auc is 
 a useful measure of global classification performance , 
 the early enrichment , or the preferential ranking of active compounds 
 early in the ranked list , is often used to judge the quality of a 
 virtual screen . enrichment factors are frequently calculated as the 
 ratio of the fraction of actives found in a given percent of the ranked 
 database to the fraction of actives in the total database . unfortunately , 
 the maximum value of this popular metric depends on the ratio of inactive 
 to active compounds in the screened database . , we use the so - called  roc enrichment  , 
 whose maximum value is independent of the ratio of decoy to active 
 compounds . the roc enrichment factor ( ef ) is the ratio of the tpf , 
 determined at some fpf of interest , to the fpf of interest.4random classification is 
 indicated by an ef 
 value of 1 , and perfect separation of actives and decoys is given 
 by a maximum value of fpf . like the auc , the standard 
 error of the roc enrichment factor may be calculated analytically , 
 which facilitates statistical analysis . for any vs protocol , classification 
 performance will vary as a result of having different compounds in 
 the screened database . for example , assuming repeated screens are performed 
 identically on different databases , the true mean should be found 
 within identically constructed 95% confidence intervals ( ci95 ) in 95% of the measurements . ci95 values were constructed 
 according eq 5.5the standard error , se , of the calculated 
 classification metric ( auc or ef ) is given and is calculated differently 
 for auc and roc - ef values . the exact form that each takes is provided 
 in the supporting information . the value 
 of l is selected such that  l bounds 95% of student s t - distribution , 
 where the number of degrees of freedom was determined by subtracting 
 one from the sum of the number of active and inactive compounds . several different methods for combining 
 multiple docking scores into a single docking score have been suggested . reported protocols include creating composite grids of all ensemble 
 members , treating conformations as an independent 
 variables during docking , and using different 
 weighted averages , which include arithmetic and boltzmann weighted averages , as 
 well as averages using weights determined by knowledge - based methods . one simple approach , and the one used in this 
 work , takes the best scoring function value across all ensemble members . 
 for example , a compound docked to an ensemble composed of n protein conformations will have n docking 
 scores , { g1 , g2 , ... , gn } , and the ensemble score of the compound is defined as the 
 smallest score of the set , i.e. , min{g1 , g2 , ... , gn}. if a compound has more 
 than one protonation or tautomer state , the state with the lowest 
 docking score is retained . given a collection of 
 target conformations generated either by 
 experiment or by simulation , it is difficult or impossible to know a priori which subset will result in the best vs performance . the problem becomes increasingly challenging as the number of target 
 conformations grows , and this is the result of the combinatorial nature 
 of the problem . to address this problem , we presented three knowledge - based 
 ensemble selection methods : the exhaustive method , the slow heuristic 
 method , and the fast heuristic method . for each method , the discussion 
 includes schematic illustrations that describe the underlying selection 
 algorithm and an examination of performance , scaling , and limitations ; 
 results from the androgen receptor , cdk2 , and ppar- provide 
 context . by enumeration of all possible combinations 
 of conformers , the exhaustive method generates the complete ensemble 
 population and only retains the highest performing individual ; that 
 is , the exhaustive method is guaranteed to identify the best performing 
 member of the population . three receptor conformers , colored red , 
 green , and blue are shown , and the ensembles that can be constructed 
 at each size are also shown . the population constitutes all of the 
 ensembles at each size , and in the simple schematic , contains seven 
 members . by performing a census of the population training method schematic : selecting the best performing 
 ensemble 
 from three target conformers . as indicated by the greater than symbols , 
 the vs performance , measured by either the auc or ef , is greatest 
 for the red conformer , followed by the green conformer , and the blue 
 conformer is the poorest performer . each method is found in a column , 
 and all combinatorial possibilities are shown . the vs performance 
 of enumerations marked with an the slow heuristic assumes the next largest optimal 
 ensemble is formed only from a combination of the current ensemble 
 and one of the remaining conformers . the fast heuristic method ranks 
 the vs performance of each target conformer and assembles ensembles 
 by successively including conformers of decreasing performance . applying conformation enumeration 
 to generate ensembles is not 
 new , and the idea has appeared in the literature . for example , to 
 retrospectively compare the vs performance of ensemble and single 
 crystal structure vs protocols , korb et al . used a similar enumerative approach . however , in their work , enumeration 
 was not tied to ensemble training , and we later proposed that enumeration 
 could be used to identify ensembles with the greatest vs utility . as the 
 exhaustive method does , guarantees that the best performing ensemble 
 will be identified , but the process is computationally expensive . 
 to reduce expense , we introduced the slow heuristic , which builds 
 ensembles recursively . beginning with the best performing target conformer , 
 each conformation not yet assigned to an ensemble is grouped with 
 the best performing ensemble of the current size . this produces a 
 sample of ensembles , each with one additional conformation and a characteristic 
 vs performance , from which the best ensemble is selected . the process 
 continues until all conformers have been included in an ensemble , 
 and the ensemble that performs best overall is retained . following this heuristic produces a biased sample that neglects population members 
 that do not contain the best performing ensembles of smaller sizes . to clarify how the slow heuristic results in biased samples column in figure 6 . 
 of the three conformations , the red one performs best , the green next 
 best , and the blue conformation performs worst . the one - membered ensemble 
 is made up of the single best performing target conformer , or the 
 red conformer , in this case . after identifying the one - membered ensemble , 
 two two - membered ensembles are then generated . each contains the best 
 one - membered ensemble : red - blue and red - green . since the blue - green 
 ensemble does not contain the best performing one - membered ensemble , 
 it is neglected . while it is not a given that the slow heuristic 
 will result in 
 samples biased to favor high performing ensembles , that did prove 
 to be the case in the three targets considered in this work . this 
 was illustrated in part by the overlap of the population and slow 
 heuristic sample distributions in figure 1 and in part by the ability of the method 
 to identify the best performing ensemble from the population . for 
 example , in figure 1 , the slow heuristic sample favored ensembles that produced larger 
 values of both classification metrics considered , and this was true 
 across all three targets . additionally , the slow heuristic identified 
 the best performing ensemble from the population in five out of the 
 six cases considered ( tables 2 and 3 ) . these observations provide 
 further support for the claim that the method produces biased samples 
 favoring high performing ensembles , and they suggest that the method 
 may be generally applicable across different target classes and roc - based 
 objective functions . nevertheless , because the slow heuristic 
 samples the population , 
 it may miss ensembles in which synergism between poor performing conformations 
 can lead to a higher performing ensemble . to help clarify this , consider 
 the blue and green conformations in figure 6 . despite their poorer individual performances , if they pair to form a high performing two - membered ensemble , it will 
 not be sampled by the slow heuristic . however , while missing potential 
 synergism is possible , when the sample is biased toward high performing 
 ensembles , the best performing sample member may perform comparably 
 to the highest performing population member . for example , when the slow heuristic was used to train androgen 
 receptor ensembles to maximize the auc , the sample did not contain 
 the optimal ensemble from the population ; however , the performances 
 of the best ensemble from the sample and the best ensemble from the 
 population were within confidence intervals of one another ( table 2 ) . the slow 
 heuristic appears to offer a reasonable compromise between 
 computational efficiency and performance . to illustrate the computationally 
 efficiency , in the supporting information , we show that the exhaustive method scales as o(2 ) , given n target 
 conformations , while the slow heuristic scales as o(n ) . for example , if 23 receptor conformations 
 are considered , the exhaustive method considers roughly 8.3 million 
 ensembles , while the slow heuristic method only evaluates 264 ensembles . however , since each of the enumerated ensembles can be evaluated on 
 a single processor , it is noteworthy to point out that the exhaustive 
 method is embarrassingly parallel . by constructing ensembles of increasing 
 size by successively merging conformations of decreasing performance , 
 the fast heuristic ignores the pools of ensembles generated at each 
 size by the slow heuristic and further reduces computational expense . thus , the fast heuristic produces a small , biased sample that neglects 
 the poorest performing conformations at each ensemble size . to clarify how the fast heuristic produces biased samples , since the red conformation performs best , it is selected as the one - membered 
 ensemble , and the poorer performing conformations are neglected . by 
 merging the one - membered ensemble with the next best performing conformation , 
 the two - membered red - green ensemble is produced . the green - blue ensemble 
 is ignored , just as it is by the slow heuristic , but the red - blue 
 ensemble is also ignored , which results in a smaller sample . relative to the exhaustive solution , which generates the entire 
 ensemble population , the fast heuristic sample is significantly smaller . 
 in general , given n target conformations , the ensemble 
 population has a size 2  1 , and 
 the fast heuristic only considers 2n  1 of 
 these . in practice for example , with 11 androgen receptor conformations , the fast heuristic 
 method ignores 2026 of the 2047 possible ensembles . the fast 
 heuristic is nearly identical to the method of xu and 
 lill , which was described in the introduction . however , rather than using the value 
 of a roc classification metric , they ranked target conformations by 
 the differences in average docking scores of decoy and active molecules 
 to each conformer . while xu s and lill s results were 
 promising , the effect of ignoring a significant fraction of the ensemble 
 population was not assessed . to provide insight into the severity 
 of the heuristic relative 
 to the enumerative solution consistent with the small sample size , the fast heuristic 
 was only able to identify the best performing population member in 
 one of the six cases considered ( tables 2 and 3 ) . despite this , 
 the ensembles identified performed similarly to the best performing 
 ensemble of the population : fast heuristic performance values were 
 within confidence intervals of the best performing members of the 
 population for all three targets and both objective functions . despite 
 the much smaller sample size , the fast heuristic may be a generally 
 applicable approach that offers linear scaling without a dramatic 
 sacrifice in classification ability . docking 
 to structural ensembles is a promising means of identifying 
 novel , structurally diverse active compounds . despite the potential 
 of ensemble docking , it is difficult to know which structures will 
 synergize and perform well during a virtual screen . this problem emerges 
 from the combinatorial nature of ensemble selection . to address the 
 selection problem each method scales differently in the limit of a large number of receptor 
 conformations but can perform similarly , which was demonstrated by 
 constructing ensembles of the androgen receptors , cdk2 , and ppar- 
 and with either x - ray crystallographic structures or snapshots from 
 all - atom molecular dynamics trajectories . as with all other knowledge - based 
 methods , those presented here are fundamentally limited by the availability 
 of high quality ligand sets . nevertheless , virtual screens are often 
 carried out on targets for which active and inactive molecules are 
 known . in these cases , the ensemble selection methods presented have 
 broad applicability .
ensemble docking 
 can be a successful virtual screening technique 
 that addresses the innate conformational heterogeneity of macromolecular 
 drug targets . yet , lacking a method to identify a subset of conformational 
 states that effectively segregates active and inactive small molecules , 
 ensemble docking may result in the recommendation of a large number 
 of false positives . here 
 , three knowledge - based methods that construct 
 structural ensembles for virtual screening are presented . 
 each method 
 selects ensembles by optimizing an objective function calculated using 
 the receiver operating characteristic ( roc ) curve : either the area 
 under the roc curve ( auc ) or a roc enrichment factor ( ef ) . as the 
 number of receptor conformations , 
 n , becomes large , 
 the methods differ in their asymptotic scaling . given a set of small 
 molecules with known activities and a collection of target conformations , 
 the most resource intense method is guaranteed to find the optimal 
 ensemble but scales as o(2n ) . a recursive approximation to the optimal solution scales 
 as o(n2 ) , and a more 
 severe approximation leads to a faster method that scales linearly , o(n ) . 
 the techniques are generally applicable 
 to any system , and we demonstrate their effectiveness on the androgen 
 nuclear hormone receptor ( ar ) , cyclin - dependent kinase 2 ( cdk2 ) , and 
 the peroxisome proliferator - activated receptor  ( ppar- ) 
 drug targets . conformations that consisted of a crystal structure 
 and molecular dynamics simulation cluster centroids were used to form 
 ar and cdk2 ensembles . 
 multiple available crystal structures were 
 used to form ppar- ensembles . for each target , we show that 
 the three methods perform similarly to one another on both the training 
 and test sets .