11 Nov 08 Faster Fingerprint Search with Java & CDK

Rich Apodaca wrote a great serious posts named Fast Substructure Search Using Open Source Tools providing details on substructure search with MySQL. But, however, poor binary data operation functions of MySQL limited the implementation of similar structure search which typically depends on the calculation of Tanimato coefficient. We are going to use Java & CDK to add this feature.

As default output of CDK fingerprint, java.util.BitSet with Serializable interface is perfect data format of fingerprint data storage. Java itself provides several collections such as ArrayList, LinkedList, Vector class in package java.util. To provide web access to the search engine, thread unsafe ArrayList and LinkedList have to be kicked out. How about Vector? Once all the fingerprint data is well prepared, the collection  function we need to do similarity search is just iteration. No add, no delete. So, a light weight array is enough.

Most of the molecule information is stored in MySQL database, so we are going to map fingerprint to corresponding row in data table. Here is the MolDFData class, we use a long variable to store corresponding primary key in data table.

public class MolDFData implements Serializable {
    private long id;
    private BitSet fingerprint;

    public MolDFData(long id, BitSet fingerprint) {
        this.id = id;
        this.fingerprint = fingerprint;
    }
    public long getId() {
        return id;
    }

    public void setId(long id) {
        this.id = id;
    }

    public BitSet getFingerprint() {
        return fingerprint;
    }

    public void setFingerprint(BitSet fingerprint) {
        this.fingerprint = fingerprint;
    }
}

This is how we storage our fingerprints.

private MolFPData[] arrayData;

No big deal with similarity search. Just calculate the Tanimoto coefficient, if it’s bigger than minimal  similarity you set, add this one into result.

    public List searchTanimoto(BitSet bt, float minSimlarity) {
        List resultList = new LinkedList();
        int i;
        for (i = 0; i < arrayData.length; i++) {
            MolDFData aListData = arrayData[i];
            try {
                float coefficient = Tanimoto.calculate(aListData.getFingerprint(), bt);
                if (coefficient > minSimlarity) {
                    resultList.add(new SearchResultData(aListData.getId(), coefficient));
                }
            } catch (CDKException e) {

            }
            Collections.sort(resultList);
        }
        return resultList;
    }

Pretty ugly code?  Maybe. But it really works, at a acceptable speed. Tests were done using the code blow on a macbook(Intel Core Due 1.83 GHz, 2G RAM).

                long t3 = System.currentTimeMillis();
                List<SearchResultData> listResult = se.searchTanimoto(bs, 0.8f);
                long t4 = System.currentTimeMillis();
                System.out.println("Thread: Search done in " + (t4 - t3) + " ms.");

In my database of 87364 commercial compounds, it takes 335 ms.

Tags: CDK, Cheminformatics, Chemoinformatics, Fingerprint, Java