Cluster Jarvis-Patrick method

Shemetulskis et al. [44] describe a method based on clustering that was used to compare two external databases with a corporate database. Each database was clustered independently using the Jarvis-Patrick method [46] representative subsets of each database were chosen and the subsets were then mixed and re-clustered. The number of clusters that contain compounds from only one of the databases was then used as an indication of the degree of overlap between the two databases. A limitation of this approach is the computational effort required to re-cluster the mixed subsets. 

The Jarvis-Patrick method involves the use of a list of the top K nearest neighbours for each molecule in a dataset, i.e., the ATmolecules that are most similar to it. Once these lists have been produced for each molecule in the dataset that is to be processed, two molecules are clustered together if they are nearest neighbours of each other and if they additionally have some... 

An example of a non-hierarchical clustering method is the Jarvis-Patrick algorithm [Jarvis and Patrick 1973]. The Jarvis-Patrick method uses a nearest-neighbours approach. The nearest neighbours of each conformation are the conformations that are the shortest distance away. Two conformations are considered to be in the same cluster in the Jarvis-Patrick method if they satisfy the following criteria ... 

Conformations can thus be placed in clusters and clusters fused together (because any two individual elements satisfy the two criteria) without any hierarchical relationships. The Jarvis-Patrick method can also be extended to take account not only of the number of nearest neighbours but also the position of each conformation within the neighbour list. In addition, it is possible to require that a molecule s nearest neighbours must be within some defined distance. This ensures that the nearest neighbours of each conformation are not too dissimilar. 

The small clusters (< 5 members) were extracted and reclustered. When the results were checked by medicinal chemists, this strategy seemed to have reduced the number of singletons to an acceptable level. An alternative approach developed by Doman et al.i" employed a fuzzy clustering technique combined with the Jarvis-Patrick method. " The methodology has no user-defined parameters and allows compounds to belong to more than one cluster. 

Table 2. Execution times in CPU seconds and speed-ups for the clustering stage of the Jarvis-Patrick method...

Figure 3. Algorithm for the Jarvis-Patrick clustering method...

---