ISSN 2590-9770
The Art of Discrete and Applied Mathematics 8 (2025) #P1.08
https://doi.org/10.26493/2590-9770.1789.4e7
(Also available at http://adam-journal.eu)
Advanced clique algorithms for
protein product graphs*
Janez Konc† , Dušanka Janežič‡
University of Primorska, Faculty of Mathematics, Natural Sciences and Information
Technologies, Glagoljaška ulica 8, SI-6000 Koper, Slovenia
Received 1 April 2024, accepted 13 January 2025, published online 25 February 2025
Abstract
In this paper, we give a comprehensive overview of the development of clique algo-
rithms and their use for drug design based on the search for cliques in protein product
graphs. The maximum clique problem is a computational problem of finding largest sub-
sets of vertices in a graph that are all pairwise adjacent. A related problem is the maximum
weight clique problem and the highest weight k-clique problem, which both extend the al-
gorithm to weighted graphs. The review covers our developed algorithms, starting with our
improved branch-and-bound algorithm for finding maximum cliques in undirected graphs
from 2007 up to the recent developments of algorithms for weighted graphs in 2024. We
show the application of these algorithms to early stages of drug discovery, in particular to
protein binding site detection based on protein similarity search in large protein databases
and to protein-ligand molecular docking.
Keywords: Cliques, protein product graphs, applications.
Math. Subj. Class.: 05C69
*Dedicated to Professor Dragan Marušič on the occasion of the 70th birthday.
†Equally Contributed.
‡Corresponding author. Equally Contributed.
E-mail addresses: konc@cmm.ki.si (Janez Konc), dusanka.janezic@upr.si (Dušanka Janežič)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 2590-9770
The Art of Discrete and Applied Mathematics 8 (2025) #P1.08
https://doi.org/10.26493/2590-9770.1789.4e7
(Dostopno tudi na http://adam-journal.eu)
Napredni algoritmi za iskanje klik v
grafih beljakovinskih izdelkov*
Janez Konc† , Dušanka Janežič‡
Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske
tehnologije, Glagoljaška ulica 8, SI-6000 Koper, Slovenija
Prejeto 1. aprila 2024, sprejeto 13. januarja 2025, objavljeno na spletu 25. februarja 2025
Povzetek
V tem prispevku podajamo obsežen pregled razvoja algoritmov za iskanje klik in nji-
hove uporabe za načrtovanje zdravil na podlagi iskanja klik v grafih beljakovinskih izdelkov.
Problem največje klike je računski problem iskanja največjih podmnožic točk danega grafa,
v katerih sta si vsaki dve točki sosednji. Sorodna problema sta problem najtežje klike in
problem najtežje k-klike, ki oba razširjata algoritem na utežene grafe. Pregled zajema naše
algoritme, ki smo jih razvili, začenši z našim izboljšanim algoritmom razveji-in-omeji za
iskanje največjih klik v neusmerjenih grafih od leta 2007 do nedavnega razvoja algoritmov
za utežene grafe leta 2024. Prikažemo uporabo teh algoritmov v zgodnjih fazah odkrivanja
zdravil, zlasti pri odkrivanju mesta vezave na beljakovine, ki temelji na iskanju podobnosti
beljakovin v velikih zbirkah podatkov o beljakovinah, in pri molekularnem povezovanju
beljakovin z ligandom.
Ključne besede: Klike, grafi beljakovinskih izdelkov, aplikacije.
Math. Subj. Class.: 05C69
*Posvečeno profesorju Draganu Marušiču ob 70. rojstnem dnevu.
†Enak prispevek.
‡Kontaktni avtor. Enak prispevek.
E-poštni naslovi: konc@cmm.ki.si (Janez Konc), dusanka.janezic@upr.si (Dušanka Janežič)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/