Pengembangan Algoritma Deteksi Komunitas dan Centrality dalam Menentukan Protein Target pada Kanker

Abstract

Komunitas dan centrality sangat penting untuk memahami sistem yang kompleks seperti jaringan protein dalam analisis jaringan. Masalah deteksi komunitas adalah bagaimana membagi jaringan yang direpresentasikan dalam bentuk graph menjadi beberapa kelompok simpul yang mempunyai kepadatan yang tinggi, memiliki karakteristik atau sifat yang berbeda. Kualitas komunitas yang terbentuk oleh algoritma deteksi komunitas dapat ditentukan dengan nilai modularity. Salah satu algoritma terkenal dan banyak menjadi rujukan dalam menyelesaikan masalah deteksi komunitas adalah algoritma greedy modularity. Algoritma ini melakukan eksplorasi untuk mencapai nilai modularity tertinggi pada setiap iterasi untuk mendapat komunitas terbaik. Kelemahan algoritma greedy modularity pada deteksi komunitas adalah dapat terjebak pada solusi lokal optimal. Untuk itu penelitian ini mengembangkan strategi disassembly greedy modularity untuk meningkatkan modularity tersebut dengan eksplorasi yaitu lepas simpul dan pecah komunitas. Terdapat empat strategi melepas simpul yaitu melepas simpul secara random/acak dengan distribusi uniform, melepas simpul lemah, melepas simpul yang mempunyai nilai embeddedness rendah, serta melepas simpul yang tidak membentuk triad. Terdapat lima strategi membongkar komunitas yaitu membongkar komunitas secara acak dengan distribusi uniform, membongkar komunitas yang lemah, membongkar komunitas dengan internal edge density yang rendah, membongkar komunitas dengan triad participation ratio yang rendah serta membongkar komunitas dengan conductance yang tinggi. Data yang digunakan dalam penelitian adalah data real-world dan data sintetis. Data real-world yang digunakan meliputi data karate Zachary, Dolphins, Les Miserables, Polbooks, Adjnoun serta Football. Sedangkan data sintetis yang digunakan adalah Lancichinetti–Fortunato–Radicchi(LFR). Hasil yang diperoleh menggunakan disassembly greedy modularity berupa peningkatan modularity dibandingkan dengan greedy modularity untuk semua dataset tersebut. Bahkan dibandingkan dengan 25 algoritma lainnya, algoritma disassembly greedy modularity menduduki mayoritas menduduki urutan pertama berdasarkan modularity. Di lain pihak, centrality adalah konsep yang digunakan untuk mengukur pentingnya suatu simpul dalam jaringan. Terdapat beberapa jenis centrality yang umum digunakan dalam analisis jaringan, di antaranya adalah degree centrality, closeness centrality, dan betweenness centrality. Namun demikian, degree, closeness dan betweenness centrality tersebut dihitung berdasarkan struktur jaringan, belum memperhatikan komunitas di dalamnya. Sehingga, centrality tersebut perlu dikembangkan agar dapat mempertimbangkan komunitas dalam jaringan, yang dalam penelitian ini disebut dengan community consideration degree centrality, community consideration closeness centrality, dan community consideration betweenness centrality. Variabel a dengan rentang [0,1] digunakan sebagai pertimbangan komunitas. Semakin rendah nilai a akan lebih mempertimbangkan komunitas, sementara semakin tinggi nilai a akan lebih mempertimbangkan jaringan secara keseluruhan. Hasil yang diperoleh menggunakan dataset karate Zachary dan dolphins dapat melibatkan simpul pada komunitas yang lebih beragam. Secara khusus, algoritma disassembly greedy modularity dan community consideration centrality dalam penelitian ini digunakan untuk mengelompokkan protein target pada kanker dan mengungkap protein yang menjadi hallmark of cancer. Data genetik pada kanker paru-paru adenokarsinoma diambil dari empat pangkalan data: TCGA, IntOGen, Bioportal, dan Cosmic, yang selanjutnya data tersebut dipergunakan untuk memperoleh jaringan interaksi protein melalui pangkalan data String. Algoritma disassembly greedy modularity digunakan untuk mendeteksi stuktur komunitas pada jaringan interaksi protein tersebut. Hasil dari algoritma ini terbentuk 11 komunitas dengan ukuran berbeda dengan dua komunitas besar, empat komunitas menengah, dan lima komunitas kecil yang sebagian besar mempunyai asosiasi fungsional melalui enrichment analysis, lebih baik daripada hasil yang diperoleh dengan algoritma greedy modularity. Hasil berikutnya adalah, bahwa community consideration degree, closeness dan betweenness centrality dengan a=0,1 dan a=0,2 dapat mengungkap protein hallmark of cancer yang lebih banyak daripada centrality yang tidak mempertimbangkan komunitas. Centrality ini juga dibandingkan dengan berbagai centrality yang lain, seperti eigen vector centrality, Katz centrality, information centrality, load centrality, subgraph centrality, harmonic centrality, second order centrality, distinctive centrality maupun viral rank centrality. Hasilnya adalah community consideration centrality mengungguli kesemua centrality pembanding dalam mengungkapkan banyaknya protein hallmark of cancer. Lebih lanjut, penentuan nilai a juga dipengaruhi struktur komunitas yang diperoleh. Apabila terdapat struktur komunitas terdapat pada jaringan yang dicirikan dengan modularity yang tinggi, maka a cenderung bernilai kecil. Sebaliknya apabila tidak ada struktur komunitas, maka nilai a cenderung mendekati 1, dalam arti bahwa centrality tidak dipengaruhi oleh komunitas. Mengingat potensi yang ada, metodologi ini mempunyai implikasi umum dan memberikan peluang untuk diterapkan di berbagai bidang yang lebih luas. Ukuran centrality seringkali mengabaikan struktur yang rumit dalam suatu jaringan. Dengan melibatkan komunitas, pendekatan community consideration centrality memungkinkan analisis jaringan yang lebih rinci dan akurat, sehingga meningkatkan pemahaman tentang pentingnya keberadaan simpul secara individu maupun pengaruhnya secara kolektif pada sebuah komunitas. Community consideration centrality mempunyai potensi yang tidak hanya terbatas pada jaringan biologis tetapi juga berlaku pada bidang lain seperti analisis jaringan sosial, organisasi, dan jaringan komunikasi maupun jaringan lainnya yang ada dalam sebuah sistem yang kompleks.

