## Archive for the ‘fingerprint’ tag

## Hashed Fingerprints and RNG’s

In my previous post I looked at how many collisions in bit positions were observed when generating hashed fingerprints (using the CDK 1024-bit hashed fingerprint and the Java hashCode method). I summarized the results in the form of “bit collision plots” where I plotted the number of times a bit was set to 1 versus the bit position (for a given molecule). As expected, for a series of molecules we observe a number of collisions in multiple bits. What was a little surprising was that even for a symmetric molecule like triphenylphosphine (i.e., a relatively small number of topologically unique paths), we observed collisions in two bits. So I decided to look into this case in a little more detail.

As I noted, collisions could occur if **a)** different paths get hashed to the same int or **b)** two different hashes lead to the same random number. Modifying the Fingerprinter code, I was able to generate the list of paths calculated for triphenylphosphine, the hash code for each path and the bit position that was generated for that hash code. The data (hash value, path, bit position) is given below.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | -662168118 P-C:C-H 3 -1466409134 H-C:C-P-C:C:C 58 1279033458 C:C:C:C:C-P-C:C:C 78 1434821739 H-C:C:C:C:C:C 80 -429128489 C:C:C:C-P-C 85 -1779215129 C:C:C:C:C 95 -245205916 H-C:C:C-P-C:C:C:C 97 -475263438 C:C:C:C:C:C-P-C:C 111 -1466409532 H-C:C-P-C:C-H 114 1434821341 H-C:C:C:C:C-H 142 -428753296 C:C:C:C:C:C 161 -245206314 H-C:C:C-P-C:C:C-H 161 1730724873 H-C:C:C-P-C 167 43327460 H-C:C:C:C:C-P-C:C 180 1731099668 H-C:C:C:C-H 180 886716569 H-C:C:C:C 182 -1406488727 C:C:C:C:C-P-C:C 191 78342 P-C 193 1731100066 H-C:C:C:C:C 211 63670037 C:C:C 213 178815835 H-C:C:C:C:C-P-C 224 179190630 H-C:C:C:C:C:C-H 230 -469902821 H-C:C-P-C:C:C:C 244 1057365278 C:C:C:C 253 -181369445 H-C:C:C:C-P-C:C 266 1056990085 C:C-P-C 300 886341376 H-C:C-P-C 333 827737424 H-C:C:C 390 -912402715 P-C:C:C:C:C-H 406 1572927053 H-C:C:C-P-C:C-H 421 1434446546 H-C:C:C:C-P-C 440 403512740 H-C:C:C:C:C:C-P-C 442 827737026 H-C:C-H 448 1572927451 H-C:C:C-P-C:C:C 458 -645296786 P-C:C:C:C:C:C-H 493 -688017645 P-C:C:C-H 503 -763796814 C:C:C:C-P-C:C:C:C 512 66252 C:C 574 75288527 P-C:C 600 -605043036 H-C:C-P-C:C:C:C:C 604 1074261266 H-C:C:C-P-C:C 629 -789313769 C:C:C-P-C:C 639 -2139775602 C:C-P-C:C 675 1370539593 H-C:C-P-C:C 698 284569632 C:C:C:C:C-P-C 702 1797624356 H-C:C:C:C-P-C:C:C 710 63294844 C-P-C 719 -912402317 P-C:C:C:C:C:C 725 72 H 741 67 C 742 80 P 744 -1779590322 C:C:C-P-C 762 1797623958 H-C:C:C:C-P-C:C-H 774 347808169 C:C:C:C-P-C:C:C 788 -688017247 P-C:C:C:C 815 240390684 P-C:C:C:C-H 834 -75615648 C:C:C:C-P-C:C 859 240391082 P-C:C:C:C:C 866 886716171 H-C:C:C-H 888 67900359 H-C:C 951 -1046303447 C:C:C:C:C:C-P-C 957 -662167720 P-C:C:C 969 70654 H-C 971 1678681248 C:C:C-P-C:C:C 979 |

