Algoritma Markov Clustering adalah algoritma pengelompokan yang banyak digunakan pada bidang bioinformatik. Operasi utama pada algoritma ini adalah operasi ekspansi. Pada operasi ekspansi dilakukan perkalian dua buah matriks. Karena data pada bidang bioinformatik umumnya berukuran sangat besar dan memiliki tingkat sparsity yang sangat tinggi, diperlukan metode untuk menghemat penggunaan memori dan mempercepat proses komputasi. Sementara itu, Graphics Processing Unit (GPU) berkembang menjadi suatu platform komputasi paralel dengan performa yang lebih baik dari pada Central Processing Unit (CPU). Pada skripsi ini data yang diproses disimpan dalam bentuk sparse matriks ELL-R dan perkalian matriks yang dilakukan menggunakan Sparse Matrix Matrix Product (SpMM) ELL-R. SpMM ELL-R dibuat dengan melakukan Sparse Matrix Vector Product (SpMV) ELL-R beberapa kali. Algoritma MCL yang dibuat menggunakan komputasi paralel dengan GPU.

---

Abstract
Markov Clustering Algorithm is a clustering algorithm that used often in bioinformatics. The main operation of this algorithm is expand operation. The multiplication of two matrix was done in expand operation. Because data processed in bioinformatics usually have a vast amount of information and have high sparsity, a method to save memory usage and make the computating process faster is needed. Meanwhile, Graphics Processing Unit (GPU) developed into a parallel computing platform with better performance compared to Central Processing Unit (CPU). In this skripsi, processed data stored using ELL-R sparse matrix and matrix multiplication done using Sparse Matrix Matrix Product (SpMM) ELL-R. SpMM ELL-R made by doing Sparse Matrix Vector Product (SpMV) ELL-R several times. MCL Algorithm made using parallel computing with GPU.