Flexible protein-protein docking based on Best-First search algorithm.

We developed a new high resolution protein-protein docking method based on Best-First search algorithm that loosely imitates protein-protein associations. The method operates in two stages: first, we perform a rigid search on the unbound proteins. Second, we search alternately on rigid and flexible degrees of freedom starting from multiple configurations from the rigid search. Both stages use heuristics added to the energy function, which causes the proteins to rapidly approach each other and remain adjacent, while optimizing on the energy. The method deals with backbone flexibility explicitly by searching over ensembles of conformations generated before docking. We ran the rigid docking stage on 66 complexes and grouped the results into four classes according to evaluation criteria used in Critical Assessment of Predicted Interactions (CAPRI; "high," "medium," "acceptable," and "incorrect"). Our method found medium binding conformations for 26% of the complexes and acceptable for additional 44% among the top 10 configurations. Considering all the configurations, we found medium binding conformations for 55% of the complexes and acceptable for additional 39% of the complexes. Introducing side-chains flexibility in the second stage improves the best found binding conformation but harms the ranking. However, introducing side-chains and backbone flexibility improve both the best found binding conformation and the best found conformation in the top 10. Our approach is a basis for incorporating multiple flexible motions into protein-protein docking and is of interest even with the current use of a simple energy function.