Exact Maximum Clique Algorithm for Different Graph Types Using Machine Learning

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 lear...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics (Basel) 2022-01, Vol.10 (1), p.97
Main Authors: Reba, Kristjan, Guid, Matej, Rozman, Kati, Janežič, Dušanka, Konc, Janez
Format: Article
Language:English
Subjects:
Algorithms
Binding sites
Bioinformatics
Computational chemistry
Graph theory
Graphs
Ligands
Machine learning
Mathematics
maximum clique
Molecular docking
Network analysis
Parameters
ProBiS
protein graphs
Proteins
Social networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2227-7390
2227-7390
DOI:10.3390/math10010097