• About Me
  • Brief CV

Asad's Blog

~ Man and his will to survive!

Asad's Blog

Tag Archives: hashed fingerprints

Shortest Path and Molecular Hashed Fingerprints

23 Monday Jul 2012

Posted by chembioinfo in CDK, Java, Similarity, Work

≈ 7 Comments

Tags

atoms, bonds, CDK, Fingerprints, graph, hash, hashed fingerprints, Java, molecule, network, shortest path, Small Molecule

Shortest Path (SP) has been used in many aspects of graph traversing. The idea is to minimise the cost (number of edges to be traversed or the cost on the edge) of traveling between a source and destination. This is one of the most optimal ways of finding a path in the graph where you can generate a combination of paths using random walk.

Interestingly, generation of path based hashed fingerprint is very common in the area of chemo-informatics. The basic idea is to find all paths of a certain length from the source atom (fragments) in a molecule and convert it into a hashed fingerprint. This works very well with smaller or sparsed graphs, although in a few cases the run time may increase exponentially with the size of the graph (connectivity). The Chemistry Development Kit (CDK) has one such effective path based hashed fingerprint generator (Fingerprinter.java). This module in the CDK has generated a lot of interest from the user community. Recently, Nina Nikolova – Jeliazkova posted an interesting set of molecules were the path search in the fingerprint was hit by combinatorial explosion!

Note: The behaviour of the path finding algorithm is compromised once the depth of the path search is more than 6 (the recommended depth is 8). Hence for these set of molecules one may not be able to find the fingerprints.

Here are the exemplar molecules where the present CDK hashed fingerprint is subdued.

git://gist.github.com/3163031.git

I have modified the existing CDK fingerprinter to report the shortest path rather than all paths. This overcomes the problem of combinatory explosion and runtime is no longer exponential as compared to previous case.

Here is the runtime and the density of the FP  (number of bit occupied) as calculated by the SP based FP. One can deduce the runtime and density by half if the FP is only based either on weighted or unweighted bonds. In the modified SP based FP, I have used both weighted and unweighted bonds to give better consensus FP (more in my next blog!).

Here is the code.

https://github.com/asad/ShortestPathMoleculeFingerprinter

Challenges:

a) Presently the fingerprint accounts for only one shortest path between a source and the sink atom (discriminates between aromatic, ring and aliphatic paths). Hence, I had to canonicalize the atoms in the graph container such that if two molecules are similar then the returned SP path is same. A natural extension would be to report k-shortest path but this maybe as good as CDK default fingerprinter (in terms of the runtime).

b) For spare graph and smaller graphs it might be as fast as the previous implementation, and it will perform better on complex graphs.

c) My present implementation is an extension of my previous work on the CDK fingerprinter where rings search and other optimizations has been done.

Edited: 6th August 2012

Here is a test case based on the ring systems (aromatic and non aromatic) and aliphatic molecules.

Updated: 29th Aug 2012

Thanks to Egon for his suggestions to use SP2 hybridization instead of aromaticity checker. In my case I have to use CDK aromaticity detection as SP2 concept may not work.

I have clustered 11 molecules based on their fingerprint similarity scores using the

a) CDK default finprinter,

b) SP based Fingerprinter and

c) CDK Hybridization Fingerprinter

The clustered results are as shown below.

The CDK default fingerprinter based similarity clusters

The CDK default fingerprinter based similarity clusters

The Shortest path fingerprinter based similarity clusters

The Shortest path fingerprinter based similarity clusters

Molecule similarity clusters based on the Hybridization Fingerprinter

Molecule similarity clusters based on the Hybridization Fingerprinter (doesn’t discriminate between open and close ring system)

The Hybridization based fingerprinter is the fastest one (in the non-complex cases), followed by the SP fingerprinter and improved CDK fingerprinter. In terms of the sensitivity and specificity, SP fingerprinter is the best and in complex cases its by far the fast one!

I will leave it to the readers to choose their favorite fingerprinter.

Kindly leave your comments and suggestions!

Share this:

  • Email
  • Print
  • Facebook
  • Twitter
  • LinkedIn
  • Google
  • Reddit

Like this:

Like Loading...

Improved CDK Hashed Fingerprinter

04 Friday Nov 2011

