The Chemfp Project
Author:
Preprint
- 22 March 2019
- preprint
- Published by American Chemical Society (ACS) in ChemRxiv
Abstract
This paper describes the 10 years of work and research results of the chemfp project, available from http://chemfp.com/ . The project started as a way to promote the FPS format for cheminformatics fingerprint exchange. This is a line-oriented text format meant to be easy to read and write. It supports metadata such as the fingerprint type and data provenance.The chemfp package for Python was developed to provide the basic command-line tools and Python API for working with fingerprint data, because a format without useful tools will not be used. The similarity search performance improved by an order of magnitude over the decade, due to careful implementation and effective use of CPU hardware, including AVX2 support for faster popcount calculations than the built-in POPCNT instruction. The implementation details for high-performance search have rarely been discussed in the literature. As a result, many tools and published papers use implementations which are not close to the machine's capabilities. This paper describes those details to help with future optimization efforts. The most advanced version of chemfp evaluates about 130 million 1024-bit fingerprint Tanimotos per second on a single core of a standard x86-64 server machine. When combined with the BitBound algorithm, a k=1000 nearest-neighbor search of the 1.8 million 2048-bit Morgan fingerprints of ChEMBL 24 averages 27 ms/query and the same search of the 970 million PubChem fingerprints averages 220 ms/query, making chemfp one of the fastest similarity search tools available for CPUs. This appears to be several times faster than previously published work in the field, including in papers which use much more sophisticated data structures. A close analysis shows that nearly all earlier work assumes that the intersection popcount was the limiting performance factor, while on modern hardware uncompressed search is effectively memory bandwidth limited. For example, AVX2 search is 10% faster when memory prefetching, and the popcount evaluation time is far faster than fetching a random location in main memory. It proved difficult to evaluate existing tool performance because in the few cases where the tools were available, each used its own format, data sets, and search tasks. This paper introduces the chemfp benchmark data set to help make head-to-head comparisons easier in the future, and to help promote the FPS format. The FPS format is slow for tasks like web server reloads and command-line scripting. This paper also describes the FPB format, which is a binary application format for fast loads.Keywords
All Related Versions
- Published version: Journal of Cheminformatics, 11 (1), 1.
This publication has 33 references indexed in Scilit:
- Molecular fingerprint similarity search in virtual screeningMethods, 2015
- Succinct Multibit Tree: Compact Representation of Multibit Trees by Using Succinct Data Structures in Chemical Fingerprint SearchesLecture Notes in Computer Science, 2012
- SketchSort: Fast All Pairs Similarity Search for Large Databases of Molecular FingerprintsMolecular Informatics, 2011
- Optimizing the use of open-source software applications in drug discoveryDrug Discovery Today, 2006
- Open-source software: not quite endsvilleDrug Discovery Today, 2005
- The case for open-source software in drug discoveryDrug Discovery Today, 2005
- Similarity Searching and Clustering of Chemical-Structure Databases Using Molecular Property DataJournal of Chemical Information and Computer Sciences, 1994
- Computation and management of chemical properties in CACTVS: An extensible networked approach toward modularity and compatibilityJournal of Chemical Information and Computer Sciences, 1994
- Clustering of chemical structures on the basis of two-dimensional similarity measuresJournal of Chemical Information and Computer Sciences, 1992
- Searching protein sequence libraries: Comparison of the sensitivity and selectivity of the Smith-Waterman and FASTA algorithmsGenomics, 1991