Solutions to IT problems

Solutions I found when learning new IT stuff

Posts Tagged ‘cheminformatics

Creating a Framework for Chemical Structure Search – Part 4

leave a comment »

Series Overview

This is Part 4 – Component Selection of the “Creating a Framework for Chemical Structure Search“-Series.

Previous posts:



Finally I will start with the actual creation of the framework. In this part I will introduce the main components (existing 3rd party frameworks and libraries) I use and briefly explain my choices. At this point I think it is fair to mention that my work was basically integrating different existing software components into my desired end-product while taking into account real-world problems and offering a solution for them. There are no new magic algorithms in chemical structure searching, modeling or drug discovery to be found here!

My first try

In my previous effort at creating a framework for chemical structure search, I thought being platform independent, especially regarding the used relational database management system (RDBMS), is an important aspect. Therefore I relied on doing the chemical structure search in the application and not the database. However it is exactly that part that lead to huge performance and efficiency problems. I had to do some stuff that just felt wrong and “hacky” to get usable performance.

Encountered issues with Application-based Substructure Search

Object Creation Performance

The first issue was, that for every structure search, all the structures (molfiles) passing the fingerprint screen had to be loaded from the database and converted to an IAtomContainer Object from the Chemistry Development Kit. It was the creation of these objects that was very CPU intensive. This was due to the fact that you had to detect aromaticity and similar things for every AtomContainer object. I found the solution for this in OrChem, a free cartridge for Oracle based on the CDK. The creators seemed to have the exact same issue and came up with their custom format. That format stored everything required like aromaticity and so forth in a CDK-specific way so the creation of IAtomContainers was not an issue anymore.

Substructure Search Performance

The second issue was the mediocre performance of the substructure search itself. The solution was a complex approach using multi-threading and queues. The first thread screened all structures using the pre-generated fingerprints. Fingerprints were stored in the database but loaded into memory on application start. If a structure passed the screen it’s database id was put into a queue. A second thread reads form that queue, loaded the molfile from database and generated the IAtomContainer and put them into a second queue. Then there were multiple threads (configurable amount) that took the AtomContainers from the queue and did the actual test for subgraph isomorphism. Again, if a structure passed this phase too, it’s database id was put into the output queue and the AtomContainer discarded. This last step was required because AtomContainers are memory hogs and you had to control somehow how many there were in memory at any time.

CPU load now easily reached 100% for seconds during substructure searches. I then realized that the database alone could easily use 20% or more of that probably due to loading all the structures form it. So I added the option to hold the custom format from OrChem in memory ( not big of an issue actually in terms of memory consumption) to reduce load on database and hence use those CPU cycles for substructure search. I guess you have long figured out how convoluted this all was. But it actually worked amazingly well! Because the hits were put into a queue it was easily possible to display the first say 5 hits on a web page while the search continued in the background. So you could give the impression of a very fast search!

Why start from scratch again?

So why change it? Tons of reasons. All of this was done with plain JDBC and various kinds of data transfer objects. Tight-Coupling and maintainability was a serious issue. On the application side of things it was impossible to sort the results because hits are returned somewhat randomly and hence real paging was not possible either. The second thing was how could you search for a substructure and a numeric property at the same time? Well the solution for that was, that one of the substructure search methods had a Set-argument. The Set should contain the database ids of the structures the search should be performed over. Hence do an SQL query for the numeric property first and feed the ids into the substructure search. That worked but again, not very straight forward. Adding and using such custom properties to the database was rather messy too, it lacked proper transaction support and so forth. All in all it was nothing to be proud of and certainly not usable in a real production environment. I did however learn a lot about the Java 5 concurrency package.

Component for Substructure Search

I decided that being dependent on a specific RDBMS is a minor issue compared to above outlined problems. I already knew about the open-source Bingo Cartridge and to my luck the company behind it was developing a version for PostgreSQL. So my choice of this component was easy. Use PostgreSQL with Bingo, both are free and open-source.

Application-side Chemistry toolkit

Especially for Input-output the framework required a Chemistry Toolkit and I again chose the Chemistry Development Kit CDK.


