Premium
Critical evaluation of search algorithms for automated molecular docking and database screening
Author(s) -
Ewing Todd J. A.,
Kuntz Irwin D.
Publication year - 1997
Publication title -
journal of computational chemistry
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.907
H-Index - 188
eISSN - 1096-987X
pISSN - 0192-8651
DOI - 10.1002/(sici)1096-987x(19970715)18:9<1175::aid-jcc6>3.0.co;2-o
Subject(s) - bipartite graph , dock , computer science , algorithm , docking (animal) , graph , matching (statistics) , 3 dimensional matching , ranking (information retrieval) , data mining , theoretical computer science , artificial intelligence , chemistry , mathematics , medicine , nursing , biochemistry , statistics
The DOCK program explores possible orientations of a moleculewithin a macromolecular active site by superimposing atoms onto precomputedsite 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 ofmolecules to a variety of macromolecular targets. By varying the amount ofsampling, we can monitor the time convergence of scores and rankings. Wenot only show that the site point–directed search is tenfold fasterthan a random search, but that the single graph matching algorithm booststhe 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 isthe extent to which a search method biases run time toward thehighest‐ranking molecules. The single docking graph matching algorithm willbe incorporated into DOCK version 4.0. © 1997 John Wiley & Sons, Inc. J Comput Chem 18: 1175–1189