13 十一 08 More Faster Fingerprint Search with Java & CDK
Recently, I wrote a post named Faster Fingerprint Search with Java & CDK . It’s fast enough, with a response time of 300 ms for a database of 100000 compounds as you can see from the chart above. If we do some simple improvement on it, it could be even faster.
As we all know, when we search for similar structures, our judgement of similarity is based on Tanimoto coefficient. If variable ‘a’ stands for the number of all TRUE bits in one fingerprint, ‘b’ stands for another, and ‘c’ stands for the number of TRUE bits they both have, we can define Tanimoto coefficient as c/(a+b-c). If we want to find some fingerprints with a minimum Tanimoto coefficient λ, we are saying c/(a+b-c) > λ. As c is the number of TRUE bits they have in common, c is absolutely not greater than a or b. Then we get b*λ<a<b/λ and a*λ<b<a/λ.
With this inequality in hand, we don’t need to iterate all the fingerprints to do a similar structure search. If we sort all the fingerprints in their number of all TRUE bits, we can significantly reduce the range of database we need to screen.
Here is the distribution of fingerprint darkness of my database of 80000 commercial compounds.
And here is the search time after new search method is applied.
Extremely fast!
Tags: CDK, Cheminformatics, Fingerprint, 化学信息学
11 十一 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, Fingerprint, Java, 化学信息学
