Molecular docking, a key process in drug discovery, is often used in the discovery of new bioactive compounds. In this technique, small molecules are systematically placed at a protein binding site to identify the ligands with the highest binding affinity. Here we have developed a new graph-theoretical algorithm called K-CliqueWeight. This algorithm efficiently identifies the top N highest weight k-cliques in different types of vertex-weighted graphs and can serve as a building block for various algorithms addressing different problems, including molecular docking. K-CliqueWeight and its variant K-CliqueDynWeight are extensions of our established and widely used maximum clique algorithm. Our new algorithm uses a novel approach to approximate graph coloring and provides efficient upper bounds on the size and weight of a k-clique within the branch-and-bound algorithm. It outperforms alternative methods and often shows a speedup of several orders of magnitude. Rigorous tests with general random graphs and those specifically designed for docking confirm its exceptional performance. K-CliqueWeight has been integrated into the existing ProBiS-Dock algorithm for molecular docking. The algorithm is freely available to the academic community at
http://insilab.org/kcliqueweight.
