Exact maximum clique algorithm for different graph types using machine learning

Reba, Kristjan (avtor), Guid, Matej (avtor), Rozman, Kati (avtor), Janežič, Dušanka (avtor), Konc, Janez (avtor)

Finding a maximum clique is important in research areas such as computational chemistry, social network analysis, and bioinformatics. It is possible to compare the maximum clique size between protein graphs to determine their similarity and function. In this paper, improvements based on machine learning (ML) are added to a dynamic algorithm for finding the maximum clique in a protein graph, Maximum Clique Dynamic (MaxCliqueDyn; short: MCQD). This algorithm was published in 2007 and has been widely used in bioinformatics since then. It uses an empirically determined parameter, Tlimit, that determines the algorithm’s flow. We have extended the MCQD algorithm with an initial phase of a machine learning-based prediction of the Tlimit parameter that is best suited for each input graph. Such adaptability to graph types based on state-of-the-art machine learning is a novel approach that has not been used in most graph-theoretic algorithms. We show empirically that the resulting new algorithm MCQD-ML improves search speed on certain types of graphs, in particular molecular docking graphs used in drug design where they determine energetically favorable conformations of small molecules in a protein binding site. In such cases, the speed-up is twofold.

• Jezik: Angleški jezik
• Ključne besede: maximum clique, protein graphs, machine learning, ProBiS
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2022
• Št. strani: 14 str.
• Številčenje: Vol. 10, iss. 1, art. 97
• PID: 20.500.12556/RUL-136784
• UDK: 54
• ISSN pri članku: 2227-7390
• DOI: 10.3390/math10010097
• COBISS.SI-ID: 94170115
• Datum objave v RUL: 20.05.2022

Gradivo je del revije

• Naslov: Mathematics
• Skrajšan naslov: Mathematics
• Založnik: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.
• Začetek licenciranja: 01.01.2022

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: kemija, algoritmi, strojno učenje, matematika, grafi, MCQD