From greedy to branch & bound and back: assessing optimization strategies for incremental construction molecular docking tools

Abstract

A branch & bound approach for the assembly-phase of the incremental construction algorithm of the software package FlexX is presented. For this a local bound for partial solutions has been implemented which estimates the best score achievable for the considered solutions. This estimation is based on scoring values which single components can achieve in certain regions of the active site as well as distance constraints deduced from the composition of the considered partial solution. Furthermore, a timeand space-bounded search strategy specific to the addressed problem has been developed. The implemented algorithm was tested on a dataset containing 169 complexes. In 116 of these cases the calculation was finished in a reasonably defined time frame while the calculation for the remaining complexes was not completed in this period of time. For all calculated complexes, the best solution shows a score better or equal to the solution of standard-FlexX. This, however, is not always associated with an improvement of the RMSD between the calculated placement of the ligand and the crystal structure. The presented algorithm is applicable for thorough virtual screening of small sets of ligands comprising up to nine rotatable, acyclic bonds. Furthermore, the method gives important insights to the k-greedy method and can be used for scientific assessment of new scoring functions within FlexX.