Pengembangan Algoritma Maximum Clique Dynamic-Machine Learning (MCQD-ML) pada Jaringan Interaksi Protein-Protein

Abstract

Maximum Clique Problem (MCP) merupakan salah satu permasalahan dalam teori graf yang tergolong NP-Hard dan banyak diaplikasikan dalam bioinformatika, termasuk analisis jaringan interaksi protein-protein (PPI). Salah satu pendekatan modern untuk menyelesaikan MCP adalah algoritma Maximum Clique Dynamic-Machine Learning (MCQD-ML), yang mengintegrasikan pembelajaran mesin untuk memprediksi parameter batas komputasi (Tlimit) untuk mengefisienkan langkah pencarian klik. Namun, pada graf jaringan biologis (Protein-Protein Interaction Network/PPIN) yang bersifat scale-free dan kompleks, performa MCQD-ML sering kali belum optimal. Besarnya ruang pencarian dan banyaknya simpul yang tidak relevan (noise) dapat menghambat efisiensi model prediktif. Untuk mengatasi keterbatasan tersebut, penelitian ini bertujuan mengembangkan algoritma Maximum Clique Dynamic-Machine Learning (MCQD-ML) yang lebih efisien untuk identifikasi maximum clique pada jaringan PPI melalui dua strategi utama, yaitu pemangkasan graf adaptif menggunakan kombinasi K-Core Decomposition dan Graph Attention Network yang dioptimasi dengan Particle Swarm Optimization (GAT-PSO), serta prediksi dinamis parameter Tlimit yang diformulasikan sebagai tugas klasifikasi multikelas menggunakan arsitektur Graph Neural Network (GNN) berbasis fitur sentralitas. Eksperimen komputasi dilakukan terhadap 12.535 jaringan PPI untuk menguji efektivitas kerangka kerja yang diusulkan. Hasil pengujian menunjukkan bahwa tahap k-core decomposition dan attention-based pruning berbasis GAT-PSO berhasil mereduksi ruang pencarian secara signifikan, dengan tingkat eliminasi rata-rata sebesar 95,87% simpul dan 91,11% sisi graf awal. Ekstraksi empat metrik sentralitas mempertahankan struktur klaster biologis meskipun ruang pencarian telah direduksi secara signifikan. Pada tahap prediksi Tlimit, model klasifikasi GIN terpilih berhasil memetakan karakteristik topologi graf sisa ke dalam tiga kelas komputasi secara stabil. Secara operasional, evaluasi sistem terintegrasi (end-to-end) pada himpunan graf irisan yang terisolasi secara ketat (independent unseen test set) berhasil mencatatkan rata-rata percepatan komputasi (speed-up) sebesar 72,19 kali lipat. Percepatan ini dicapai tanpa mengorbankan struktur biologi esensial, dibuktikan oleh nilai Similarity Size sebesar 93,20% dan Jaccard Index 0,8343. Lebih lanjut, analisis pengayaan fungsional lintas kingdom memvalidasi bahwa maximum clique yang ditemukan memiliki signifikansi biomedis. Hal ini terlihat dari kemampuannya dalam memetakan lokalisasi anatomi tumbuhan serta mengisolasi modul ribosom yang rentan menjadi target infeksi patogen. Hasil ini menunjukkan bahwa algoritma yang diusulkan tidak hanya meningkatkan efisiensi komputasi, tetapi juga mempertahankan relevansi biologis dari maximum clique yang diidentifikasi.

The Maximum Clique Problem (MCP) is an NP-Hard problem in graph theory with extensive applications in bioinformatics, including the analysis of Protein-Protein Interaction (PPI) networks. A modern approach to solving the MCP is the Maximum Clique Dynamic-Machine Learning (MCQD-ML) algorithm, which integrates machine learning to predict the computational time limit parameter (Tlimit) to improve the efficiency of clique searching. However, on biological network graphs (Protein-Protein Interaction Networks / PPINs), which are characteristically scale-free and complex, the performance of MCQD-ML is often suboptimal. The massive search space and the abundance of irrelevant nodes (noise) can hinder the efficiency of the predictive model. To address these limitations, this study aims to develop a more efficient Maximum Clique Dynamic-Machine Learning (MCQD-ML) algorithm for identifying maximum cliques in PPI networks through two main strategies, adaptive graph pruning using a combination of K -Core Decomposition and a Graph Attention Network optimized with Particle Swarm Optimization (GAT-PSO), as well as the dynamic prediction of the Tlimit parameter, formulated as a multi-class classification task using a Graph Neural Network (GNN) architecture based on centrality features. Computational experiments were conducted on 12.535 PPI networks to evaluate the effectiveness of the proposed framework. The experimental results demonstrate that the k-core decomposition and GAT-PSO-driven attention-based pruning stages successfully and significantly reduced the search space, achieving an average elimination rate of 95,87% of nodes and 91,11% of edges from the initial graphs. The extraction of four centrality metrics preserves the biological cluster structure even though the search space has been significantly reduced. In the Tlimit prediction stage, the selected GIN classification model successfully and stably mapped the topological characteristics of the residual graphs into three computational time classes. Operationally, the end-to-end evaluation of the integrated system on an intersection set of strictly isolated graphs (independent unseen test set) achieved an average computational speed-up of 72,19 times. This acceleration was achieved without sacrificing essential biological structures, as evidenced by a Similarity Size of 93,20% and a Jaccard Index of 0,8343. Furthermore, cross-kingdom functional enrichment analysis validated that the discovered maximum cliques hold biomedical significance. This is evident from their ability to map plant anatomical localizations and isolate ribosomal modules that are highly susceptible to pathogenic infections. These results demonstrate that the proposed algorithm not only improves computational efficiency but also preserves the biological relevance of the identified maximum cliques.