Critical evaluation of search algorithms for automated molecular docking and database screening

TLDR

The DOCK program explores possible orientations of a molecule within a macromolecular active site by superimposing atoms onto precomputed site points. The authors compare several search methods, including an exhaustive matching algorithm based on a single docking graph. They evaluate each method by screening a small database of molecules against multiple macromolecular targets, varying sampling to monitor time convergence of scores and rankings. The site point–directed search is tenfold faster than random search, and the single docking graph matching algorithm accelerates database screening up to 60‑fold, outperforming the current bipartite graph matching in DOCK, indicating that bias toward high‑ranking molecules drives speed and will be incorporated into DOCK 4.0. © 1997 John Wiley & Sons, Inc.

Abstract

The DOCK program explores possible orientations of a molecule within a macromolecular active site by superimposing atoms onto precomputed site points. Here we compare a number of different search methods, including an exhaustive matching algorithm based on a single docking graph. We evaluate the performance of each method by screening a small database of molecules to a variety of macromolecular targets. By varying the amount of sampling, we can monitor the time convergence of scores and rankings. We not only show that the site point–directed search is tenfold faster than a random search, but that the single graph matching algorithm boosts the speed of database screening up to 60-fold. The new algorithm, in fact, outperforms the bipartite graph matching algorithm currently used in DOCK. The results indicate that a critical issue for rapid database screening is the extent to which a search method biases run time toward the highest-ranking molecules. The single docking graph matching algorithm will be incorporated into DOCK version 4.0. © 1997 John Wiley & Sons, Inc. J Comput Chem 18: 1175–1189