Community and centrality are critical to understanding complex systems, such as protein networks, in network analysis. The community detection problem involves dividing a network in graph form into several groups of nodes with a high density and different characteristics or properties. Modularity can determine the quality of the community formed by the community detection algorithm. The greedy modularity algorithm is a well-known algorithm with many references for solving community detection problems. This algorithm performs exploration to achieve the highest modularity value at each iteration to obtain the best community. The weakness of the greedy modularity algorithm in community detection is that it can become stuck in a locally optimal solution. Therefore, this study develops a disassembly greedy modularity strategy to increase modularity through exploration: disassembly nodes and disassembly communities. There are four strategies for disassembling nodes: releasing nodes randomly with a uniform distribution, releasing weak nodes, releasing nodes with low embeddedness values, and releasing nodes that do not form a triad. There are five strategies for disassembling communities: random with uniform distribution, weak communities, communities with low internal density, communities with low triad participation ratio, and communities with high conductance. The data used in the research were real-world and synthetic data. The real-world data used includes data on Zachary's karate, Dolphins, Les Miserables, Polbooks, Adjnoun and Football. The synthetic data used was LFR. The results obtained using disassembly greedy modularity show an increase in modularity compared to greedy modularity for all of these datasets. Compared to the 25 other algorithms, the disassembly greedy modularity algorithm occupies the first place in the majority. On the other hand, centrality is a concept used to measure the importance of a node in a network. Several types of centralities are commonly used in network analysis, including degree, closeness, and betweenness centralities. However, degree, closeness, and betweenness centrality are calculated based on the network structure without paying attention to the community within it. Therefore, centrality needs to be developed to consider the community in the network, which in this research is called community consideration degree centrality, community consideration closeness centrality, and community consideration betweenness centrality. Variable a in the range [0,1] is used as a community consideration. The lower the a value, the more the community will be considered, whereas the higher the a value, the more the network as a whole will be considered. The results obtained using the Zachary Karate and Dolphin datasets can involve nodes in more diverse communities. Specifically, the disassembly greedy modularity and community consideration centrality algorithms in this research were used to group target proteins in cancer and obtain proteins that are hallmarks of cancer. Data on genetic mutations in lung adenocarcinoma were obtained from four databases: TCGA, IntOGen, Bioportal, and Cosmic, which were then used to obtain protein interaction networks via the String database. Greedy modularity disassembly algorithm to detect community structure in protein interaction network. The results of this algorithm formed 11 communities of different sizes, with two large communities, four medium communities, and five small communities, most of which had functional associations through enrichment analysis. The following result is that community consideration degree, closeness, and betweenness centrality with a=0.1 and a=0.2 can reveal more cancer protein hallmarks than centrality that does not consider the community. Next, it was compared with other centralities, such as eigenvector centrality, Katz centrality, information centrality, load centrality, subgraph centrality, harmonic centrality, second-order centrality, distinctive centrality, and viral rank centrality. The result is that community consideration centrality outperforms all in revealing the protein hallmarks of cancer. Furthermore, determining the a value was also influenced by the community structure obtained. If a community structure in a network is characterized by high modularity, a tends to have a small value. However, if there is no community structure, the value of a tends to be close to 1 because the community does not influence centrality. Given the existing potential, this methodology has general implications and the potential to be applied in a wider variety of fields. Traditional centrality measures often ignore the complex substructures within a network. By involving the community, the community consideration centrality approach allows for more detailed and accurate network analysis, thereby increasing the understanding of the importance of individual nodes and their collective influence on a community. Community consideration centrality has the potential not only to be limited to biological networks but also to other fields, such as social network analysis, organizational studies, communication networks, and other networks that exist in a complex system.