Effectiveness Analysis of Multiple Initial States Simulated Annealing Algorithm, a Case Study on the Molecular Docking Tool AutoDock Vina.

Simulated Annealing (SA) algorithm is not effective with large optimization problems for its slow convergence. Hence, several parallel Simulated Annealing (pSA) methods have been proposed, where the increase of searching threads can boost the speed of convergence. Although satisfactory solutions can be obtained by these methods, there is no rigorous mathematical analyses on their effectiveness. Thus, this article introduces a probabilistic model, on which a theorem about the effectiveness of multiple initial states parallel SA (MISPSA) has been proven. The theorem also demonstrates that the increasing parallelism in pSA algorithm with the reducing of search depth in each thread could obtain almost the same probability of finding the global optimal solution. We validated our theorem on AutoDock Vina, a widely used molecular docking tool with high accuracy and docking speed. AutoDock Vina uses a pSA strategy to find optimal molecular conformations. Under the premise that the total searching workload (i.e., thread number * iteration depth of each thread) remains unchanged, the docking accuracy from an aggressively parallelized SA searching method is almost the same or even better than those from the default exhaustiveness (parallelism degree) configuration of AutoDock Vina. Taking complex '1hnn' as an example,with the increase (125x) in the number of initial states (from 8 to 1000) and the decrease in the search depth for each thread (from 15540 to 124, or 1/125 of the original search depth), the mean energy is -7.80 and -7.94, while the mean RMSD is 3.4 and 3.14, respectively. The result also implies that a considerable speedup (in this case 125x in theory) can be obtained by a highly parallelized SA algorithm implementation.

Accelerating AutoDock Vina with GPUs.

AutoDock Vina is one of the most popular molecular docking tools. In the latest benchmark CASF-2016 for comparative assessment of scoring functions, AutoDock Vina won the best docking power among all the docking tools. Modern drug discovery is facing a common scenario of large virtual screening of drug hits from huge compound databases. Due to the seriality characteristic of the AutoDock Vina algorithm, there is no successful report on its parallel acceleration with GPUs. Current acceleration of AutoDock Vina typically relies on the stack of computing power as well as the allocation of resource and tasks, such as the VirtualFlow platform. The vast resource expenditure and the high access threshold of users will greatly limit the popularity of AutoDock Vina and the flexibility of its usage in modern drug discovery. In this work, we proposed a new method, Vina-GPU, for accelerating AutoDock Vina with GPUs, which is greatly needed for reducing the investment for large virtual screens and also for wider application in large-scale virtual screening on personal computers, station servers or cloud computing, etc. Our proposed method is based on a modified Monte Carlo using simulating annealing AI algorithm. It greatly raises the number of initial random conformations and reduces the search depth of each thread. Moreover, a classic optimizer named BFGS is adopted to optimize the ligand conformations during the docking progress, before a heterogeneous OpenCL implementation was developed to realize its parallel acceleration leveraging thousands of GPU cores. Large benchmark tests show that Vina-GPU reaches an average of 21-fold and a maximum of 50-fold docking acceleration against the original AutoDock Vina while ensuring their comparable docking accuracy, indicating its potential for pushing the popularization of AutoDock Vina in large virtual screens.