Posted by chembioinfo in CDK, Java, Similarity, SMSD, Substructure

≈ 4 Comments

Tags

CDK, hashCode(), hashed fingerprints, Isomorphism, Java, KEGG, Mersenne Twister, Random(), Similarity, SMSD, substructure, Tanimoto, VF2

Edited: 4th Nov, 10:20 AM

In my previous post, I discussed the impact of the hashcode and random number generators on a hashed fingerprint. They play a major role in the uniform distribution of the bits in a fixed length array and the occurrence of the bit clashes. In order to prove the concept, I have prepared a test case of 1200 molecules and preformed a substructure search using the default CDK Fingerprinter class and its improved Fingerprinter class version (with the Apache math librarys HashCodeBuilder() method and Mersenne Twister random number generator).

Each molecule was searched against other molecules in the dataset including itself. This was done at an interval of 200 data points. The gold standard was the substructure search results from the SMSD.

Accuracy of the Fingerprints

New Fingerprinter has better accuracy (red line) than the CDK Fingerprinter (low FPR too!)

As expected the improved version of the Fingerprinter class outperformed the present CDK Fingerprinter class. The number of false positives (FP) were reduced by 35-40% (due to minimal bit clashes) thereby increasing the accuracy of the results, while the true positives remained unchanged. This also made an overall positive impact on the speed of the search results!

The raw results and the Fingerprinter code is available via my github account https://github.com/asad/CDKHashFingerPrint.

The present code can further be optimised for lowering the number of false positives.

Thus a better hashcode and random number generator leads to an improved hashed fingerprint.

Share this:

  • Email
  • Print
  • Facebook
  • Twitter
  • LinkedIn
  • Google
  • Reddit

Like this:

Like Loading...

Revisiting Molecular Hashed Fingerprints

30 Sunday Oct 2011

Posted by chembioinfo in Atom Typing, CDK, Java, Similarity, Substructure, Work

≈ 1 Comment

Tags

Atom typing, bitset, circular fingerprints, Fingerprints, hashCode(), hashed fingerprints, hashing, Java, Mersenne Twister, molecular signatures, Random(), rings, RNG's, Similarity, SMARTS, stereo, subfingerprints, substructure

Introduction

Fingerprints have been widely used in various fields to find similar features. Now for those of you who are using their detective instincts and aiming for DNA fingerprint or biological fingerprints, I might disappoint you in the later half of my post. Fingerprints are typically used to avoid cumbersome data comparison by using shorter “bit” string. My focus will be on the molecular fingerprints which have been used by chemo/bio informatician for finding similar molecular structures i.e. finding a needle in a hay stack! Theoretically, if you know the prerequisite features of “should have and not have” in the target molecules, then you can use a set of predefined keys to generate fingerprints. For examples PubChem fingerprint, MACCS keys etc. are based on certain substructure/SMARTS keys which are expected to be found or skipped in your target. On the other hand when we play with unknowns both at the level of query and target then one of the fastest ways to go for the kill is hashed fingerprints. Typically, in a hashed fingerprint a set of patterns are generated by gathering atom environment information or subgraph information or both. The generated patterns are then transformed into hash codes (a fixed size message digest) using hashing algorithm in computer science. These hash codes can then transformed into bit strings using random number generation of a defined length (size of the fingerprint). The presence and the absence of a pattern is marked as “1” and “0” respectively.

Pros:

  • Hashed fingerprints are like a black box with an assurance that similar patterns will have similar bits set to “1”. In the language of information science you are allowing clashes of the similar bits with certain probability.
  • The size of the generated fingerprints can be controlled by the user as predefined knowledge of the fingerprint patterns are not required.
Cons:
  • The resolution of the fingerprints depends on algorithms used for generating the hash code and random numbers.
  • It’s challenging to find a perfectly sized fingerprints which can strike a balance between minimising the clashes of bitsets and wastage of the bit space.

Implementation

Let’s play with some real-time examples to understand the depth of the above mentioned statements. Now we need to generate some patterns from molecules and store them as fingerprints. In order to analyse the quality of the fingerprints we will open the black box by keeping track of the generated pattern types. This will help us to quantify the patterns involved in the bitset clashes. The circular fingerprint or molecular signatures can be used to generate patterns of various diameter/height for a molecule. By increasing the diameter/height, we can enrich the patterns/information about the molecules. However, this will also increase the overhead of balancing the fingerprint size and reducing the bit clashes.