First, all the hash codes are unique. So clearly the issue lies in the RNG and indeed, we see the following two paths being mapped to the same random integer.

1 2 | -428753296 C:C:C:C:C:C 161 -245206314 H-C:C:C-P-C:C:C-H 161 |

Does this mean that the two hash values, when used as seeds to the RNG give the same sequence of random ints? Using the code below

1 2 3 4 5 | Random rng1 = new Random(-428753296); Random rng2 = new Random(-245206314); for (int i = 0; i < 5; i++) { System.out.println(rng1.nextInt(1024) + " " + rng2.nextInt(1024)); } |

we generate the first five random integers and we see that they match at the first value but then differ.

1 2 3 4 5 | 161 161 846 40 317 885 461 535 448 982 |

This suggests that instead of using the first random integer from the RNG seeded by a hash value, we use the second random integer. Modifying the code to do this still gives collisions in two bits. Once again, looking at the paths, hashes and bit positions, we see that now, two different paths get mapped to the same bit position.

1 2 | 886341376 H-C:C-P-C 686 1434821341 H-C:C:C:C:C-H 686 |

As before, we look at the sequence of random ints obtained from RNG’s seeded using these hash values. The resultant sequence looks like:

1 2 3 4 5 | 333 142 686 686 905 1022 70 571 177 384 |

So now, the two sequences match at the second value. OK, so what happens if we take the third value from the sequence and use that as a bit position? We get exactly the same behavior (collisions at two bit positions), except that now, when we look at the sequence of random int’s they match at the third value.

This behavior seems a little strange to me – as if there is a pair of seeds such that the “trajectory” of the sequences generated using those seeds will always (?) intersect at a certain point (where point actually corresponds to the n’th element of the sequences).

May be this is a property of random sequences? Or a feature of the Java RNG. I’d love to hear if anybody has insight into this behavior.

## Path Fingerprints and Hash Quality

Recently, on an email thread I was involved in, Egon mentioned that the CDK hashed fingerprints were probably being penalized by the poor hashing provided by Java’s **hashCode** method. Essentially, he suspected that the collision rate was high and so that the many bits were being set multiple times by different paths and that a fraction of bits were not being touched.

Recall that the CDK hashed fingerprint determines all topologically unique paths upto a certain length and stores them as strings (composed of atom & bond symbols). Each path is then converted to an int via the **hashCode** method and this int value is used to seed the Java random number generator. Using this generator a random integer value is obtained which is used as the position in the bit string which will be set to 1 for that specific path..

A quick modification to the CDK Fingerprinter code allowed me to dump out the number of times each position in the bitstring was being set, during the calculation of the fingerprint for a single molecule. Plotting the number of hits at each position allows us to visualize the effectiveness of the hashing mechanism. Given that the path strings being hashed are unique, a collision implies that **t****wo different paths are being hashed to the same bit position**.

The figure alongside summarizes this for the CDK 1024-bit hashed fingerprints on 9 arbitrary molecules. The x-axis represents the bit position and the y-axis on each plot represents the number of times a given position is set to 1 during the calculation. All plots are on the same scale, so we can compare the different molecules (though size effects are not taken into account).

Visually, it appears that the bit positions being set are uniform randomly distributed throughout the length of the fingerprint. However, the number of collisions observed is non-trvial. While for most cases, there doesn’t seem to be a significant number of collisions, the substituted benzoic acid does have a number of bits that are set 4 times and many bits with 2 or more collisions.

The sparsity of triphenyl phosphine can be ascribed to the symmetry of the molecule and the consequent smaller number of unique paths being hashed. However it’s interesting to note that even in such a case, two bit positions see a collision and suggests that the hash function being employed is not that great.

This is a quick hack to get some evidence of hash function quality and its effect on hashed fingerprints. The immediate next step is to look at alternative hash functions. There are also other aspects of the measurement & visualization process that could be tweaked – taking into account molecular size, the actual number of unique paths and converting the plots shown here to some concise numeric representation, allowing us to summarize larger datasets in a single view.

