An Effective and Robust Approach Based on Malatya Centrality Algorithm for Interpreting Cheminformatics Graphs Using Maximum Clique

Abstract

Cheminformatics graphs are derived by transforming the atomic nodes and bonds of chemical compounds into graph structures and are used to analyze the chemical and structural properties of molecules. In this study, an effective and robust approach based on the Malatya Centrality Algorithm is proposed for identifying the maximum clique in cheminformatics graphs. The proposed method transforms cheminformatics graphs by taking their complement and calculates the Malatya centrality values for these graphs. Using these values, the minimum independent set is identified in the complemented graph, which corresponds to the set of nodes forming the maximum clique in the original graph. The study demonstrates, through tests on various cheminformatics graphs, including enzyme and molecular graphs, that maximum clique and chromatic number values provide significant insights into the structural properties of these graphs. Notably, the maximum clique value was often calculated as 2 for bipartite graphs. Additionally, it was observed that enzyme graphs exhibit maximum clique and chromatic number values that are optimal or near-optimal, with some graphs possessing perfect graph properties. The proposed approach offers an effective and robust solution for structural analysis in cheminformatics graphs.

Keywords

• Cheminformatics Graphs
• Enzyme Graphs
• Malatya Centrality
• Maximum Clique Problem
• Molecular Graphs

References

1. J. Bajorath, Chemoinformatics: Concepts, Methods, and Tools for Drug Discovery. Springer Nature, 2013.
2. P. Bongini, M. Bianchini, and F. Scarselli, “Molecular generative Graph Neural Networks for Drug Discovery,” Neurocomputing, vol. 450, pp. 242–252, 2021, doi: 10.1016/j.neucom.2021.04.039.
3. R. Mercado et al., “Graph networks for molecular design,” Mach. Learn. Sci. Technol., vol. 2, no. 2, 2021, doi: 10.1088/2632-2153/abcf91.
4. Y. Singh, S. K. Sharma, and P. Hazra, “Mathematical analysis of one-dimensional lead sulphide crystal structure using molecular graph theory,” Mol. Phys., vol. 120, no. 12, 2022, doi: 10.1080/00268976.2022.2086933.
5. J. Stumpfe, D., & Bajorath, “Similarity searching and scaffold hopping in chemical space,” Nat. Chem. Biol., vol. 8, no. 2, pp. 118–126, 2012.
6. N. M. Kriege, “Comparing Graphs,” 2015.
7. C. A. Lipinski, “Lead- and drug-like compounds: The rule-of-five revolution,” Drug Discov. Today Technol., vol. 1, no. 4, pp. 337–341, 2004, doi: 10.1016/j.ddtec.2004.11.007.
8. Z. Guo et al., “Graph-based Molecular Representation Learning,” IJCAI Int. Jt. Conf. Artif. Intell., vol. 2023-Augus, pp. 6638–6646, 2023, doi: 10.24963/ijcai.2023/744.