Stage 1: Generate patterns using molecular signatures of heights 0 to 3 for every atom in the molecule. An example is illustrated in the figure below.

Circular / Signatures patterns encoded as fingerprints
Circular / Signatures patterns encoded as fingerprints

Stage 2: Transform these patterns as SMARTS/SMILES/Signatures and generate hash code for each pattern using your favourite algorithm.

Stage 3: Once we have the hash codes for these patterns then using random number generator, convert these hash codes into bit set bucket with a fixed range (eg. 1024).

I have used the CDK to generate molecular signatures (σ) of various heights (0 to 3) for 5000 mols. These signatures were transformed into canonical SMILES and hash code was generated using Java Apache math library HashCodeBuilder() method (better than default java hashCode() due to the flexibility). Well, you could use any method you like as long as equal objects produce same hash code and unequal objects produce distinct hash codes. Some of the most common hash code generation algorithms are MD5, SHA, PJW (Peter Weinberger’s hash) etc. The choice is made on the basis of data distribution (balance between random generation vs pattern in generation) and hashing function efficiency (should be very quick, stable and deterministic).

Now the tricky part is the conversion of hash codes into a fingerprint. I have used the famous Mersenne Twister random number generator. This yields better results than default java Random() method in terms of minimising the bit clashes and maximizing the bit set resolution.

Here are few statistical measure regarding the patterns generated and encoded into fingerprint bitsets.

Statistical Measure (5000 mols) Height 0 Height 1 Height 2 Height 3
Unique Pattern Count (UPC) 53 426 4083 14448
Average number of patterns/fingerprint 3.09 +/- 1.04 10.34 +/- 5.82 15.16 +/- 10.01 17.01 +/- 13.07
Median number of patterns/fingerprint 3 9 13 13
Max. number of patterns/fingerprint 7 35 64 89

In order to understand the resolution of the fingerprints with respect to the bit clash and size of the fingerprints, I generated fingerprints of various sizes (ranging from 128 to 8192 bits). The fingerprint size 1024 bits seems like a good bet for signatures of height up to 2 (as marked in the graph below), while 4096 stands good for signature of height 3 (more than 95% bitsets are used and lesser % of bits clash).

BitSet usage vs Bit Clash in the hashed fingerprints
BitSet usage vs Bit Clash in the hashed fingerprints

Analysis

From the above figure, it is clear that one of the key improvements which can be made in the hashed fingerprints is to divide it into sub-fingerprints. Then each sub-fingerprint can be populated with certain chemical/subgraph property of the molecule. Say in the case of molecular fingerprint of size 1024 bitset, one can divide the fingerprints into two sub-fingerprints –

a) One of 256 bits for storing labelled atom types and,

b) The second, of 768 bits for graph/topological information.

The hash code from the atom typed section is the depiction of concatenated labelled string of the CDK atom types + presence of atom in a ring system + stereo for each atom in a molecule (you could choose your own physiochemical labelling schema). The signatures/graph section can be populated with signatures/circular fingerprints of height/diameter 2. The Sub-fingerprints are easy to achieve and store with the above mentioned process due to the flexibility of generating hash codes within a range. The idea is to get the best of both the worlds i.e. physiochemical properties and subgraph patterns.

Conclusion

The quality of the hashed fingerprint depends a lot on the patterns generated (UPC), size of the bitsets, hashing function and random number generator. Next step for me would to cluster these similarity matrices or perform Leave One Out test on the dataset to check the specificity and sensitivity of the model.

References:

Further reading and reference therein will give you more insight into the story:

  1. jCompoundMapper: An open source Java library and command-line tool for chemical fingerprints
  2. Hashed Fingerprints and RNG’s
  3. Molecular fingerprints, background
  4. Fingerprints – Screening and Similarity
  5. Lossless Compression of Chemical Fingerprints Using Integer Entropy Codes Improves Storage and Retrieval
  6. Extended-Connectivity Fingerprints
  7. more…..
Please feel free to make suggestions and leave your thoughts/comments.

Share this:

  • Email
  • Print
  • Facebook
  • Twitter
  • LinkedIn
  • Google
  • Reddit

Like this:

