A basin hopping algorithm for protein-protein docking

We present a novel probabilistic search algorithm to efficiently search the structure space of protein dimers. The algorithm is based on the basin hopping framework that repeatedly follows up structural perturbation with energy minimization to obtain a coarse-grained view of the dimeric energy surface in terms of its local minima. A Metropolis criterion biases the search towards lower-energy minima over time. Extensive analysis highlights efficient and effective implementations for the perturbation and minimization components. Testing on a broad list of dimers shows the algorithm recovers the native dimeric configuration with great accuracy and produces many minima near the native configuration. The algorithm can be employed to efficiently produce relevant decoys that can be further refined at greater detail to predict the native configuration.