Metagenome Fragment Clustering Menggunakan Algoritme Pillar K-Means Secara Paralel Dalam Model Mapreduce
View/ Open
Date
2016Author
Fathurrohman
Kusuma, Wisnu Ananta
Sukoco, Heru
Metadata
Show full item recordAbstract
Metagenom adalah DNA yang berasal dari komunitas mikroba yang dapat mengandung dari berbagai jenis spesies. Hal ini membuat rekonstruksi DNA dari metagenom tidak dapat langsung dilakukan. Mikroba yang heterogen pada metegenom tersebut, memungkinkan terjadinya kesalahan perakitan fragmen metagenom yaitu munculnya interspecies chimeras akibat tersambungnya fragmen antara spesies. Oleh karena itu diperlukan sebuah metode untuk mecegah terjadinya kesalahan tersebut. Salah satu cara untuk melakukan pencegahan terjadinya kesalahan perakitan fragmen metagenom sebelum rekonstruksi DNA dilakukan adalah dengan melakukan proses binning. Clustering merupakan sebuah cara untuk mengelompokan objek-objek yang mempunyai kemiripan ke dalam kelompok tertetntu, sehingga dapat digunakan untuk melakukan binning.
Salah satu algoritme clustering adalah K-Means. K-Means Clustering tidak menjamin hasil clustering yang unik. Untuk mendapatkan hasil clustering optimal dapat dilakukan dengan melakukan penentuan centroid awal terlebih dahulu dengan menggunakan algoritme Pillar sebelum proses clustering dilakukan. Algoritme Pillar sangat efektif untuk menentukan posisi awal centroid pada K-Means dan meningkatkan ketepatan hasil clustering.
Selain itu, data metagenom merupakan data dengan ukuran yang sangat besar, sehingga bisa digolongkan sebagai big data. Data berukuran besar dapat menjadi sebuah masalah komputasi dalam pengelolaan data secara sekuensial. Salah satu solusi untuk menangani masalah data berukuran besar ialah dengan memproses data secara paralel. MapReduce merupakan sebuah model pemrograman yang penerapannya digunakan untuk memproses data berukuran besar secara paralel.
Hasil clustering data metagenom, baik dengan algoritme K-Means maupun dengan algoritme Pillar K-Means pada masing-masing data uji pada penelitian ini menunjukkan kesimpulan hasil yang sama, di mana secara dominan genus Agrobacterium selalu menggerombol dalam satu cluster, sedangkan genus Bacillus and Staphylococcus secara dominan selalu bergerombol dalam cluster yang sama. Jumlah iterasi dan waktu eksekusi pada penerapan Pillar K-Means dalam clustering data lebih efisien dibandingkan pada penerapan metode K-Means. Penggunaan model MapReduce memberikan kinerja yang lebih baik dibandingkan dengan proses sekuensial, di mana speedup yang dihasilkan berkisar antara 60,00 sampai 69,03 dengan nilai efisiensi rata-rata sebesar 400%. Penentuan nilai centroid awal pada algoritme Pillar menambah waktu total clustering dibandingkan dengan penentuan centroid dengan K-Means, sehingga masih bisa memungkinkan untuk dilakukan optimalisasi algoritme Pillar pada penelitian selanjutnya.