Like Loading...

Subscribe

  • Entries (RSS)
  • Comments (RSS)

Archives

  • August 2015
  • December 2014
  • March 2014
  • February 2014
  • July 2012
  • April 2012
  • November 2011
  • October 2011
  • September 2011
  • August 2011
  • July 2011
  • June 2011
  • April 2011
  • March 2011
  • April 2010
  • December 2009

Categories

  • EC-BLAST
  • General
    • Food
    • Life
  • Work
    • CDK
      • Atom Typing
    • Enzymes
      • Similarity
    • Java
    • SMSD
    • Substructure

Meta

  • Register
  • Log in

Top Posts & Pages

  • How are enzymes classified?
  • Ultra Fast substructure search based on the VF2 outperforms CDK UIT
  • EC-BLAST: A Novel Tool for Finding Chemically Similar Enzymes
Follow Asad's Blog on WordPress.com

Enter your email address to follow this blog and receive notifications of new posts by email.

Recent

  • A Romance between Biology and Chemistry – Protein Sequences, Molecules and Enzyme function! August 15, 2015
  • ChemBLAST: Old dog new tricks December 31, 2014
  • Atom Atom Mapping (AAM) and Challenges March 18, 2014
  • EC-BLAST Tutorial for Hands-on Training February 4, 2014
  • Shortest Path and Molecular Hashed Fingerprints July 23, 2012

Archives

Tags

Atom typing bitset BRENDA CDK chemaxon circular fingerprints EBI EC Number Enzyme Classification Fingerprints hashCode() hashed fingerprints Indian Isomorphism IUBMB enzyme nomenclature Java join Structures KEGG MACiE MCS Mersenne Twister Random() Reaction Reaction Similarity Similarity Small Molecule SMSD substructure Tanimoto VF2

Blogroll

  • Andrew Dalke
  • ChEMBL
  • Christoph Steinbeck
  • Egon Willighagen
  • Gilleain Torrance
  • Joerg Kurt Wegner
  • Niyaz Ahmed
  • Noel O'Blog
  • Rajarshi Guha
  • Richard Apodaca

