liveBook · Manning

Clustering

As explained in Build AI Drug Discovery Pipelines

Clustering is an unsupervised learning technique that partitions data instances into groups of similar instances.

Clustering is an unsupervised learning technique that groups similar data instances without requiring labels. Each group is a cluster: the model determines how to divide the data and assigns instances to the resulting groups. In drug discovery, clustering can organize a compound library so that representative molecules can be selected from different clusters. section 1.2.2 section 7.2.3

The resulting groups depend on how similarity is measured. A molecular fingerprint encodes features of a molecule; a distance measure then compares those representations. One workflow uses Morgan fingerprints with radius 2 and converts Tanimoto similarity to distance by subtracting it from 1. Representation, distance, clustering algorithm, and selection strategy are linked choices: an earlier choice affects the options that follow. section 7.2.3

A cluster-based compound selection workflow has four main decisions:

  • Represent each compound with descriptors or fingerprints. section 7.2.3
  • Choose a distance measure appropriate to the representation. section 7.2.3
  • Choose a clustering algorithm to divide the compounds into groups. section 7.2.3
  • Select compounds from each cluster according to the library’s requirements. section 7.2.3

Hierarchical clustering builds a hierarchy of groups. Divisive clustering starts with all compounds together and repeatedly splits groups. Agglomerative clustering starts with each compound in its own group and repeatedly merges the closest groups. A linkage method determines how distances between groups are calculated. section 7.2.3

Listing 7.7 Fit Agglomerative Clustering with Ward’s Method
from rdkit import DataStructs
from rdkit.Chem import rdFingerprintGenerator
from sklearn.cluster import AgglomerativeClustering
 
def molecules_to_fingerprints(mols, maxPath=5):
    rdkit_gen = rdFingerprintGenerator.GetRDKitFPGenerator(    #A
        maxPath=maxPath)   #A
    fingerprints = [rdkit_gen.GetFingerprint(mol) for mol in mols]
    np_fps = []
    for fp in fingerprints:
        arr = np.zeros((1,))
        DataStructs.ConvertToNumpyArray(fp, arr)
        np_fps.append(arr)
    return np.array(np_fps), fingerprints
 
fps, rdkit_fps = molecules_to_fingerprints(new_mols)
 
model = AgglomerativeClustering(    #B
    distance_threshold=0, n_clusters=None, linkage='ward')    #B
model = model.fit(fps)

This Python listing converts molecules to RDKit fingerprints and fits scikit-learn’s agglomerative clustering with Ward linkage. It uses RDKit fingerprints rather than the Morgan fingerprints described above. section 7.2.3

Listing 7.8 Agglomerative Clustering & Sampling Diverse Compounds
from scipy.spatial.distance import cdist
def sample_from_clusters(fps, clusters, n_samples=3):
    sampled_mols, cluster_centers = [], []
    for cluster in clusters:
        if len(cluster) < n_samples:
            sampled_mols.extend(cluster)
        else:
            cluster_fps = [fps[i] for i in cluster]
            cluster_center = np.mean(cluster_fps, axis=0).reshape(1, -1)
            cluster_centers.append(cluster_center)
 
            distances = cdist(
                cluster_fps, cluster_center, metric='euclidean'
            )
            closest_indices = np.argsort(distances.flatten())[:n_samples]
            sampled_mols.extend([cluster[i] for i in closest_indices])
    return sampled_mols
 
agg_model = AgglomerativeClustering(n_clusters=16, linkage='ward')
agg_model.fit(fps)
agg_clusters = [
    np.where(agg_model.labels_ == i)[0].tolist()
    for i in np.unique(agg_model.labels_)
]
agg_sampled_indices = sample_from_clusters(fps, agg_clusters)
agg_sampled_molecules = [new_mols[i] for i in agg_sampled_indices]

This listing fits 16 clusters and selects compounds close to each cluster’s mean fingerprint. Small clusters contribute all their compounds. section 7.2.3

Evaluate the selected library as well as the clusters. Pairwise fingerprint similarity and the proportion of pairs above a similarity threshold provide checks on diversity and redundancy. Clusters can also be misleading when their input representation is poor: dimensionality reduction errors can carry through to downstream clustering and analysis. section 7.2.3 section 7.1.3

Listing 7.10 Evaluate Agglomerative and Taylor-Butina on Library Diversity
def calculate_diversity(sampled_indices, fingerprints):
    sampled_fps = [fingerprints[i] for i in sampled_indices]
    n = len(sampled_fps)
    sims = []
    for i in range(n):
        for j in range(i + 1, n):    #A
            sims.append(DataStructs.FingerprintSimilarity(
                sampled_fps[i], sampled_fps[j]))
    return float(np.mean(sims))    #B
 
def calculate_redundancy(sampled_indices, fingerprints, threshold=0.85):
    sampled_fps = [fingerprints[i] for i in sampled_indices]
    n = len(sampled_fps)
    num_redundant_pairs = 0
    num_unique_pairs = n * (n - 1) / 2
    for i in range(n):
        for j in range(i + 1, n):    #C
            sim = DataStructs.TanimotoSimilarity(sampled_fps[i], sampled_fps[j])
            if sim > threshold:
                num_redundant_pairs += 1
    return num_redundant_pairs / num_unique_pairs    #D
 
agg_diversity = calculate_diversity(agg_sampled_indices, rdkit_fps)
butina_diversity = calculate_diversity(butina_sampled_indices, rdkit_fps)
agg_redundancy = calculate_redundancy(agg_sampled_indices, rdkit_fps)
butina_redundancy = calculate_redundancy(butina_sampled_indices, rdkit_fps)
 
# print statements omitted for brevity
Output (representative values from the chapter 7 notebook):
Agglomerative sampled-set diversity (lower is better):  0.2909
Taylor-Butina sampled-set diversity (lower is better):  0.2365
Agglomerative sampled-set redundancy (lower is better): 0.0762
Taylor-Butina sampled-set redundancy (lower is better): 0.0010

This listing calculates mean pairwise fingerprint similarity and counts highly similar pairs to assess a selected library. section 7.2.3

How Build AI Drug Discovery Pipelines covers it

How deep it goes
Explains representation, distance, hierarchical clustering, sampling, and evaluation with implementations of agglomerative and Taylor-Butina clustering.
Examples
Demonstrates fingerprint-based compound selection, cluster sampling, and library diversity and redundancy checks.
What you can do after
Apply it via RDKit and scikit-learn to group molecular fingerprints and select compounds from clusters.
How it connects
Connects clustering to molecular fingerprints, Tanimoto similarity, hierarchical clustering, and dimensionality reduction.

Also explained in

Compare how 24 books explain clustering →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Build AI Drug Discovery Pipelines. The section links point to the parts of the book it draws on.