**Update** – I just realized that the hash function is not the only factor here. The Java random number generator plays an important role. A quick test with the MD5 hash function indicates that we still see collisions (actually, more so than with hashCode), suggesting that the problem may be with how the RNG is being seeded (and the fact that only 48 bits of the seed are used).

## SALI in Bulk

Sometime back John Van Drie and I had developed the Structure Activity Landscape Index (SALI), which is a way to quantify activity cliffs – pairs of compounds which are structurally very similar but have significantly different activities. In preparation for a talk on SALI at the Boston ACS, I was looking for SAR datasets that contained cliffs. It turns out that ChEMBL is a a great resource for SAR data. And with the EBI providing database dumps it’s very easy to query across the entire collection to find datasets of interest.

For the purposes of this talk, I wanted to see what the datasets looked like in terms of the presence (or absence of cliffs). Given that the idea of an activity cliff is only sensible for ligand receptor type interactions, I only considered compound sets associated with binding assays. Furthermore, I only considered those assays which involved human targets, had a confidence score greater than 8 and contained between 75 and 500 molecules. (If you have an Oracle installation of ChEMBL then this SQL snippet will get you the list of assays satisfying these constraints).

This gives us 31 assays, which we can now analyze. For the purposes of this note, I evaluated the CDK hashed fingerprints and used the standardized activities to generate the pairwise SALI values for each of the datasets (performing the appropriate log transformation of the activities when required). The matrices that represent the pairwise SALI values are plotted in the heatmap montage below (the ChEMBL assay ID is noted in each image) where black represents the minimum SALI value and white represents the maximum SALI value for that dataset. (See the original paper for more details on this representation.) Clearly, the “roughness” of the activity landscape differs from dataset to dataset.

At this point I haven’t looked in depth into each dataset to characterize the landscapes in more detail, but this is a quick summary of multiple datasets. (Though a few datasets contain cliffs which are derived from stereoiomers and hence may not actually be real cliffs – since their activity difference may be small, but will look structurally identical to the fingerprint).

An alternative and useful representation is to convert the SALI values for a dataset into an empirical cumulative distribution function to provide a more quantitative view of how cliffs are distributed within a landscape. I’ll leave those details for the talk.

## Benchmarking the CDK Hybridization Fingerprinter

This morning Egon reported that he had implemented a new fingerprinter for the CDK, which only considered hybridization rather than looking at aromaticity. As a result this approach does not require aromaticity perception. I took a quick look to see how it performs in a virtual screening benchmark. Firstly, it’s faster than the other CDK hashed fingerprints – 15,030 fingerprint calculations took ~ 60s with the hybridization only fingerprint. In contrast the extended fingerprint took 80s for the same set of molecules. To test the utility of the fingerprint in a virtual screening scenario I evaluated enrichment curves (see here for a comprehensive comparison of CDK fingerprints) using the AID 692 MUV benchmark dataset. The plots below show the enrichment curves for the first 5% of the database and the entire database. The red curve corresponds to random selections. (In this experiment the database consists of 15,000 decoys and 30 actives). The enrichment factor for the standard, extended and hybiridization only fingerprints were 0.94, 1.06 and 1.38 respectively.

Overall, the hybridization only fingerprint performs comparably to the extended fingerprint and better than the standard one. But at a small percentage of the database screened, it appears that this fingerprint outperforms both. Of course, this is only one dataset, and more MUV datasets should be analyzed to get a more comprehensive view.

## Update to the fingerprint Package

I’ve just uploaded a new version of the fingerprint package (v3.3) to CRAN that implements some ideas described in Nisius and Bajorath. First, the **balance** method generates “balanced code” fingerprints, which given an input fingerprint of N bits, returns a new fingerprint of 2N bits, such that the bit density is exactly 50%. Second, **bit.importance** is a method to evaluate the importance of each bit in a fingerprint, in terms of the Kullback-Liebler divergence between a collection of actives and background molecules. In other words, the method ranks the bits in terms of their ability to discriminate between the actives and the background molecules.