Page 106 - Science and Technology For Society 5.0
P. 106
~ Science and Technology for Society 5.0 ~ 69
Tabel 1. Algoritma MCL
Input: matriks adjacency A dari graf G
Step 1: tambahkan self-loop pada graf, A = A + I
Step 2: bentuk matriks Markov M dengan menormalisasi kolom dari
matriks A
Step 3: ulangi step 4 sampai step 6
Step 4: M = Ekspansi (M) : = M dengan parameter ekspansi p ,
p
2
default p =
Step 5: M = Inflasi (M,r)
Step 6: M = Prune (M), Mij = 0 if Mij < minval
hingga global chaos matriks M < threshold e
Output: Matriks clustering M
7. Tribe Markov Clustering (Tribe MCL)
Algoritma Tribe MCL terdiri dari dua kegiatan utama, yaitu ekspansi
(perluasan) dan inflasi (penggelembungan) yang bergantian diulang sampai
konvergensi tercapai, yaitu matriks similar menjadi invariant selama siklus.
Sama halnya dengan Markov Clustering konvensional, pada Tribe MCL juga
terdapat penambahan gelung (self-adding). Berikut adalah langkah-langkah
pada algoritma Tribe MCL
Tabel 2. Algoritma Tribe MCL
Input : matriks yang terkait S0 dari graf G
(matriks simetri ini diperoleh dari nilai kesamaan antar
sekuens protein (E-value) pada program BLASTp yang
dapat direpresentasikan ke dalam bentuk graf terhubung
yang menunjukkan adanya interaksi antar protein yang
satu dengan yang lainnya)
Langkah 1 : tambahkan self-loop (gelung) S= S0+I
Langkah 2 : normalisasi matriks
Langkah 3 : lakukan ekspansi (perluasan)
Langkah 4 : lakukan inflasi (penggelembungan) dengan r>1