Molecular Similarity Search With Fingerprint Embeddings

Similarity search over molecules is a set-overlap problem dressed as a vector problem. Getting it fast is mostly about exploiting that, and getting it meaningful is mostly about knowing what the number does not say.

Tanimoto, computed

For two binary fingerprints A and B, the Tanimoto coefficient — identical to the Jaccard index — is the size of the intersection over the size of the union.

T(A,B) = c / (a + b - c)

  a = bits set in A
  b = bits set in B
  c = bits set in both

worked example, ECFP4 folded to 2048 bits:

  a = 48        molecule A sets 48 bits
  b = 52        molecule B sets 52 bits
  c = 31        31 bits are set in both

  T = 31 / (48 + 52 - 31)
    = 31 / 69
    = 0.449

in machine terms, over 2048-bit vectors packed into 32 words:
  c       = popcount(A AND B)
  a + b   = popcount(A) + popcount(B), both precomputed and stored
so a comparison is 32 ANDs and 32 popcount instructions.

Two properties are worth holding on to. Tanimoto ignores the bits set in neither molecule, which is nearly all of them in a sparse fingerprint — that is exactly the right behaviour, since two molecules sharing the absence of a ferrocene are not thereby similar. And one minus Tanimoto is a true metric on binary vectors, satisfying the triangle inequality, which is what licenses the pruning below.

Dice similarity, 2c / (a + b), is the other common choice; it is monotonically related to Tanimoto so it ranks identically and reads higher. Cosine on binary vectors gives c / sqrt(a*b). Report which one you used, because a paper quoting “similarity 0.6” without naming the coefficient and the fingerprint has said almost nothing.

The size bias built into the metric

Suppose A’s bits are a strict subset of B’s — a fragment and a molecule containing it. Then c = a and the union is b, so T = a / b. If A sets 20 bits and B sets 100, the maximum achievable similarity is 0.2, no matter how perfectly the fragment is contained.

This is not a defect to correct; it follows from the definition. But it has direct consequences. A screening library of small fragments will never look similar to a lead-like query, so a fixed Tanimoto threshold across a size-heterogeneous library silently excludes the small end. Substructure search — does this SMARTS pattern occur? — is the right tool for containment questions, and it is a different query with a different index.

The asymmetric variants exist for exactly this. Tversky similarity generalises Tanimoto with separate weights on the bits unique to each side — c / (c + alpha*(a-c) + beta*(b-c)) — and setting alpha to 1 with beta to 0 asks how much of the query is contained in the candidate while ignoring whatever else the candidate carries. That is the right coefficient for growing a fragment into a lead. It is also not symmetric, so it cannot be used with any index that assumes a distance, and the choice of coefficient therefore constrains the choice of index.

The bound that makes search fast

The size bias turns into a performance win. Since c cannot exceed the smaller of a and b, and the union cannot be smaller than the larger of them,

T(A,B)  <=  min(a, b) / max(a, b)

so if you require T >= t, then min(a,b)/max(a,b) >= t,
which for a query with a bits set means any candidate must satisfy

  t * a  <=  b  <=  a / t

worked: query sets a = 50 bits, threshold t = 0.7

  lower bound  0.7 * 50 = 35
  upper bound  50 / 0.7 = 71.4  -> 71

only candidates whose popcount is between 35 and 71 can
possibly reach 0.7. everything else is skipped without ever
computing an AND.

Sort the database by popcount once, and a threshold query touches a contiguous slice of it. This bound — set out by S. Joshua Swamidass and Pierre Baldi in the Journal of Chemical Information and Modeling in 2007 — plus tighter bounds that use the popcount of individual words, is why exact Tanimoto search over hundreds of millions of fingerprints runs on ordinary hardware. Andrew Dalke’s chemfp is the well-known implementation. The important consequence is that you usually do not need an approximate index at all: the search is exact and still fast.

Why a normal vector index disappoints

The instinct is to load fingerprints into whatever vector database is already running. HNSW and the other general-purpose indexes are built around cosine and Euclidean distance on dense float vectors, and a 2,048-bit fingerprint stored as 2,048 floats is 8 KB of mostly zeros per molecule — 256 times the memory of the packed bits, before the index.

Some engines support Jaccard or Hamming distance on binary vectors natively, and that combination is worth using. Where it is unavailable, the alternatives are a MinHash sketch of the fingerprint with locality-sensitive hashing — the approach behind MHFP and TMAP from Daniel Probst and Jean-Louis Reymond — or simply the popcount-bounded linear scan above, which is competitive far further up the scale than people expect.

If your goal is a dense embedding for a downstream model rather than retrieval, that is a different object: a learned encoder, or a dimensionality reduction of count fingerprints. Do not conflate the two. A learned molecular embedding retrieves neighbours that are similar under whatever objective it was trained on, which is a feature when the objective matches your question and a silent distortion when it does not.

What a similarity of 0.85 does not mean

The similar-property principle says structurally similar molecules tend to have similar properties, and a Tanimoto threshold around 0.85 on Daylight-style fingerprints entered folklore as the line above which molecules are “similar”.

Yvonne Martin, James Kofron and Linda Traphagen tested the implication directly in “Do Structurally Similar Molecules Have Similar Biological Activity?” (Journal of Medicinal Chemistry, 2002) and found that even above that threshold, the probability that a compound shares the activity of its neighbour is well below a half. The principle holds on average and fails constantly in the individual case — that failure is the activity cliff.

So the operational reading of a Tanimoto number is narrow. It is a good filter for finding analogues of a known compound, a good basis for diversity selection when you invert it, and a reasonable applicability- domain check for a property model. It is not a prediction of shared activity, and any threshold you choose is specific to the fingerprint type, the radius and the bit length that produced it — 0.85 on ECFP4 at 2,048 bits is a different population of pairs from 0.85 on a path-based fingerprint at 1,024.

Two practical habits follow. Calibrate the threshold on your own data rather than importing one: take a few thousand random pairs from the library you are searching, plot the distribution of their similarities, and pick the threshold from the tail of that distribution instead of from a paper about a different fingerprint. And report the pair of numbers together — fingerprint specification and threshold — every time, because a colleague reproducing your search with RDKit defaults when you used a path fingerprint at 1,024 bits will get a different neighbour set and no error message.