Page 94 - Science and Technology For Society 5.0
P. 94
~ Science and Technology for Society 5.0 ~ 57
menjadi beberapa kelompok (cluster) berdasarkan kemiripan dan klasifikasi.
Salah satu proses pengelompokan adalah pengelompokan graf yang
merupakan pengelompokan simpul-simpul pada sebuah graf berdasarkan
pada ada atau tidaknya hubungan antara simpul dan seberapa kuat
hubungan yang terjadi antara satu simpul dengan simpul yang lainnya. Salah
satu metode pengelompokkan graf adalah markov clustering.
Markov Clustering Algoritm (MCL) merupakan metode yang dilakukan
dengan beberapa iterasi (bootstrapping) dan memiliki faktor
penggelembungan (inflation) yang mempengaruhi kepadatan (granularity)
dari kelompok yang dihasilkan, dimana kelompok (cluster) tersebut
setimbang dan non-hirarki (flat) (Dongen, 2000). Algoritma ini
dikembangkan oleh Stijn van Dongen pada tahun 2000 dan telah
diimplementasikan di berbagai bidang ilmu, salah satunya di bidang
bioinformatik seperti pada jaringan interaksi protein, analisis famili protein
dan gen dari spesies tunggal maupun antarspesies, analisis ruang sekuens,
orthologus groups, protein kinase, protein tersekretasi, protein mata,
elemen genetis yang bersifat mobile, dan penentuan fungsi protein. Selain
itu, MCL juga banyak dipakai di bidang corpus linguistic, pencarian gambar
yang bersifat content-based, analisis peer-to-peer network, dan analisis
jejaring sosial (Dongen, 2008).
Beberapa faktor yang mendorong banyaknya penggunaan algoritma
MCL meliputi kemampuan algoritma ini untuk menghasilkan clustering non-
hierarkis yang setimbang (well-balanced), merupakan metode
bootstrapping, memiliki parameter natural (inflation) yang dapat
mempengaruhi glanuralitas dari cluster yang dihasilkan, dapat
diimplementasikan dalam sparse graf/matriks yang berimplikasi pada
skalabilitas yang baik, serta adanya hasil matematis yang dapat menjelaskan
hubungan erat dari setiap iterasi proses MCL, interpretasi cluster, inflation,
dan jumlah dari cluster yang dihasilkan (Dongen, 2008). Metode lain yang
merupakan pengembangan dari MCL adalah Tribe Markov Clustering.
Dalam melakukan proses clustering, salah satu hal yang menjadi tujuan
utama adalah meminimalisir jumlah cluster yang berukuran besar, sebab
kompleks protein cenderung hanya memiliki sekitar 15-30 node. Serupa
dengan itu, output berupa singleton cluster juga perlu diminimalisir
jumlahnya, sebab node tunggal tidak mengandung cukup informasi yang
bisa digunakan untuk mengidentifikasi interaksi dalam sebuah network.
Pada bidang bioinformatika, data yang dikelompokkan biasanya berukuran