RSS Asad’s Blog

  • A Romance between Biology and Chemistry – Protein Sequences, Molecules and Enzyme function! August 15, 2015
    Next Generation Sequencing (NGS) data is knocking at our door and simultaneously, our ability to design novel enzymes (rational design or directed …Continue reading →
    chembioinfo
  • ChemBLAST: Old dog new tricks December 31, 2014
    Updated:07/01/2015 BLAST-Basic Local Alignment Tool was born in the 1990s (1,2) and has since been the bread and butter of …Continue reading →
    chembioinfo
  • Atom Atom Mapping (AAM) and Challenges March 18, 2014
    We have just released our long awaited AAM tool in the public domain…this was long over due! You can download the tool from …Continue reading →
    chembioinfo
  • EC-BLAST Tutorial for Hands-on Training February 4, 2014
    EC-BLAST Tutorial for Hands-on Training Publication:  EC-BLAST: a tool to automatically search and compare enzyme reactions, SA Rahman, SM Cuesta, N …Continue reading →
    chembioinfo
  • Shortest Path and Molecular Hashed Fingerprints July 23, 2012
    Shortest Path (SP) has been used in many aspects of graph traversing. The idea is to minimise the cost (number …Continue reading →
    chembioinfo
  • EC-BLAST: A Novel Tool for Finding Chemically Similar Enzymes April 11, 2012
    Enzymes have been part of our evolutionary machinery and it’s importance is ever increasing in our life. An enzymatic hierarchal …Continue reading →
    chembioinfo
  • Improved CDK Hashed Fingerprinter November 4, 2011
    Edited: 4th Nov, 10:20 AM In my previous post, I discussed the impact of the hashcode and random number generators …Continue reading →
    chembioinfo
  • Revisiting Molecular Hashed Fingerprints October 30, 2011
    Introduction Fingerprints have been widely used in various fields to find similar features. Now for those of you who are …Continue reading →
    chembioinfo
  • Thread safe SMSD September 14, 2011
    How can I run SMSD using Java Thread….is SMSD thread safe? The short answer is “YES” you can. Here is …Continue reading →
    chembioinfo
  • Indian Style Ginger Tea August 20, 2011
    Ingredients: 3 tsp. of Tea Leaves (you can use the Indian tea bags if preferred…Assam/Darjeeling etc) ½” piece of Ginger crushed …Continue reading →
    chembioinfo
I Voted

Top Posts & Pages

  • How are enzymes classified?
  • Ultra Fast substructure search based on the VF2 outperforms CDK UIT
  • EC-BLAST: A Novel Tool for Finding Chemically Similar Enzymes
Follow Asad's Blog on WordPress.com

Enter your email address to follow this blog and receive notifications of new posts by email.

Recent

  • A Romance between Biology and Chemistry – Protein Sequences, Molecules and Enzyme function! August 15, 2015
  • ChemBLAST: Old dog new tricks December 31, 2014
  • Atom Atom Mapping (AAM) and Challenges March 18, 2014
  • EC-BLAST Tutorial for Hands-on Training February 4, 2014
  • Shortest Path and Molecular Hashed Fingerprints July 23, 2012

Archives

Tags

Atom typing bitset BRENDA CDK chemaxon circular fingerprints EBI EC Number Enzyme Classification Fingerprints hashCode() hashed fingerprints Indian Isomorphism IUBMB enzyme nomenclature Java join Structures KEGG MACiE MCS Mersenne Twister Random() Reaction Reaction Similarity Similarity Small Molecule SMSD substructure Tanimoto VF2

Blogroll

  • Andrew Dalke
  • ChEMBL
  • Christoph Steinbeck
  • Egon Willighagen
  • Gilleain Torrance
  • Joerg Kurt Wegner
  • Niyaz Ahmed
  • Noel O'Blog
  • Rajarshi Guha
  • Richard Apodaca

RSS Asad’s Blog

  • A Romance between Biology and Chemistry – Protein Sequences, Molecules and Enzyme function! August 15, 2015
    Next Generation Sequencing (NGS) data is knocking at our door and simultaneously, our ability to design novel enzymes (rational design or directed …Continue reading →
    chembioinfo
  • ChemBLAST: Old dog new tricks December 31, 2014
    Updated:07/01/2015 BLAST-Basic Local Alignment Tool was born in the 1990s (1,2) and has since been the bread and butter of …Continue reading →
    chembioinfo
  • Atom Atom Mapping (AAM) and Challenges March 18, 2014
    We have just released our long awaited AAM tool in the public domain…this was long over due! You can download the tool from …Continue reading →
    chembioinfo
  • EC-BLAST Tutorial for Hands-on Training February 4, 2014
    EC-BLAST Tutorial for Hands-on Training Publication:  EC-BLAST: a tool to automatically search and compare enzyme reactions, SA Rahman, SM Cuesta, N …Continue reading →
    chembioinfo
  • Shortest Path and Molecular Hashed Fingerprints July 23, 2012
    Shortest Path (SP) has been used in many aspects of graph traversing. The idea is to minimise the cost (number …Continue reading →
    chembioinfo
  • EC-BLAST: A Novel Tool for Finding Chemically Similar Enzymes April 11, 2012
    Enzymes have been part of our evolutionary machinery and it’s importance is ever increasing in our life. An enzymatic hierarchal …Continue reading →
    chembioinfo
  • Improved CDK Hashed Fingerprinter November 4, 2011
    Edited: 4th Nov, 10:20 AM In my previous post, I discussed the impact of the hashcode and random number generators …Continue reading →
    chembioinfo
  • Revisiting Molecular Hashed Fingerprints October 30, 2011
    Introduction Fingerprints have been widely used in various fields to find similar features. Now for those of you who are …Continue reading →
    chembioinfo
  • Thread safe SMSD September 14, 2011
    How can I run SMSD using Java Thread….is SMSD thread safe? The short answer is “YES” you can. Here is …Continue reading →
    chembioinfo
  • Indian Style Ginger Tea August 20, 2011
    Ingredients: 3 tsp. of Tea Leaves (you can use the Indian tea bags if preferred…Assam/Darjeeling etc) ½” piece of Ginger crushed …Continue reading →
    chembioinfo
I Voted

Blog at WordPress.com.

Cancel
loading Cancel
Post was not sent - check your email addresses!
Email check failed, please try again
Sorry, your blog cannot share posts by email.
%d bloggers like this: