PENERAPAN ALGORITMA K-MEANS UNTUK PENGELOMPOKAN DATA EKSPRESI GEN
LAPORAN TUGAS AKHIR
Disusun sebagai syarat kelulusan tingkat sarjana
oleh : Aloysius Nugroho W / 13501042
PROGRAM STUDI TEKNIK INFORMATIKA SEKOLAH TEKNIK ELEKTRO DAN INFORMATIKA INSTITUT TEKNOLOGI BANDUNG 2008
Lembar Pengesahan Program Studi Sarjana Teknik Informatika Penerapan Algoritma K-Means Untuk Pengelompokan Data Ekspresi Gen
Tugas Akhir Program Studi Sarjana Teknik Informatika ITB
Oleh Aloysius Nugroho W / 13501042
Telah disetujui dan disahkan sebagai laporan tugas akhir di Bandung, pada tanggal 30 Juni 2008
Pembimbing II
Pembimbing I
Masayu Leylia Khodra S.T., M.T. NIP. 999023508
Henny Yusnita Zubir B.S., M.T. NIP. 132208711
ii
RINGKASAN Teknologi microarray dapat mengukur tingkat ekspresi gen pada organisme tertentu. Karena hasil dari microarray tersebut berupa matriks ekspresi gen yang pada umumnya berskala besar, diperlukan aplikasi yang dapat melakukan clustering terhadap data ekspresi gen tersebut. Clustering dapat memberikan informasi kedekatan antar gen maupun sampel. Algoritma clustering yang digunakan adalah simple k-means.
Pada tugas akhir ini dilakukan implementasi algoritma k-means untuk pengelompokan data ekspresi gen dengan menggunakan struktur data list of pointer. Aplikasi dibangun dalam bentuk aplikasi desktop dengan menggunakan lingkungan pemrograman Borland Delphi 7.0. Aplikasi ini mampu membaca data ekspresi gen dalam format tab-delimited text file dan mengeluarkan hasil berupa cluster dan anggota – anggotanya. Aplikasi ini diharapkan dapat membantu penelitian ahli biologi dalam memprediksi kedekatan antar gen maupun sampel.
Pengujian aplikasi dilakukan terhadap data iris (150 data) dan data ekspresi gen ragi (6221 gen dan 79 sampel). Hasil clustering dengan data iris menunjukan algoritma kmeans yang diimplementasikan valid. Berdasarkan perbandingkan hasil clustering data ekspresi gen dengan data Biogrid, hanya sebagian gen dalam cluster yang dianalisis punya keterkaitan satu sama lain.
Kata kunci: microarray, data ekspresi gen, clustering, k-means
iii
KATA PENGANTAR Puji syukur ke hadirat Tuhan Yang Maha Esa, karena atas rahmat dan bimbingan-Nya penulis dapat menyelesaikan tugas akhir yang berjudul ”Penerapan Algoritma KMeans Untuk Pengelompokan Data Ekspresi Gen”. Tugas akhir ini dilaksanakan sebagai syarat kelulusan tingkat Sarjana Strata I dari Departemen Teknik Informatika Institut Teknologi Bandung.
Selama masa pengerjaan tugas akhir ini, banyak pihak yang telah membantu dan mendukung penulis. Untuk itu penulis mengucapkan terima kasih yang sebesar – besarnya kepada: 1. Ibu Henny Yusnita Zubir dan Ibu Masayu Leylia Khodra selaku pembimbing tugas akhir yang telah banyak memberikan masukan dan bantuan. 2. Ibu Ayu Purwarianti dan Bapak Bugi Wibowo yang telah memberikan masukan selama prasidang dan sidang tugas akhir. 3. Ibu Harlili selaku reviewer pada sidang tugas akhir dan selaku dosen wali penulis. 4. Keluarga penulis tercinta atas segala doa, petunjuk, dukungan moral dan material, serta semangat dan kesabarannya. 5. Pasangan jiwa penulis: Arti Purwanti atas segala doa, dukungan, semangat dan kesabarannya. 6. Seluruh staf dosen, tata usaha, perpustakaan dan dukungan teknis yang telah membantu penulis selama perkuliahan. 7. Sahabat penulis: Yoppy dan Meiry, Cicely, Ivan, Albin, Citrady, Byaryoga, Eni, Asri dan seluruh rekan – rekan IF 2001 dan KMK atas semangat dan dukungannya selama kuliah dan pengerjaan tugas akhir. 8. Pihak – pihak lain yang penulis tidak dapat sebutkan satu – persatu, yang telah membantu penulis baik secara langsung maupun tidak langsung.
Semoga tugas akhir ini dapat bermanfaat bagi perkembangan ilmu pengetahuan dan seluruh pihak yang membutuhkannya khususnya untuk mereka yang tertarik dengan iv
bidang Bioinformatika. Penulis menyadari bahwa tugas akhir ini masih banyak memiliki kekurangan. Oleh karena itu, kritik dan saran dari pembaca sangat penulis hargai dan harapkan.
Bandung, Juni 2008
Penulis
v
DAFTAR ISI
Lembar Pengesahan.................................................................................................... ii RINGKASAN ............................................................................................................. iii KATA PENGANTAR................................................................................................ iv DAFTAR ISI............................................................................................................... vi DAFTAR GAMBAR................................................................................................ viii DAFTAR TABEL ...................................................................................................... ix DAFTAR ALGORITMA ........................................................................................... x BAB I PENDAHULUAN..........................................................................................I-1 1.1 Pengantar......................................................................................................I-1 1.2 Rumusan Masalah........................................................................................I-2 1.3 Tujuan ..........................................................................................................I-2 1.4 Batasan Masalah ..........................................................................................I-2 1.5 Metodologi...................................................................................................I-3 1.6 Sistematika Pembahasan..............................................................................I-3 BAB II DASAR TEORI ......................................................................................... II-1 2.1 DNA (Deoxy-Ribonucleic Acid) ................................................................ II-1 2.2 Data Ekspresi Gen...................................................................................... II-2 2.3 Analisis Data Ekspresi Gen ....................................................................... II-4 2.3.1 Unsupervised Analysis .......................................................................II-6 2.3.2 Supervised Analysis ...........................................................................II-8 BAB III ANALISIS DAN PERANCANGAN..................................................... III-1 3.1 Analisis Perangkat Lunak ......................................................................... III-1 3.1.1 Deskripsi Umum Sistem .................................................................. III-1 3.1.2 Spesifikasi Kebutuhan Perangkat Lunak ......................................... III-2 3.1.3 Analisis Masukan............................................................................. III-3 3.1.4 Analisis Keluaran............................................................................. III-4 3.2 Analisis Algoritma dan Struktur Data....................................................... III-5 3.2.1 K-means ........................................................................................... III-5 3.2.2 Struktur Data.................................................................................... III-6 3.3 Perancangan Antarmuka Perangkat Lunak............................................... III-7 BAB IV IMPLEMENTASI DAN PENGUJIAN .................................................IV-1 4.1 Implementasi............................................................................................. IV-1 4.1.1 Lingkungan Implementasi ............................................................... IV-1 4.1.2 Spesifikasi Produk ........................................................................... IV-2 4.1.3 Batasan Implementasi ...................................................................... IV-2 4.1.4 Implementasi Antar Muka ............................................................... IV-2 4.1.5 Implementasi Modul ........................................................................ IV-4 4.1.6 Interpretasi Hasil.............................................................................. IV-4 4.2 Pengujian................................................................................................... IV-5 4.2.1 Tujuan Pengujian ............................................................................. IV-5 vi
4.2.2 Lingkungan Pengujian ..................................................................... IV-5 4.2.3 Skenario Pengujian dan Kriteria Keberhasilan ................................ IV-5 4.2.4 Hasil Pengujian ................................................................................ IV-7 4.3 Analisis Hasil Pengujian ......................................................................... IV-10 BAB V KESIMPULAN DAN SARAN.................................................................. V-1 5.1 Kesimpulan ................................................................................................ V-1 5.2 Saran .......................................................................................................... V-1 DAFTAR REFERENSI ............................................................................................. xi DAFTAR PUSTAKA................................................................................................ xii
vii
DAFTAR GAMBAR Gambar II-1 Gambar II-2 Gambar II-3 Gambar III-1 Gambar III-2 Gambar III-3 Gambar III-4 Gambar III-5 Gambar III-6 Gambar IV-1 Gambar IV-2 Gambar IV-3 Gambar IV-4 Gambar IV-5 Gambar IV-6 Gambar IV-7
Proses pengubahan DNA menjadi protein [BRA01] .........................II-2 Contoh microarray [AND06].............................................................II-3 Analisis unsupervised (kiri) dan supervised (kanan) [BRA00] .........II-5 Gambaran Umum Perangkat Lunak................................................. III-1 Cuplikan data masukan aplikasi [EIS05]......................................... III-3 Contoh keluaran aplikasi.................................................................. III-4 Contoh algoritma K-means .............................................................. III-6 Rancangan antarmuka input............................................................. III-7 Rancangan antarmuka output........................................................... III-8 Implementasi Antarmuka Data Input .............................................. IV-2 Implementasi antarmuka output....................................................... IV-3 Hasil aplikasi dengan data iris ......................................................... IV-7 Hasil WEKA dengan data iris.......................................................... IV-7 Cuplikan hasil pengujian dengan data ragi (cluster kecil)............... IV-8 Cuplikan hasil pengujian dengan data ragi (cluster sedang) ........... IV-9 Cuplikan hasil pengujian dengan data ragi (cluster besar) .............. IV-9
viii
DAFTAR TABEL Tabel II-1 Tabel III-1 Tabel IV-1 Tabel IV-2 Tabel IV-3
Matriks Ekspresi Gen Saccharomyces cerevisiae [EIS05]................II-4 Format File Masukan....................................................................... III-3 Komponen Antarmuka Data Input .................................................. IV-3 Komponen Antarmuka Output......................................................... IV-3 Implementasi modul......................................................................... IV-4
ix
DAFTAR ALGORITMA Algoritma II-1 Algoritma K-means [HOO04] ...........................................................II-7
x
