Exact maximum clique algorithm for different graph types using machine learning

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

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.

• Language: English
• Keywords: maximum clique, protein graphs, machine learning, ProBiS
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FRI - Faculty of Computer and Information Science
• Publication status: Published
• Publication version: Version of Record
• Year: 2022
• Number of pages: 14 str.
• Numbering: Vol. 10, iss. 1, art. 97
• PID: 20.500.12556/RUL-136784
• UDC: 54
• ISSN on article: 2227-7390
• DOI: 10.3390/math10010097
• COBISS.SI-ID: 94170115
• Publication date in RUL: 20.05.2022

Record is a part of a journal

• Title: Mathematics
• Shortened title: Mathematics
• Publisher: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.
• Licensing start date: 01.01.2022

Secondary language

• Language: Slovenian
• Keywords: kemija, algoritmi, strojno učenje, matematika, grafi, MCQD