Protein Clustering in Formation of Falciparum Plasmodium using Soft Regularized-Markov Clustering Algorithm

Hafizh Amrullah, Syamsuddin Wisnubroto



Protein has an important role in our life. Every protein interacts with other proteins, DNA, and other molecules. It forms a very large protein interaction networks. We need clustering method to analyze it. Soft Regularized Markov Clustering (SR-MCL) algorithm is one of clustering method to reduce the weakness of Regularized Markov Clustering and Markov Clustering.  In this research, SR-MCL will be applied using OpenMP.  In every thread, SR-MCL is run using inflation parameter r = 2, 3, and 4. The simulation results show that, based on the fastest execution time and the smallest iteration, the parameter r = 2 produces the best cluster with 40 iterations and execution time is 613 seconds. The cluster centers obtained are 49 clusters with the largest cluster center is the XPO1 protein that interacts with 662 proteins, and 17 protein pairs that interact with each other. Therefore, the XPO1 is a very influential protein in Plasmodium Falciparum.

Keywords: SR-MCL Algorithm, Protein Interaction Network, Plasmodium Falciparum.



Protein memiliki peranan yang sangat penting dalam kehidupan. Setiap  protein berinteraksi  dengan  protein-protein  lain,  DNA,  dan  molekul-molekul  lainnya, sehingga  terbentuklah  jaringan  interaksi  protein  yang  berukuran  sangat  besar. Untuk memudahkan dalam menganalisisnya, diperlukan metode clustering. Algoritma  Soft  Regularized  Markov  Clustering  (SR-MCL)  yang  merupakan pengembangan metode clustering untuk mengurangi kelemahan dari Regularized Markov  Clustering  dan Markov  Clustering.  Pada  penelitian  ini,  SR-MCL  akan diterapkan  menggunakan  OpenMP,  yaitu  setiap  thread  menjalankan  SR-MCL dengan  parameter  inflasi  r  =  2,  3,  dan  4.  Hasil simulasi menunjukkan bahwa, berdasarkan waktu eksekusi tercepat dan iterasi terkecil, cluster terbaik diperoleh ketika r = 2 yang menghasilkan 40 iterasi dengan waktu eksekusi 613 detik. Pusat cluster adalah protein XPO1 yang berinteraksi dengan 662 protein dan 17 pasangan protein yang saling berinteraksi satu dengan lainnya. Oleh karena itu, protein XPO1 adalah protein yang sangat berpengaruh dalam pembentukan Plasmodium Falciparum.

Kata kunci: Algoritma SR-MCL, Jaringan Interaksi Protein, Plasmodium Falciparum.


A. Bustamam, M. Wisnubroto and D. Lestari, "Analysis of protein-protein interaction network using Markov clustering with pigeon-inspired optimization algorithm in HIV (human immunodeficiency virus)," in AIP Conference Proceedings, 2018.

R. Ginanjar, A. Bustamam and H. Tasman, "Implementation of regularized Markov clustering algorithm on protein interaction networks of schizophrenia's risk factor candidate genes," in International Conference on Advanced Computer Science and Information System (ICACSIS), pp. 297-302, 2016.

V. Satuluri, S. Parthasarathy and D. Ucar, "Markov clustering of protein interaction networks with improved balance and scalability," in The 1st ACM International Conference on Bioinformatics and Computational Biology, BCB 2010, pp. 247-256, New York, 2010.

A. Zhang, Protein interaction networks: computational analysis, Cambridge University Press, 2009.

C. Lin, Y. Cho, W. Hwang, P. Pei and Zhan, "Clustering methods in protein-protein interaction network," Knowledge Discovery in Bioinformatics: techniques, methods and application, pp. 1-35, 2007.

S. Dongen, Graph Clustering by Flow Simulation, Ph.D. Thesis: University of Utrecht, 2000.

Y. Shih and S. Parthasarathy, "Identifying functional modules in interaction networks through overlapping Marcov clustering," Bioinformatics, vol. 15:28, no. 18, pp. i473-i479, 2012.

V. Satuluri, Scalable clustering of modern networks, Doctoral Dissertation: The Ohio State University, 2013.

K. Rosen, Discrete Mathematics and Its Applications, New York: Mac Graw-Hill, inc, 2012.

S. Varia, Regularized Markov Clustering in MPI and Map Reduce, Doctoral dissertation: The Ohio State University, 2013.

Full Text: PDF

DOI: 10.15408/inprime.v1i2.12957


  • There are currently no refbacks.