title: SketchSort: Fast All Pairs Similarity Search for Large Databases of Molecular Fingerprints.
abstract: Similarity networks of ligands are often reported useful in predicting chemical activities and target proteins. However, the naive method of computing all pairwise similarities of chemical fingerprints takes quadratic time, which is prohibitive for large scale databases with millions of ligands. We propose a fast all pairs similarity search method, called SketchSort, that maps chemical fingerprints to symbol strings with random projections, and finds similar strings by multiple masked sorting. Due to random projection, SketchSort misses a certain fraction of neighbors (i.e., false negatives). Nevertheless, the expected fraction of false negatives is theoretically derived and can be kept under a very small value. Experiments show that SketchSort is much faster than other similarity search methods and enables us to obtain a PubChem-scale similarity network quickly.
authors.affiliation: Minato Discrete Structure Manipulation System Project, ERATO, Japan Science and Technology Agency, Sapporo, 060-0814, Japan.
authors.forename: Yasuo
authors.initials: Y
authors.lastname: Tabei
authors.affiliation: Minato Discrete Structure Manipulation System Project, ERATO, Japan Science and Technology Agency, Sapporo, 060-0814, Japan. koji.tsuda@aist.go.jp.|Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), Tokyo, 135-0064, Japan. koji.tsuda@aist.go.jp.
authors.forename: Koji
authors.initials: K
authors.lastname: Tsuda
keywords: All pairs similarity search; Multiple sorting; SketchSort