While it would be preferable to be independent of the ORM, I wasn’t able to achieve that but I admit I did not but much effort in it. MoleculeDatabaseFramework uses JPA 2.0 and hibernate as it’s JPA provider. The part that is hibernate specific is the custom SQL dialect I created for accessing the Structure Search functions of Bingo in JPQL and hence also QueryDSL. There is no specific reason I chose hibernate except I already knew it and it was able to do what I required. So I did not investigate any other JPA providers.

Application Framework – Dependency-Injection

Well I guess this is obvious. I chose Spring. I’ve heard and read a lot about Spring. I’ve always wanted to learn it and this was my chance. I also did not want the framework to depend an a full-blown Java EE Application server.

Data Access Layer – CRUD and Querying

I initial started the project with plain Spring and JPA (Hibernate). But shortly after I in my “research” I read about Spring Data JPA and it’s integration with QueryDSL. I quote from Spring-Data website:

Spring Data JPA aims to significantly improve the implementation of data access layers by reducing the effort to the amount that’s actually needed. As a developer you write your repository interfaces, including custom finder methods, and Spring will provide the implementation automatically.

To illustrate this here an example snippet showing an example implementation of my framework:

public interface RegistrationCompoundRepository extends ChemicalCompoundRepository {

    List findByRegNumberStartingWith(String regNumber);


RegistrationCompound has a property called regNumber. Above interface method is automatically implemented by Spring Data and will return a result List of the RegistrationCompounds that match the passed in argument. That’s all you need to write. No SQL and not even a method implementation. Just create the interface and then follow the findBy method conventions of Spring Data.

A Spring Data repository can also make use of QueryDSL.

Querydsl is a framework which enables the construction of type-safe SQL-like queries for multiple backends including JPA, JDO and SQL in Java.


List result = query.from(customer)
    .orderBy(customer.lastName.asc(), customer.firstName.desc())

If you use QueryDSL in your Spring Data Repository using QueryDslPredicateExecutor

@Transactional(propagation = Propagation.MANDATORY)
public interface ChemicalCompoundRepository
        extends ChemicalStructureSearchRepository, JpaRepository<T, Long>,
        QueryDslPredicateExecutor {

the repository will have additional methods that take a QueryDSL Predicate as an input. A Predicate is basically the WHERE-Clause of the query, like from above example"A%"). Some methods take additional parameter like a Pageable. This can be used for paging, the Pageable includes the paging (limit, offset) and sorting information.

This all means it is trivial to extend the repository my framework provides and add your own custom search methods to it. With using predicates you can create complex queries which at the same time search by chemical substructure, return the result sorted and paged and all this with a 1-line method declaration.

public Page findByChemicalStructure(String structureData,
            StructureSearchType searchType,
            Pageable pageable, Predicate predicate);

So I hope this got you interested!


Creating a Framework for Chemical Structure Search – Part 3

leave a comment »

Series Overview

This is Part 3 – Current Cheminformatics Landscape of the “Creating a Framework for Chemical Structure Search“-Series.

Previous posts:



In this part I will explain why I believe that a free, open-source framework for creating chemical structure search enabled database applications is needed. This is my personal opinion, nothing less or more.

Cheminformatics Landscape

There are several companies that offer a range of standard products. Not all companies offer all products. Common products are:

