liveBook · Manning

Performance

As explained in Build AI Drug Discovery Pipelines

Big O notation describes an algorithm's asymptotic growth in time or memory as input size or dimensionality increases.

Big O notation profiles how machine-learning algorithms scale as the number of compounds or feature dimensions grows. It helps select methods when processing time and memory are constrained, especially for libraries containing millions of compounds represented in 1K-plus dimensions. section 7.2.3

For clustering, the stated worst-case costs are:

  • Agglomerative clustering: O(n³ × d) time and O(n²) memory, because pairwise distances and successive merges create substantial cost. section 7.2.3
  • K-means clustering: O(k × n × i × d) time and O((n + k) × d) memory, where k is the centroid count and i is the iteration count. section 7.2.3
  • Taylor-Butina clustering: pairwise distance computation can require quadratic memory when the implementation materializes all distances; optimized implementations can use less. 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)

Inspect a runnable RDKit and scikit-learn implementation of agglomerative clustering on molecular fingerprints. section 7.2.3

How Build AI Drug Discovery Pipelines covers it

How deep it goes
Defines asymptotic time and memory costs for three clustering methods, but stops short of formal derivations.
Examples
Compares clustering costs for millions of compounds represented by more than 1K features.
What you can do after
Evaluate clustering methods by estimating their time and memory growth before applying them to large compound libraries.
How it connects
Connects Big O notation with agglomerative clustering, K-means clustering, Taylor-Butina clustering, and dimensionality reduction.

Also explained in

Compare how 55 books explain performance →

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.