9. A. J. Goodsell, D. S., Morris, G. M., & Olson, “Automated docking of flexible ligands: applications of AutoDock,” J. Mol. Recognit., vol. 9, no. 1, pp. 1–5, 1996, [Online]. Available: https://doi.org/10.1002/(SICI)1099-1352(199601)9:1%3C1::AID-JMR241%3E3.0.CO;2-6
10. I. T. Jollife and J. Cadima, “Principal component analysis: A review and recent developments,” Philos. Trans. R. Soc. A Math. Phys. Eng. Sci., vol. 374, no. 2065, 2016, doi: 10.1098/rsta.2015.0202.
11. R. M. Karp, “Complexity of Computer Computations,” in Reducibility Among Combinatorial Problems, Springer Berlin Heidelberg, 1972, pp. 85–103.
12. C. Bron and J. Kerbosch, “Algorithm 457: Finding All Cliques of an Undirected Graph [H],” Commun. ACM, vol. 16, no. 9, pp. 575–577, 1973, doi: 10.1145/362342.362367.
13. A. Karcı, S. Yakut, and F. Öztemiz, “A New Approach Based on Centrality Value in Solving the Minimum Vertex Cover Problem: Malatya Centrality Algorithm,” Comput. Sci., vol. 55, no. 35, pp. 1–100, Nov. 2022, doi: 10.53070/bbd.1195501.
14. S. Yakut, F. Öztemiz, and A. Karcı, “A New Approach Based on Centrality Value in Solving the Maximum Independent Set Problem: Malatya Centrality Algorithm,” Comput. Sci., vol. 55, no. 35, pp. 1–100, Jan. 2023, doi: 10.53070/bbd.1224520.
15. S. Yakut and F. Öztemiz, “A New Maximum Clique Method,” in International Informatics Congress, 2024, pp. 200–208.
16. M. A. Yirik, E. K. Çolpan, S. Schmidt, M. Sorokina, and C. Steinbeck, “Review on Chemical Graph Theory and Its Application in Computer-Assisted Structure Elucidation,” Pre-print, no. November, 2021, doi: 10.20944/preprints202111.0546.v1.
17. Z. Zhang, Q. Liu, C. K. Lee, C. Y. Hsieh, and E. Chen, “An equivariant generative framework for molecular graph-structure Co-design,” Chem. Sci., vol. 14, no. 31, pp. 8380–8392, 2023, doi: 10.1039/d3sc02538a.
18. Y. Okamoto, “Finding a Maximum Common Subgraph from Molecular Structural Formulas through the Maximum Clique Approach Combined with the Ising Model,” ACS Omega, vol. 5, no. 22, pp. 13064–13068, 2020, doi: 10.1021/acsomega.0c00987.
19. R. Schmidt, F. Krull, A. L. Heinzke, and M. Rarey, “Disconnected Maximum Common Substructures under Constraints,” J. Chem. Inf. Model., vol. 61, no. 1, pp. 167–178, 2021, doi: 10.1021/acs.jcim.0c00741.
20. S. O’Hagan and D. B. Kell, “Analysis of drug-endogenous human metabolite similarities in terms of their maximum common substructures,” J. Cheminform., vol. 9, no. 1, pp. 1–17, 2017, doi: 10.1186/s13321-017-0198-y.
21. Y. Cao, T. Jiang, and T. Girke, “A maximum common substructure-based algorithm for searching and predicting drug-like compounds,” Bioinformatics, vol. 24, no. 13, pp. 366–374, 2008, doi: 10.1093/bioinformatics/btn186.
22. G. De Ita Luna, P. Bello López, and R. Marcial-Romero, “Counting Rules for Computing the Number of Independent Sets of a Grid Graph,” Mathematics, vol. 12, no. 6, pp. 1–14, 2024, doi: 10.3390/math12060922.
23. G. De Ita, P. Bello, and M. Tovar, “A Branch and Bound Algorithm for Counting Independent Sets on Grid Graphs,” p. 28, 2023, doi: 10.3390/iocma2023-14434.
24. Z. Raza, K. Naz, and S. Ahmad, “Expected Values of Molecular Descriptors in Random Polyphenyl Chains,” Emerg. Sci. J., vol. 6, no. 1, pp. 151–165, 2022, doi: 10.28991/ESJ-2022-06-01-012.
25. F. Ali, B. A. Rather, M. Sarfraz, A. Ullah, N. Fatima, and W. K. Mashwani, “Certain Topological Indices of Non-Commuting Graphs for Finite Non-Abelian Groups,” Molecules, vol. 27, no. 18, pp. 1–15, 2022, doi: 10.3390/molecules27186053.
26. Z. Shui and G. Karypis, “Heterogeneous molecular graph neural networks for predicting molecule properties,” Proc. - IEEE Int. Conf. Data Mining, ICDM, vol. 2020-Novem, no. Icdm, pp. 492–500, 2020, doi: 10.1109/ICDM50108.2020.00058.
27. Z. Wu et al., “Chemistry-intuitive explanation of graph neural networks for molecular property prediction with substructure masking,” Nat. Commun., vol. 14, no. 1, pp. 1–15, 2023, doi: 10.1038/s41467-023-38192-3.
28. A. Kengkanna and M. Ohue, “Enhancing property and activity prediction and interpretation using multiple molecular graph representations with MMGX,” Commun. Chem., vol. 7, no. 1, 2024, doi: 10.1038/s42004-024-01155-w.
29. L. David, A. Thakkar, R. Mercado, and O. Engkvist, “Molecular representations in AI-driven drug discovery: a review and practical guide,” J. Cheminform., vol. 12, no. 1, pp. 1–22, 2020, doi: 10.1186/s13321-020-00460-5.
30. S. Bougueroua, M. Bricage, Y. Aboulfath, D. Barth, and M. P. Gaigeot, “Algorithmic Graph Theory, Reinforcement Learning and Game Theory in MD Simulations: From 3D Structures to Topological 2D-Molecular Graphs (2D-MolGraphs) and Vice Versa,” Molecules, vol. 28, no. 7, 2023, doi: 10.3390/molecules28072892.
31. X. Zang, X. Zhao, and B. Tang, “Hierarchical Molecular Graph Self-Supervised Learning for property prediction,” Commun. Chem., vol. 6, no. 1, pp. 1–10, 2023, doi: 10.1038/s42004-023-00825-5.
32. P. C. S. Costa, J. S. Evangelista, I. Leal, and P. C. M. L. Miranda, “Chemical graph theory for property modeling in qsar and qspr—charming QSAR & QSPR,” Mathematics, vol. 9, no. 1, pp. 1–19, 2021, doi: 10.3390/math9010060.
33. S. K. Sharma, V. K. Bhat, H. A. E. W. Khalifa, and A. M. Alanzi, “Mixed Metric Dimension of Certain Carbon Nanocone Networks,” Polycycl. Aromat. Compd., vol. 44, no. 3, pp. 2046–2061, 2024, doi: 10.1080/10406638.2023.2211734.
34. Z. Ertem, E. Lykhovyd, Y. Wang, and S. Butenko, “The maximum independent union of cliques problem: complexity and exact approaches,” J. Glob. Optim., vol. 76, no. 3, pp. 545–562, 2020, doi: 10.1007/s10898-018-0694-2.
35. F. Öztemiz and S. Yakut, “An Effective Method for Determining Node Dominance Values: Malatya Centrality Algorithm,” 32nd IEEE Conf. Signal Process. Commun. Appl. SIU 2024 - Proc., pp. 1–4, 2024, doi: 10.1109/SIU61531.2024.10601155.
36. C. T. Bakan and S. Yakut, “Graf Teorisi ve Malatya Merkezilik Algoritmasına Dayalı Haber Metinlerinin Özetlemesi,” BİLİŞİM Teknol. DERGİSİ, vol. 17, no. 3, pp. 189–198, 2024, doi: 10.17671/gazibtd.1463107.
37. “Cheminformatics Graphs, Accesed Time: 02.11.2024, https://networkrepository.com/chem.php.”
38. M. C. Golumbic, “Chapter 3 - Perfect graphs,” in Annals of Discrete Mathematics, Elsevier, 2004, pp. 51–80. [Online]. Available: https://doi.org/10.1016/S0167-5060(04)80051-7.