  • Chemical Drawing Program
  • Client for local or remote chemical databases
  • Database Cartridge (for chemical structure search in relational database
  • Chemistry Toolkit (API for one or multiple programming languages)

A database cartridge is an “add-on” to a relational database management system (RDBMS) that enables chemical structure searching directly within the RDBMS. A cartridge usually also supports the conversion between different chemical formats. In the database client the chemical structure search usually takes place client-side and no cartridge is needed.

Out of above components the companies create and offer some typical applications (often called “solutions”) like

  • Chemical Registration
  • Chemical Inventory
  • Electronic Lab Notebook (ELN)
  • Search / Analysis Tool
  • others

Those applications are either web applications or client-server applications. They usually require a commercial RDBMS like Oracle or SQL Server.

Most suppliers create their own proprietary format for handling chemical structures. While they offer the option to convert them to standard formats like SMILES or molfiles, the available functionality with those is usually limited. Certain functionality can not be converted at all.

Besides the commercial suppliers there are multiple free, open-source chemistry tool-kits for different programming languages. Also there is a professionally developed open-source database cartridge for Oracle, SQL Server and PostgreSQL.

What is the problem?

Commercial Solutions

The commercial solutions have a high risk for vendor lock-in. Once you decide for one product it will be much easier to integrate it with a product from the same vendor and licensing a whole bundle of products from one vendor is a lot cheaper. After accumulating data over several years migrating the whole application suite becomes very cumbersome and expensive.

Another issue is the need for a specific commercial RDBMS which are also known to be fairly expensive. There is no guarantee that the free version or the cheapest version is supported by the database cartridge. Often this isn’t even clearly documented and especially free versions have some serious limitations.

The support offered for commercial products is in my opinion not worth the money. Usually support is outsourced to “cheap countries” and the positions are filled with entry-level staffers and proficiency in English and their accent can be an issue that makes dealing with support much harder and more time consuming than it needs to be. The ones that stay longer and get more proficient in the applications usually move out of support rather quickly. There are good people there but you normally just don’t get into contact with them directly. Anyway the issues support can solve are almost always those a competent application admin can solve himself. And in case you find real bugs there is no guarantee they will be fixed soon if at all. And if you want new features you either have to be very patient with no guarantee you will ever get it or finance it yourself and the supplier will happily implement it for you.

Another issue is scientific reproducibility. The code is proprietary and hence you can not reproduce experiments that use such proprietary solutions unless you own a license too. Also you can’t guarantee that the code doesn’t have some bug of any kind making the results invalid.

Open-Source Products

The current issue is that these are more like individual components but not whole applications. To create as example a fully functional, chemical structure searchable Inventory System, that would require a significant development (programming) effort and hence the according expertise, be it in-house or outsourced. So while the commercial solutions are expensive, creating your own using open-source components can be even more expensive. This only makes sense if you are a large company with very special needs.


If you are a small to mid-level organizations your basically forced to buy a pricey product and RDBMS which you can barley afford. These systems are in general used by research departments which usually get less budget than say “production department” meaning while it is fine to spend millions in CRM and SRM system, this is not true for research systems.

Proposed Solution

The proposed solution would be a free, open-source ecosystem of cheminformatics applications. This is however a very long way to go. In this series I’m introducing you to the first, basic step: A free, open-source framework for creating chemical structure search enabled database applications.

Written by kienerj

April 15, 2013 at 12:41

Creating a Framework for Chemical Structure Search – Part 2

leave a comment »

Series Overview

This is Part 2 – Substructure Search Performance of the “Creating a Framework for Chemical Structure Search“-Series.

Previous posts:



In this part I will cover the solution for per-filtering when performing a chemical substructure search and go briefly into the topic of similarity searching.

Substructure Searching and Performance

History and User Expectations

As explained in Part 1 of this series chemical substructure search can be computationally very expensive and 20 to 30 years ago this was an extremely big issue due to the limited computing power available. Hence relying only on sub graph isomorphism was just not feasible and still is not. Because a researcher of today wants to search in databases containing millions of compounds and he wants the results to be displayed as quickly as possible, meaning seconds.


The solution is to filter out any records that can not match the query structure before the actual substructure search. This filtering is done by the use of so called fingerprints. A fingerprint is just a set of bits. If a bit is set, it means that the given chemical structure has the feature associated with that bit (Note: simplified, not really true). Below an example of a hashed fingerprint:

chemical hashed fingerprints

Image Source and further explanations

The important part about a fingerprint is that any bit set in the query structure will also be set in a structure containing it. This is checked by a logical AND of the query structure and every target structure in the database. If queryFingerprint AND targetFingerprint == targetFingerprint then the target might be a potential sub structure. All other molecule can be filtered out. So there are false-positives but no false-negatives.

Comparing fingerprints is extremely fast in modern CPUs. Hence the time added for the fingerprint comparison is minimal. In contrast depending on you database content and query structure filtering by fingerprint can eliminate 90% of the records in your database.

Similarity Searching

Similarity searching is comparing fingerprints to each other using a certain algorithm (there are different ones) and the result is a percentage how similar the 2 chemical structures are. The most common used measure (algorithm) is tanimoto similarity. Of course the results also depends on the used fingerprint and not only the algorithm.

For a lot more details on fingerprints and similarity searching I highly recommend to read daylight theory about fingerprints.

What’s next?

After the first 2 parts that were a very brief and simplistic introductions into cheminformatics and particular into chemical structure searching, the next part will discuss the current landscape especially available solutions for chemical structure searching and explain why I created a free, open-source framework for creating chemical structure search enabled database applications.

Written by kienerj

April 7, 2013 at 14:49

Creating a Framework for Chemical Structure Search – Part 1

leave a comment »

Series Overview

This is Part 1 – Simplistic Introduction to Cheminformatics of the “Creating a Framework for Chemical Structure Search“-Series.



Anyone reading my previous blog entry Spring 3 and Hibernate 4 for beginners probably realized that I’m working on something that has to do with chemistry and I don’t mean the thing you have going on with your pretty co-worker next door!

I’m going to shamelessly use this blog to “promote” my Open Source Project Molecule Database Framework. This framework allows you to rapidly create chemical structure search enabled database applications.

At least the first few parts of a long series will focus on the involved chemistry aspects and not on programming and code examples. The arguments made here obviously affect the design of the end product. Basic chemistry knowledge is required for this post.

What is a Chemical Structure?

A Chemical Structure is a model of what atoms compounds are build up of and how they are connected with each other. But enough with words. Here are 2 examples:

Water (aka H2O):

Chemical Structure of Water

Caffeine (aka C8H10N4O2 or the stuff that doesn’t make you yawn at your boss):

Chemical Strucutre of Caffeine

Searching for Chemical Structures

After seeing above images you hopefully asked yourself the question: How can these “images” be searched?. There are several answer: it depends on how you want to search. There are fundamentally 3 types of searches:

  • Full Structure Search
  • Sub Structure Search
  • Similarity Search

Full Structure Search

This is the easiest type. The chemical structure is converted to a chemically meaningful String and then all you do is exact string matching. There are several such formats the 2 most common being


SMILES alone is not useful as depending on how the structure is “drawn” and on the implementation the output for the same structure can be different. To partially solve that problem you need to use so called canonical SMILES which always returns the same string. However the actual output will still depend on the used algorithm and portability to another one is not guaranteed. Advantage of SMILES is the human readability. One way to write the SMILES for caffeine is:



In contrast to SMILES the so called standard InChI will always generate the same String for the same chemical structure. InChI was initially developed by NIST and now is supported by the InChi Trust. InChI is a pretty new format and only in the last few years has become more widespread. Downside compared to SMILES is that it is not very human readable.

The generated InChI can be converted to a hash, the so called InChIKey. An InChIkey has no chemical meaning and can not be converted back to an InChI (it’s a hash…). You probably get the point. The InChikey is an ideal candidate for performing full structure search.

The InChI for caffeine is:


(note: the InChI=1S is part of the string and required.)

The InChikey for caffeine is:


Source of SMILES and InChI: chemspider

Sub Structure Search

A Sub Structure Search is for finding any structure that contains the query structure. As images say more than 1000 words below again caffeine (left) and an example of one of many sub-structures that match caffeine (right):

Chemical Strucutre of CaffeineImidazole

A substructure search for the chemical structure on the right, called Imidazole, will find caffeine. But it would also find a lot of other structures. A random example being:

4-Amino-1H-imidazole-5-carboxylic acid

I hope above examples made it clear what is meant by a substructure search (Note: This assumes above structures are in the database you are searching in).

The question you need to ask yourself is: How can this search be done? To point out the obvious: This can’t be done by comparing Strings. The solution comes from a specific math field called Graph Theory. A graph has nodes (the atoms) and edges (bonds). Here an example taken from Wikipedia:

graph example

Nodes and edges can have attributes, eg. atom type and bond type (single, double…). The specific problem from graph theory we are interested in is called subgraph isomorphism. If you are interested in the details, please read the linked articles.

The problem with subgraph isomorphism is that it is so called NP-complete.

Although any given solution to such a problem can be verified quickly, there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known.

Or said in other words: subgraph isomorphism (substructure search) can be computationally very expensive. I will address the solution to this issue in-depth in the next part. Simplified you can do pre-filter structures that will certainly not match and then only need to to the subgraph isomorphism on a subset of the database.

Similarity Search

This will be addressed in the next part. The solution uses the same principle as above mentioned pre-filter.

Written by kienerj

April 5, 2013 at 13:25