Clustering

Cheminformatics clustering and diversity picking behind a scikit-learn API: Taylor–Butina, sphere exclusion, MaxMin and hierarchical linkage, all on Tanimoto distance.

Warning

Euclidean distance is wrong for sparse binary fingerprints. Two molecules sharing no bits at all are “close” in Euclidean terms because they agree on the thousands of bits that are jointly zero — which carry no chemical information. Everything here uses Tanimoto/Jaccard.

Taylor–Butina

The standard cheminformatics clustering: no n_clusters to choose, just a similarity cutoff, and every cluster has a real molecule at its centre rather than an average that corresponds to nothing.

>>> from qsarkit.cluster import ButinaClustering
>>> X = demo_fingerprints(256)
>>> labels = ButinaClustering(cutoff=0.6).fit_predict(X)
>>> labels[:8].tolist()
[0, 0, 0, 0, 0, 0, 0, 1]
>>> len(set(labels.tolist()))
6

The cutoff is a Tanimoto distance, so a larger value merges more:

>>> len(set(ButinaClustering(cutoff=0.4).fit_predict(X).tolist()))
14

Sphere exclusion and hierarchical

>>> from qsarkit.cluster import HierarchicalClustering, SphereExclusionClustering
>>> len(set(SphereExclusionClustering(cutoff=0.6).fit_predict(X).tolist()))
6
>>> HierarchicalClustering(n_clusters=3).fit_predict(X)[-4:].tolist()
[1, 1, 2, 2]

Diversity picking

MaxMin selects a maximally diverse subset — the right way to choose compounds for a screening plate, or a representative subset of a large library:

>>> from qsarkit.cluster import MaxMinPicker
>>> MaxMinPicker(n_to_pick=4, seed_index=0).fit(X).picks_.tolist()
[0, 21, 22, 8]

Each pick is the compound furthest from everything already picked, so the selection covers the space rather than clustering in its densest region — which is what a random sample would do.

API

Cheminformatics clustering and diversity picking with a scikit-learn API.

All estimators here follow the scikit-learn clustering protocol (fit/fit_predict/labels_) and operate on fingerprint matrices using Tanimoto (Jaccard) distance, which is the chemically appropriate metric for sparse binary fingerprints.

class qsarkit.cluster.ButinaClustering(cutoff=0.35, metric='jaccard', reordering=False)[source]

Bases: BaseEstimator, ClusterMixin

Taylor-Butina sphere-exclusion clustering of fingerprints.

The standard clustering algorithm of cheminformatics. Unlike k-means it needs no n_clusters, produces deterministic results, and its single parameter (cutoff) is a chemically meaningful similarity threshold. The algorithm:

  1. Count, for every molecule, how many neighbours fall within the distance cutoff — its “neighbour count”.

  2. Take the molecule with the largest count as a cluster centroid, and assign all of its unassigned neighbours to that cluster.

  3. Repeat with the next-largest unassigned molecule until none remain.

Molecules that end up alone form singleton clusters, which is informative: a large singleton fraction means the library is structurally diverse (or the cutoff is too tight).

Parameters:

  • cutoff (float) – Maximum Jaccard distance for two molecules to be neighbours, i.e. a Tanimoto similarity of 1 - cutoff. The 0.35 default (Tanimoto 0.65) is the customary value for ECFP4.

  • metric (str) – "jaccard" computes Tanimoto distances from fingerprints; "precomputed" treats X as a square distance matrix.

  • reordering (bool) – If True, re-sort the remaining candidates by neighbour count after each cluster is formed (the “reordering” variant, which tends to give tighter clusters at higher cost).

Variables:

  • labels (ndarray of shape (n_samples,)) – Cluster index of each sample, ordered by descending cluster size.

  • cluster_centers_indices (ndarray of shape (n_clusters,)) – Index of the centroid molecule of each cluster.

  • n_clusters (int) – Number of clusters found.

Examples

>>> import numpy as np
>>> X = np.array([[1, 1, 1, 0], [1, 1, 1, 1], [0, 0, 0, 1], [0, 0, 1, 1]])
>>> model = ButinaClustering(cutoff=0.5).fit(X)
>>> model.n_clusters_ >= 1
True
>>> model.labels_.shape
(4,)

References

labels_: ndarray[tuple[Any, ...], dtype[int64]]
cluster_centers_indices_: ndarray[tuple[Any, ...], dtype[int64]]
n_clusters_: int
fit(X, y=None)[source]

Cluster the fingerprints (or precomputed distance matrix).

Parameters:
Returns:

The fitted estimator.

Return type:

ButinaClustering

fit_predict(X, y=None)[source]

Fit and return labels_.

Parameters:
Returns:

Cluster labels.

Return type:

ndarray[tuple[Any, ...], dtype[int_]]

class qsarkit.cluster.SphereExclusionClustering(cutoff=0.35, metric='jaccard')[source]

Bases: BaseEstimator, ClusterMixin

Sphere-exclusion clustering (RDKit LeaderPicker semantics).

Greedily selects “leader” molecules such that no two leaders are within cutoff distance of each other, then assigns every remaining molecule to its nearest leader. Unlike Butina it does not need the full neighbour-count pass, so it scales to very large libraries, and it guarantees a minimum inter-centroid distance — which is what makes it the usual choice for picking a diverse screening subset.

Parameters:

  • cutoff (float) – Minimum Jaccard distance between any two leaders.

  • metric (str) – Distance source, as in ButinaClustering.

