Fingerprints in the RDKit
Gregory Landrum
NIBR IT
Novartis Institutes for BioMedical Research
Basel
RDKit UGM 2012, London

Molecular Fingerprints§ Idea : Apply a kernel to a molecule to generate a bit vector or countvector (less frequent)...

§ Typical kernels extract features of the molecule, hash them, and use
the hash to determine bits that should be set§ Typical fingerprint sizes: 1K-4K bits.

Calculating similarity between fingerprints§ Most common approach is Tanimoto similarity:Vi •VjTani(Vi ,Vj ) =∑Vib + ∑Vjb −Vi •Vjbb§ Shorthand for that:Tani(Vi,Vj) = |Vi&Vj| / (|Vi| + |Vj| - |Vi&Vj|)§ A more general form, Tversky similarity:
Tversky(Vi,Vj,a,b) = |Vi&Vj| / (a*|Vi| + b*|Vj| + (1-a-b)*|Vi&Vj|)§ Tani(Vi,Vj) = Tversky(Vi,Vj,1,1)§ Dice(Vi,Vj) = Tversky(Vi,Vj,0.5,0.5)
These metrics and others are described and compared here:
JW Raymond, P Willett JCAMD 16:59-71 (2002)

Fingerprint similarity == molecule similarity?
§ Each fingerprint bit corresponds to a fragment of the molecule...

§ Assumption: molecules that are similar have a lot of fragments incommon§ No “right” answer for defining similarity: there’s no canonical definitionof “molecular similarity”§ Lots of experience shows that the best fingerprint for activities likevirtual screening (finding active similar molecules in a database)depends strongly on the data set.
§ So: there are many different fingerprints available

Substructure Searching§ Find a subgraph isomorphism between two molecules (or: find whetheror not an isomorphism exists)

X§ Problem is NP complete, but there are clever algorithms and heuristics
to make it tractable (e.g. vf2)
Cordella, L.P., Foggia, P., Sansone, C. & Vento, M. A (sub)graph isomorphism algorithm for matchinglarge graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 1367-1372 (2004).
Ehrlich, H.-C. & Rarey, M. Systematic benchmark of substructure search in molecular graphs - FromUllmann to VF2. J Cheminf 4, 13 (2012).

Substructure Searching at Scale using Fingerprints§ Problem: Practical SSS algorithms work for small numbers of searches,
but are too slow for general database querying§ Solution: Use a fingerprinting algorithm to minimize the number of calls
to the subgraph isomorphism library:

Molj is a subgraph of Moli if and only if every bit set in FPj is also set in FPi (i.e. |FPj&FPi| == |FPj|)§ Places severe constraints on the nature of the fingerprinting algorithm§ The more accurate this fingerprint-based screenout is, the faster theoverall substructure search will be“RDKit” fingerprints

yet another implementation of a Daylight-like fingerprint§§§§

Substructure fingerprint
Atom types: set by atomic number and aromaticity
Bond types: set by atom types and bond types
Algorithm:
For each subgraph (or path, if branchedPaths is false) of length minPathmaxPath bonds:
1. generate hash for the path using bond types and each bond’s neighborcount
2. seed random-number generator with hash
3. generate nBitsPerHash random numbers between 0 and fpSize and set
the corresponding bits
4. [optional]: “fold” fingerprint to target density of tgtDensity of bits set(minimum size minSize bits)

RDKit layered fingerprints

An alternate subgraph-hashing scheme§

Substructure fingerprint if appropriate layers are used§

Atom and bond types: contributions determined by which layers areincluded§

Layers:§•

0x01: pure topology•

0x02: bond order•

0x04: atom types (atomic number)•

0x08: presence of rings•

0x10: ring sizes•

0x20: aromaticity

Algorithm: same as RDKit fingerprintRDKit layered fingerprint 2

An experimental substructure fingerprint§Substructure fingerprint§Use a set of pre-defined generic substructure patterns§Algorithm:
1.

Find all mappings of each pattern onto the molecule2.

Hash the subgraph defined by that mapping using atom numbers and set a bit

3.

