Enhanced Molecular Docking: Novel Algorithm for Identifying Highest Weight k-Cliques in Weighted General and Protein-Ligand Graphs

Rozman, Kati and Ghysels, An and Zaválnij, Bogdán and Kunej, Tanja and Bren, Urban and Janežič, Dušanka and Konc, Janez (2024) Enhanced Molecular Docking: Novel Algorithm for Identifying Highest Weight k-Cliques in Weighted General and Protein-Ligand Graphs. JOURNAL OF MOLECULAR STRUCTURE, 1304. No.-137639. ISSN 0022-2860

Preview

Text 1-s2.0-S0022286024001625-main.pdf - Published Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (3MB) | Preview

Abstract

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.

Actions (login required)

Edit Item