Variables:

  • labels (ndarray of shape (n_samples,)) – Cluster assignment of each sample.

  • cluster_centers_indices (ndarray of shape (n_clusters,)) – Indices of the selected leaders.

  • n_clusters (int) – Number of leaders selected.

Examples

>>> import numpy as np
>>> X = np.array([[1, 1, 0, 0], [1, 1, 0, 1], [0, 0, 1, 1]])
>>> model = SphereExclusionClustering(cutoff=0.5).fit(X)
>>> model.labels_.shape
(3,)

References

labels_: ndarray[tuple[Any, ...], dtype[int64]]
cluster_centers_indices_: ndarray[tuple[Any, ...], dtype[int64]]
n_clusters_: int
fit(X, y=None)[source]

Select leaders and assign every sample to its nearest one.

Parameters:
Returns:

The fitted estimator.

Return type:

SphereExclusionClustering

fit_predict(X, y=None)[source]

Fit and return labels_.

Return type:

ndarray[tuple[Any, ...], dtype[int_]]

class qsarkit.cluster.MaxMinPicker(n_to_pick=10, metric='jaccard', seed_index=None)[source]

Bases: BaseEstimator

MaxMin diverse-subset selection (RDKit MaxMinPicker semantics).

Iteratively picks the molecule whose minimum distance to the already picked set is largest, producing a maximally spread-out subset. This is the standard way to choose a diverse plate from a large library, and the diversity-sampling primitive used by qsarkit.active_learning.

Parameters:

  • n_to_pick (int) – Size of the diverse subset to select.

  • metric (str) – Distance source.

  • seed_index (Optional[int]) – Index of the first pick. When None (default) the molecule farthest from the dataset centroid is used, which makes the result deterministic without a random seed.

Variables:

  • picks (ndarray of shape (n_to_pick,)) – Indices of the selected molecules, in selection order.

  • min_distances (ndarray of shape (n_to_pick,)) – The MaxMin distance achieved at each pick — a monotonically non-increasing diversity profile of the selection.

Examples

>>> import numpy as np
>>> X = np.array([[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 1, 1]])
>>> picker = MaxMinPicker(n_to_pick=2).fit(X)
>>> len(picker.picks_)
2

References

picks_: ndarray[tuple[Any, ...], dtype[int64]]
min_distances_: ndarray[tuple[Any, ...], dtype[float64]]
fit(X, y=None)[source]

Select the diverse subset.

Parameters:
Returns:

The fitted picker.

Return type:

MaxMinPicker

transform(X)[source]

Return the rows of X corresponding to the picks.

Parameters:

X (Union[Buffer, _SupportsArray[dtype[Any]], _NestedSequence[_SupportsArray[dtype[Any]]], complex, bytes, str, _NestedSequence[complex | bytes | str]])

Return type:

ndarray[tuple[Any, ...], dtype[double]]

fit_transform(X, y=None)[source]

Fit then return the picked rows.

Return type:

ndarray[tuple[Any, ...], dtype[double]]

class qsarkit.cluster.HierarchicalClustering(n_clusters=2, linkage='average', distance_threshold=None)[source]

Bases: BaseEstimator, ClusterMixin

Agglomerative clustering on Tanimoto distances.

A thin wrapper that computes the Jaccard distance matrix and hands it to scikit-learn’s AgglomerativeClustering with metric="precomputed", so that hierarchical clustering can be used on fingerprints with the chemically correct distance. Ward linkage is not available for precomputed distances; use "average" (the default here, equivalent to RDKit’s UPGMA option), "complete" or "single".

Parameters:

  • n_clusters (Optional[int]) – Number of clusters. Pass None together with distance_threshold to cut the dendrogram by distance instead.

  • linkage (str) – Linkage criterion.

  • distance_threshold (Optional[float]) – Distance at which to cut the dendrogram. Requires n_clusters=None.

Variables:

  • labels (ndarray of shape (n_samples,)) – Cluster labels.

  • n_clusters (int) – Number of clusters found.

Examples

>>> import numpy as np
>>> X = np.array([[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 1, 1], [0, 0, 1, 1]])
>>> model = HierarchicalClustering(n_clusters=2).fit(X)
>>> model.n_clusters_
2

References

labels_: ndarray[tuple[Any, ...], dtype[int64]]
n_clusters_: int
fit(X, y=None)[source]

Cluster fingerprints by agglomerative linkage on Tanimoto distance.

Parameters:
Returns:

The fitted estimator.

Return type:

HierarchicalClustering

fit_predict(X, y=None)[source]

Fit and return labels_.

Return type:

ndarray[tuple[Any, ...], dtype[int_]]

References

  • Butina, D. (1999). “Unsupervised Data Base Clustering Based on Daylight’s Fingerprint and Tanimoto Similarity.” J. Chem. Inf. Comput. Sci., 39(4), 747-750. doi:10.1021/ci9803381

  • Taylor, R. (1995). “Simulation Analysis of Experimental Design Strategies for Screening Random Compounds.” J. Chem. Inf. Comput. Sci., 35(1), 59-67. doi:10.1021/ci00023a009

  • Ashton, M. et al. (2002). “Identification of Diverse Database Subsets using Property-Based and Fragment-Based Molecular Descriptions.” Quant. Struct.-Act. Relat., 21(6), 598-604. doi:10.1002/qsar.200290002

  • Willett, P. (2006). “Similarity-Based Virtual Screening Using 2D Fingerprints.” Drug Discov. Today, 11(23-24), 1046-1053. doi:10.1016/j.drudis.2006.10.005