Hash the subgraph defined by that mapping using bond types and set a bit

Avalon Fingerprints

P. Gedeck, B. Rohde, C. Bartels J. Chem. Inf. Model.
46:1924-36 (2006)

highly optimized in-house fingerprint§Substructure or similarity fingerprint (depending on flags)§Handles query features well (when built from a CTAB)§Part of the avalon toolkit•

https://sourceforge.net/projects/avalontoolkit/•

Optionally useable from within the RDKitAvalon Fingerprints
terms

P. Gedeck, B. Rohde, C. Bartels J. Chem. Inf. Model.
46:1924-36 (2006)

Atom-Pair and Topological-Torsion Fingerprints
related descriptors from the distant past§ Similarity Fingerprint§ Atom-type:

C_3_1(Element, #heavy neighbors, #pi electrons)

N_2_1 N§ Atom Pair1:
Atom-type – topological distance – Atom-type

C_3_0

C_1_0

C_2_1N_2_1 - 2 - C_3_1
N
C_2_1 - 5 - C_1_0

N§ Topological Torsion2:
Atom-type – Atom-type – Atom-type – Atom-type

N_2_1 - C_2_1 - C_3_1 - C_3_0

NN

C_2_1 - C_2_1 - C_3_1 - C_3_0

1 R.E. Carhart, D.H. Smith, R. Venkataraghavan JCICS 25:64-73 (1985)
2 R. Nilakantan, N. Bauman, J. S. Dixon, R. Venkataraghavan; JCICS 27:82-5 (1987).

Morgan/Circular Fingerprints
new and popular§ Similarity fingerprint§ Atom types :• Connectivity: (Element, #heavy neighbors, #Hs, charge, isotope, inRing )• Chemical features: Donor, Acceptor, Aromatic, Halogen, Basic, Acidic§ Fingerprint takes into account the neighborhood of each atom:NNNradius=1

NNN

radius=2§ Typical radii: 0-3 bonds
Rogers, D. & Hahn, M. Extended-Connectivity Fingerprints. J. Chem. Inf. Model. 50,742-754 (2010).

Morgan/Circular Fingerprints
Chemical Feature definitions§ Adapted from A. Gobbi, D. Poppinger Biotech and Bioeng 61:47-54(1998)

Donor[$([N;!H0;v3,v4&+1]),\$([O,S;H1;+0]),\n&H1&+0]

Acceptor[$([O,S;H1;v2;!$(*-*=[O,N,P,S])]),\$([O,S;H0;v2]),\$([O,S;-]),\$([N;v3;!$(N-*=[O,N,P,S])]),\
n&H0&+0,\$([o,s;+0;!$([o,s]:n);!$([o,s]:c:n)])]Aromatic[a]

Halogen[F,Cl,Br,I]

Basic[#7;+,\$([N;H2&+0][$([C,a]);!$([C,a](=O))]),\$([N;H1&+0]([$([C,a]);!$([C,a](=O))])[$([C,a]);!$([C,a](=O))]),\$([N;H0&+0]([C;!$(C(=O))])([C;!$(C(=O))])[C;!$(C(=O))])]

Acidic[$([C,S](=[O,S,P])-[O;H1,-1])]

https://sourceforge.net/p/rdkit/code/2174/tree/trunk/Code/GraphMol/Fingerprints/MorganFingerprints.cpp

2D Pharmacophore Fingerprints
another "blast from the past"§ Identify feature points in a molecule§ Calculate inter-feature topologicaldistances§ Assign bit id to feature – distancecombination§ Can be stored as counts or bits
§ Feature definitions and distance bins
are user-definable

HAcc

HAcc
OON

AromOH44

AcidArom

HAccOHAccON

4

6OH

AromAromArom

One set of useful feature definitions:
A. Gobbi, D. Poppinger Biotech and Bioeng 61:47-54 (1998)

4Acid2Arom

2D Pharmacophore Fingerprints
Supplemental : features + distances -> bit ids

2D Pharmacophores§ Gobbi2d [A. Gobbi, D. Poppinger Biotech and Bioeng 61:47-54 (1998)]• Features (from paper):- Hydrophobic: [$([C;H2,H1](!=*)[C;H2,H1][C;H2,H1][$([C;H1,H2,H3]);!$(C=*)]),$(C([C;H2,H3])([C;H2,H3])[C;H2,H3])]- Donor: [$([N;!H0;v3]),$([N;!H0;+1;v4]),$([O,S;H1;+0]),$([n;H1;+0])]- Acceptor: [$([O,S;H1;v2]-[!$(*=[O,N,P,S])]),$([O,S;H0;v2]),$([O,S;-]),$([N&v3;H1,H2]-[!$(*=[O,N,P,S])]),$([N;v3;H0]),$([n,o,s;+0]),F]- AromaticAttachment: [$([a;D3](@*)(@*)*)]- AliphaticAttachment: [$([A;D3](@*)(@*)*)]- UnusualAtom: [!#1;!#6;!#7;!#8;!#9;!#16;!#17;!#35;!#53]- BasicGroup: [$([N;H2&+0][$([C,a]);!$([C,a](=O))]),$([N;H1&+0]([$([C,a]);!$([C,a](=O))])[$([C,a]);!$([C,a](=O))]),$([N;H0&+0]([C;!$(C(=O))])([C;!$(C(=O))])[C;!$(C(=O))]),$([N,n;X2;+0])]- AcidicGroup: [$([C,S](=[O,S,P])-[O;H1])]• Distance bins (GL): [(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,100)]• "fuzzing" from original paper not done§ Pharm2d:• Feature definitions from BaseFeatures.fdef :Donor, Acceptor, NegIonizable, PosIonizable, ZnBinder, Aromatic, Hydrophobe,LumpedHydrophobe• Distance bins: [(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,100)]

Comparing fingerprints§ Pick 10K random pairs of vendor compounds that have at least some
topological similarity to each other (Avalon similarity >= 0.5)
§ Compare similarities calculated with Pipeline Pilot and the RDKit

Comparing fingerprints§ RDKit Morgan2 vs PP ECFP4

Larger differences are mostly
aromaticity related§ RDKit Morgan3 vs PP ECFP6 is similarComparing fingerprints§ RDKit FeatMorgan2 vs PP FCFP4

Differences are due to feature definitions
84% of similarities differ by <0.05
95% differ by <0.1

Simulating count-based fingerprints§ Sometimes it makes sense to count the number of times a featureappears instead of simply that it appears -> count-based fingerprints§ “Dice” similarity for count-based fingerprints:

Sim(Vi ,V j ) =2.0 *∑ min(Vib ,V jb )b

∑ Vib + ∑ V jbbb

§ Problem: count vectors take up more disk space/memory than bitvectors and similarity calculations using count vectors are slower.
§ Partial solution: simulate counts1 2by
4 8including multiple bits per feature:0 bits1 bits2 bits3 bits6 bitsSimulating count-based fingerprints
How well does it work?

§ Dataset: 20K pairs of “drug like” commercial compounds selected tohave a minimum topological similarity (based on Avalon fingerprint)§ Compare unhashed count-based topological-torsion fingerprint to ahashed bit vector version
#bits

99%

95%

90%

80%

4096

0.13

0.09

0.07

0.05

2048

0.130.09

0.07

0.05

1024

0.14

0.10

0.08

0.06

512

0.16

0.12

0.10

0.07

SSS Screening performance of fingerprints§ Database: 20K diverse ZINC drug-like molecules§ "Fragments" queries: 500 diverse fragment-like molecules from ZINC
§ "Leads" queries: 500 diverse lead-like molecules from ZINC
§ “Pieces” queries: 823 pieces constructed by doing a BRICS
fragmentation of a set of molecules from the pubchem screening set.
Size range from 1->64 atoms§ Metric: what fraction of the fingerprint matches actually are substructure
matches| fp| zinc_frags | zinc_leads | pubchem_pieces || avalon|
0.13 |
0.22 |
0.41 || layered |0.08 |
0.10 |
0.35 || layered2 |0.78 |
0.26 |
0.64 |
Expt date: 07.07.2012