MaxMin algorithm

Finally, applying MaxMin algorithm II, the sets of molecules for which the Euclidean distance is maxima have been determined. 

When the algorithms were compared, howevei the MaxMin algorithm gave better results than the alternatives under study. In fact, several workers o > have highlighted a problem with the MaxSum procedure. The measure is based on the distance of the point from the centroid of the set and so tends to select molecules firom the comers of diversity space, and duplicate selections can appear to add to the diversity. This situation is clearly a problem with traditional descriptors, because the extremes of space tend to be less relevant chemical compounds (very high or very low log P, etc.). 

In the Maximum Dissimilarity (MD) selection method described by Lajiness [40] the first compound is selected at random and subsequent compounds are then chosen iteratively, such that the distance to the nearest of the compounds already chosen is a maximum. This method is known as MaxMin. In this study, the compounds were represented by COUSIN 2-D fragment-based bitstrings. Polinsky et al. [41] use a similar algorithm in the LiBrain system. In this case, the molecules are represented by a feature vector that contains information about the following affinity types—aliphatic hydrophobic, aromatic hydrophobic, basic, acidic, hydrogen bond donor, hydrogen bond acceptor and polarizable heteroatom. 

The basic DBCS algorithm has time complexity 0(n2N), where n compounds are selected from N. Since n is generally a small fraction of N, the time is thus cubic in N. DBCS can also be very computational demanding however, fast implementations have been developed, for example the MaxSum method described by Holliday et al. [42] and a MaxMin method described by Agrafiotis and Lobanov that can be used with low-dimensional descriptors [55],... 

This approach is particularly efficient when combined with the Cosine coefficient (69) and was used by Pickett et al. in combination with pharmacophore descriptors (70). In lower dimensional spaces the maxsum measure tends to force selection from the comers of diversity space (6b, 71) and hence maxmin is the preferred function in these cases. A similar conclusion was drawn from a comparison of algorithms for dissimilarity-based compound selection (72). 

Several different DBCS algorithms have been described and they differ in the way the seed compound is chosen and the way in which the dissimilarity of one compound to a set of compounds is measured [28]. For example, in the MaxMin method, the subset is chosen to maximize the minimum distance between all pairs of molecules in the subset [29], whereas in the MaxSum method, the subset that maximizes the sum of pairwise dissimilarities in the subset is chosen [28]. The basic... 

---