Space complexity measures how an algorithm’s memory requirements grow as input size increases. For molecular clustering, the dominant storage structure can determine whether a method scales to a compound library. section 7.2.3
For clustering molecular fingerprints:
- Agglomerative clustering uses O(n²) memory for its pairwise distance matrix. section 7.2.3
- K-means uses O((n + k) × d) memory to store data points and centroids. section 7.2.3
- Taylor-Butina uses O(n²) memory when the implementation materializes all pairwise distances, but an optimal implementation can use O(n × d). section 7.2.3
Molecular library clustering
With n compounds and d fingerprint dimensions, storing every pairwise distance requires quadratic memory, while storing compounds and their features requires linear-in-n memory. 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 fingerprint conversion and agglomerative clustering code to connect the memory analysis with a molecular implementation. section 7.2.3




