Klustering Data Ekspresi Gen dengan Metoda-metoda Berbasis Dekomposisi Nilai Singular Studi Kasus: Data Ekspresi Gen Kanker Paru

Kumpulan Makalah Seminar Semirata 2013

Fakultas MIPA Universitas Lampung

Klustering Data Ekspresi Gen dengan Metoda-metoda Berbasis Dekomposisi Nilai Singular Studi Kasus: Data Ekspresi Gen Kanker Paru Evi Noviani1, Yoga Satria Putra1, Kuntjoro Adji Sidarto2 1

FMIPA Universitas Tanjungpura Pontianak 2 FMIPA Institut Teknologi Bandung [email protected]

Abstrak.Pada penelitian ini telah dikelompokkan data ekspresi gen kanker paru dengan memanfaatkan dekomposisi nilai singular. pasien kanker yang tergolong pada sub tipe kanker paru yang sama dikelompokkan pada cluster yang sama berdasarkan data ekpresi gen yang berupa matriks berukuran puluhan ribu sampai ratusan ribu. Pembentukan cluster dilakukan dengan terlebih dahulu memodelkan ke dalam permasalahan optimisasi yaitu meminimumkan kesalahan penempatan pasien pada suatu kelompok, atau maksimumkan ketepatan dalam menempatkan pasien pada suatu kelompok. Masalah minimisasi/maksimisasi tersebut dapat diselesaikan dengan mengambil nilai singular kanan pertama dari dekomposisi nilai singular matriks data yang telah dinormalisasi. Dari proses ini didapatkan beberapa kelompok penderita kanker paru. Data ekspresi gen kanker paru telah dikelompokkan juga dengan menggunakan SVD-gaps. SVD-gaps ini mengambil k vektor singular kanan pertama, yang kemudian dicari selisih antara elemen vektor singular yang telah diurutkan. Dengan toleransi tertentu, maka selisih ini akan menentukan apakah dibentuk kelompok baru atau tidak. SVD-gaps menghasilkan 11 kelompok pasien kanker paru-paru. Kata Kunci.SVD-gaps, Dekomposisi Nilai Singular, Data Ekspresi Gen, Klustering.

PENDAHULUAN Rangkaian Deoxyribonucleic acid (DNA) merekam setiap karakteristik dan sifat setiap mahluk hidup. Gen yang dikodekan dalam DNA berperan sebagai pesan di dalam sel yang memberitahu bagaimana sel berperilaku. Gen yang berbeda memberitahu sel bagaimana membuat protein yang berbeda. Satu kode gen untuk satu protein. Setiap sel memiliki banyak gen dan karena itu dapat membuat banyak protein yang berbeda. Beberapa protein mengontrol bagaimana sel berperilaku. Contohnya protein yang memberitahu sel untuk mereproduksi dengan membagi dirinya menjadi dua[1].

Dewasa ini informasi yang terkandung dalam DNA yang nantinya akan menghasilkan protein tertentu dapat diukur oleh teknologi microarray. Data microarrayini menyajikan data tingkat ekspresi gen yang direpresentasikan melalui titik-titik warna.Satu sampel pada data microarrayterdiri dari ribuan atau

puluhan ribu gen. Pada pengolahan data microarrayinilah menjadi hal yang menarik manakala didapatkan informasi penting dari data yang berukuran besar. Data ekspresi gen yang dihasilkan dari data microarray juga dapat mengukur ekspresi manakala terjadi mutasi pada gen. Mutasi pada gen berarti bahwa gen tersebut telah rusak atau hilang. Sebuah mutasi dapat berarti bahwa terlalu banyak protein dibuat atau protein tidak dibuat sama sekali[1]. Seringkali, mutasi yang menyebabkankanker adalah mutasi padagen-gen yangmengatur pertumbuhan sel[2].

Data level ekspresi gen manusia berukuran relatif besar, sesuai dengan jumlah gen pada manusia. Jadi melalui level ekspresi setiap gen ini diperlukan suatu metoda sedemikian sehingga data microarray manusia yang memiliki puluhan ribu gen tersebut dapat terbaca karakteristiknya.Beberapa pasien dikelompokan menjadi satu kelompok jika Hal 185

Evi Noviani dkk: Klustering Data Ekspresi Gen dengan Metoda-metoda Berbasis Dekomposisi Nilai Singular Studi Kasus: Data Ekspresi Gen Kanker Paru

mereka mempunyai karakteristik yang sama dan akan terbagi dalam kelompok yang berbeda manakala karakteristiknya berbeda. Terdapat beberapa metode untuk mengklusterkan data dengan ukuran relatif besar. Diantaranya adalah matrix Factorisation[3], dan Dekomposisi Nilai Singular (Singular Value Decomposition/ SVD)[4,5, 6, 7]. Pada pencitraan digital, dekomposisi nilai singular telah digunakan. Pada pengiriman citra digital, reduksi dimensi pada data, sehingga hanya beberapa data saja yang digunakan akan tetapi gambar yang dikirim hampir sama dengan gambar asli, sangat menguntungkan terutama pada pemakaian memori. Pada penelitian ini data ekspresi gen yang berukuran relatif besar akan diklusterkan dengan teknik-teknik yang menggunakan dekomposisi nilai singular. Algoritma akan diimplementasikan pada data ekspresi gen pasien kanker paruparu[8].Garber mengelompokan data microarray pasienkanker paru dengan menggunakan teknik hierarchical clustering. Data yang dipublikasikan oleh Garber inilah yang akan disimulasikan dengan menggunakan teknik yang menggunakan dekomposisi nilai singular. METODE PENELITIAN Misalkan diberikan suatu matriks data ekspresi gen, sebut , dengan ukuran . Dengan menyatakan banyaknya gen dan menyatakan banyaknya pasien yang akan dikelompokkan. Elemen matriks pada baris dan kolom , , menyatakan level ekspresi gen pada pasien Data ekspresi gen dapat dinyatakan ke dalam graf bipartit dengan gen dan sampel masing-masing di kelompok titik yang berbeda [6].Bobot pada sisi yang menghubungkan antara gen dan sampel bernilai positif jika gen i relatif overHal 186

expressed di sampel j, dan bernilai negatif jika gen i relatif under-expressed di sampel j. Tujuan graf-bipartit tersebut adalah ingin membagi himpunan G(gen) kedalam 2 atau lebih grup, dan membagi himpunan S(sampel) kedalam 2 atau lebih grup, sehingga untuk masing-masing grup dan sampel level ekspresinya memiliki sifat hampir sama. Hal ini dikarenakan gen berkaitan yang terlibat dalam suatu proses akan aktif di himpunan sampel tertentu yang memiliki sifat hampir sama[6]. Misalkan adalah vektor indikator apakah gen i dimasukkan ke G1 ( )atau G2 ( ). Dan misalkan pula adalah vektor indikator apakah sampel j dimasukkan ke S1 ( ) atau S2 ( ).Tujuan dari pengelompokkan ini adalah diinginkan ketika , dan diinginkan , maka , ,dan . Dengan klustering ini diharapkan dapat memaksimalkan ketepatan dalam menempatkan gen dan sampel pada grup yang sesuai. Secara matematis dapat dituliskan sebagai berikut: ∑ (1) { } ∑ {

}

Ketika aij> 0 maka tempatkan gen i dan sampel j di grup yang sama piqi= 1. Dan ketika aij< 0 maka tempatkan gen i dan sampel j di grup lain yang berbeda piqi= -1.Dengan dimana ∑ | | ( ) dan ∑ | |. Matriks dengan ( ) menunjukkan setiap entri di dipangkatkan . Untuk selanjutnya, menunjukkan setiap elemennya dipangkatkan k, yaitu . Sehingga masalah optimisasi (1) tersebut dapat dituliskan sebagai berikut: ‖

‖ ‖

‖


Pada pengolahan data selanjutnya digunakan normalisasi data terlebih dahulu, yakni

dan

. Secara biologi, normalisasi data dapat menghilangkan efek karena adanya perbedaaan kondisi saat eksperimen dan dilakukan sedemikian sehingga penekanan ada pada pengelompokan(bi-clustering) data [9]. HASIL DAN PEMBAHASAN Pada penelitian ini akan dibahas implementasi dengan menggunakan algoritma dengan memanfaatkan hasil dari solusi analitik yang dibuat Higham, untuk selanjutnya disebut sebagai algoritma Higham. Untuk selanjutnya akan dibahas juga klustering dengan SVD-gaps pada data kanker paru-paru. SVD gaps pertama kali diperkenalkan oleh Douglas [5], yang menggunakannya untuk mengklusterkan data Yahoo!. Klustering Dengan Algoritma Higham Masalah klustering (2) dapat diselesaikan dengan teorema berikut[7]: Teorema Masalah dapat ‖ ‖ ‖ ‖ diselesaikan

mengambil ( ) dan ( ) dengan dan adalah vektor singular kiri dan kanan kesatu dari ( ) ( ) .[7] Berdasarkan teorema tersebut, didapat algoritma sebagai berikut[10]: 1. Input matriks 2. Hitung jumlah total ekspresi dari nilai mutlak dari elemen di setiap baris ( ) dan setiap kolom ( ). 3. Bentuk vektor dari jumlah total ekspresi baris ( ) dan kolom ( ) 4. Bentuk matriks diagonal dengan elemen diagonal utama adalah akar entri dari vektor dan , yang dinotasikan

dengan

dan


5. Hitung matriks 6. Hitung bentuk

. dekomposisi

nilai

singular dari , ambil vektor singular kiri dan kanan Pertama. Hitung

dan sebagai solusi dari masalah

clustering.Plot atau juga melibatkan singular kedua dan ketiga sebagai visualisasi hasil pengelompokan sampel data. Penyelesaian di atas berlaku untuk matriks ekspresi gen dengan elemen positif, negatif atau nol. Sedangkan khusus untuk matriks dengan elemen tak negatif, telah disimulasikan oleh Noviani,et. Al pada kankerkanker Leukemia[11]. Klustering Dengan Svd-Gaps Matriks data ekspresi gen, , dinormalisasi terlebih dahulu, baru kemudian dicari dekomposisi nilai singularnya. SVD yang digunakan adalah truncated SVD, yakni hasil dekomposisinya hanya diambil vektor saja. Nilai ditentukan yaitu pada saat nilai singular mengalami lengkungan (elbow).Hal ini berarti bahwa hanya diambil vektor singular yang memiliki pengaruh cukup besar terhadap data.Berikut algoritma SVD gaps yang digunakan pada penelitian ini: 1. Tentukan [ ] 2. Untuk i = 1 : k, 3. Untuk , pisahkan dan tentukan selisih(gaps) diantara vektor singular kananyang telah diurutkan.. 4. Jika gaps antara baris dan dari cukup besar, lebih dari sama dengan toleransi, maka bagi A dengan baris yang sesuai (columns). 5. Buat vektor kolom yang mengandung nama-nama cluster numerik dari untuk semua kolom. 6. Setelah menemukan untuk semua , bandingkan pola nama cluster untuk baris . Hal 187


pengurutan kembali dengan menggunakan algoritma Higham. Sedangkan Gambar 1(d) merupakan matriks hasil pengurutan dengan menggunakan SVD-gaps. Pada Gambar 1 dapat terlihatbahwa dengan algoritma Higham dan SVD-gaps, blok matriks dapat disusun kembali menjadi tiga. Hal ini menunjukkan bahwa dari data yang ada dapat dikelompokkan menjadi tiga kluster. Untuk selanjutnya, dilakukan simulasi pada data kanker paru-paru. Data ekspresi jik d n gen kanker paru-paru yang akan diolah, jik d n { terlebih dahulu diubah menjadi bentuk jik 1 d n | | sel inn matriks data. Entri pada baris i dan kolom Notasi rand menyatakan nilai yang dipilihj matriks tersebut menunjukkan ekspresi secara random dengan menggunakangen i pada pasien j. Pada Gambar 2 dapat distribusi uniform ( ).Sedangkandilihat hasil simulasi dengan menyatakan nilai yang dipilih secaramenggunakan algoritma Higham. random mengikuti distribusi normal dengan rataan 0 dan standar deviasi 1. Matriks di atas kemudian diacak kolom dan barisnya, kemudian diterapkan algoritma Higham dan SVD-gaps. Hasil algoritma tersebut dapat dilihat pada Gambar 1. Jika kolom dan memiliki pola nama cluster yang sama dalam , maka kolom dan termasuk kedalam cluster yang sama. Toleransi yang digunakan untuk penentuan kluster baru pada penelitian ini adalah zscore dari selisih antara nilai vektor singular yang telah diurutkan lebih dari 3,5. Implementasi Algoritma Algoritma Higham dan SVD gaps pertama-tama diimplementasikan pada matriks dengan aturan sebagai berikut:

-3

Nilai Vektor Singular Pertama dengan Skala

8 6 4 2 0

-2 -4 -6

5

5

10

10

15

15

20

20 5

10

15

5

(a)

10

15

10

15

(b)

5

5

10

10

15

15

20

20 5

10 (c)

15

5 (d)

Gambar 4Hasil algoritma higham dan svdgaps pada data simulasi Pada Gambar 1 (a) disajikan matriks awal yang dibentuk ( ). Kemudian matriks diacak baris dan kolomnya dan disajikan dalam Gambar 1(b). Matriks hasil acak inilah yang akan diterapkan algoritmaHigham dan SVDgaps. Dapat dilihat pada Gambar 1 (c) dan (d) matriks data dapat diurutkan kembali. Matriks terdiri dari tiga submatriks yang relatif berbeda dengan entri yang lain. Gambar 1(c) merupakan matriks hasil Hal 188

x 10

0

10

20

30

40 Pasien

50

60

70

80

Gambar 5Nilai vektor singular pertama yang telah diurutkan dengan algoritma higham Gambar 2 menyatakan nilai vektor singular pertama dari data ekspresi gen kanker paru yang telah diurutkan. Dari sini terlihat belum adanya ketentuan pasien mana tergolong pada kluster apa. Pembentukan kluster baru terbatas dengan subjektifitas seseorang dalam melihat pengelompokannya. Jika nilai vektor singular pertama dan kedua diplot, maka akan didapatkan seperti pada Gambar 3.



-3

6

x 10

Nilai Vektor Singular Kanan Kedua

2 0 69

53 24 48

7 42

4

25

41 36 8 62 12 67 52 64

70 15 44 33 2 28 4 3 71 4355 63 51 2068 40 56 13

45 65 66

58

35

11

17

50 49 30

61 72 29

-2

14 18 16 6

5

10

-4

31 34

1 60

-6

27

57

26 23 9 22 39 54 1932

21

59

37 -8 -10 -6

38 47 73 46 -4

-2 0 2 4 Nilai Vektor Singular Kanan Pertama

6

8 -3

x 10

Gambar6Nilai vektor Singular Pertama yang telah diurutkan dengan algoritma Higham

Jika diperhatikan, data-data pada Gambar 3 akan sulit untuk menentukan pasien termasuk kluster mana. Oleh karena itu, selanjutnya klustering dicoba dengan menggunakan SVD-gaps. Dengan menggunakan algoritma pada SVD-gaps dapat diketahui bahwa pasien kanker paru-paru terbagi menjadi 11 kluster. Pasien normal termasuk dalam satu kluster. Sedangkan kluster 3 didominasi oleh pasien Adenocarsinoma. Hasil penghitungan dapat dilihat pada Tabel 1.

TABEL 3Hasil klustering pasien kanker paru Nomor Pasien 28 29 30 31 32 53 62 Nomor Pasien 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 26 27 33 34 35 36 37

Nomor Baru Hasil Pengacakan 12 10 4 16 13 17 46 Nomor Baru Hasil Pengacakan 53 71 58 67 50 15 49 47 56 51 21 34 55 39 68 11 63 52 18 44 32 41 6 23 8 73 35 26

Cluster

Diagnosa Awal(Garber, 2001)

Nomor Pasien

1 1 1 1 1 1 2 Cluster

306-99_normal 219-97_normal 222-97_normal 315-99_normal 314-99_normal 157-96_SCC 315-99_SCLC Diagnosa Awal(Garber, 2001)

43 44 45 46 47 48 49 Nomor Pasien

3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

181-96_Adeno 132-95_Adeno 198-96_Adeno 156-96_Adeno 187-96_Adeno 180-96_Adeno 199-97_Adeno_p 199-97_Adeno_c 12-00_Adeno 137-96_Adeno 68-96_Adeno 257-97_Adeno 204-97_Adeno 11-00_Adeno 320-00_Adeno_c 320-00_Adeno_p 319-00PT_Adeno 313-99MT_Adeno 313-99PT_Adeno 185-96_Adeno 178-96_Adeno 165-96_Adeno fetal_lung 319-00MT2 319-00MT1 218-97_Adeno 223-97_Adeno 80-96_Adeno

51 52 54 55 56 57 58 59 60 63 65 66 67 68 72 73 39 41 22 23 24 25 64 40 69 71 70 61

Nomor Baru Hasil Pengacakan 43 1 40 57 45 36 60 Nomor Baru Hasil Pengacakan 20 59 2 5 22 19 3 9 29 48 64 72 66 31 38 61 24 65 7 37 70 28 30 27 62 42 25 54

Cluster

Diagnosa Awal(Garber, 2001)

3 3 3 3 3 3 3 Cluster

139-97_LCLC 219-97_SCC 75-95_combined 166-96_SCC 246-97_SCC_c 246-97_SCC_p 42-95_SCC Diagnosa Awal(Garber, 2001)

3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 5 6 6 6 6 6 7 8 8 9 10

245-97_SCC 239-97_SCC 69-96_Adeno 232-97_node 232-97_SCC 220-97_node 220-97_SCC 3-00_SCC 58-95_SCC 230-97_SCLC 207-97_SCLC 299-99_Adeno 161-96_Adeno 6-00_LCLC 147-96_Adeno 237-97_Adeno 184-96_node 234-97_Adeno 306-99_node 306-99_Adeno 226-97_Adeno 222-97_Adeno 314-99_SCLC 184-96_Adeno 256-97_LCLC 248-97_LCLC 191-96_Adeno 315-99_node

Hal 189


Nomor Pasien 38 42

Nomor Baru Hasil Pengacakan 14 33

Cluster

3 3

Diagnosa Awal(Garber, 2001) 265-98_Adeno 59-96_SCC

Dari Tabel 1 dapat terlihat bahwa pasien normal terkelompokkan menjadi satu kelompok. Sedangkan kluster 3 didominasi oleh pasien adenocarsinoma. Kluster 8 hanya terdiri dari pasien LCLC. Pada pembagian kluster dengan SVDgaps tersebut, dapat terlihat pada Tabel 1 terdapat kluster yang hanya terdiri dari satu anggota.Terdapat pasien SCC tergolong pada kluster 3 yang anggota klusternya didominasi pasien Adeno. Yang menyebabkan hal ini terjadi sangat dipengaruhi oleh penentuan toleransi yang digunakan untuk pembentukan suatu kluster. Pada penelitian ini digunakan nilai zscore 3,5. Selain penentuan toleransi gaps, hasil klustering juga dipengaruhi pemilihan nilai k pada saat penentuan truncated-SVD. KESIMPULAN Data ekspresi gen telah dapat dikelompokkan dengan menggunakan teknik dekomposisi nilai singular. Dengan menggunakan algoritma Higham belum ada aturan mekanisme suatu pasien termasuk kluster mana, akan tetapi penentuan kluster dilakukan secara subjektif dengan melihat plot nilai vektor singular kanan pertama. Hal ini akan efektif ketika data yang diteliti nilai vektor singular kanannya antara kluster yang satu dengan yang lainnya terpisah sangat jelas. Tetapi untuk data kanker paru pada penelitian ini hampir tidak dapat dibedakan antara kluster yang satu dengan yang lain. Berbeda halnya dengan algoritma Higham, pada algoritma SVDgaps sudah ada kriteria penentuan suatu kluster, yaitu melalui besarnya toleransi pada selisih antara nilai vektor singular kanan. Setiap pasien sudah ditetapkan termasuk kluster mana. Namun demikian, Hal 190

Nomor Pasien 50

Nomor Baru Hasil Pengacakan 69

Cluster

11

Diagnosa Awal(Garber, 2001) 245-97_node

untuk memperbaiki ketepatan dalam menentukan kluster diperlukan kajian mengenai besarnya toleransi ini dan penentuan sampai dimensi berapa harus dihitung truncated-SVDnya. UCAPAN TERIMA KASIH Penelitian ini merupakan bagian dari Penelitian Pekerti tahun 2012 yang dibiayai Dikti.Terima kasih penulis ucapkan kepada Jurusan Matematika dan Fakultas MIPA Universitas Tanjungpura dan Dept. Matematika FMIPA ITB serta Dirjen Dikti yang telah mendukung penulis. DAFTAR PUSTAKA _____,

How

Cancer

Start.

http://www.cancerresearchuk.org/cancerhelp/about-cancer/what-is-cancer/cells/howcancer-starts#how_starts. Akses tanggal 30

April 2013 _____, The Relationship Between DNA and Cancer. http://www.foundationmedicine.com/patientsdna-cancer.php. Akses tanggal 30 April

2013 Brunet, JP., Pablo Tamayo, T.R. Golub, & J.P. Mesirov. (2004). Metagenes and Molecular Pattern Discovery Using Matrix Factorization. Procidings of The National Academy of Sciences: 101.p. 4164-4169. Noviani, Evi & Putra,Y. S., (2010), Pengklasteran Pasien Kanker Leukemia Berdasarkan Data Ekspresi Gen dengan Menggunakan Dekomposisi Nilai Singular. Journal of Mathematics and Its Applications (Limits): 7, p. 49-56 Douglas, E.P. (2008), Clustering datasets with Singular Value Decomposition, Thesis Master of Science in



Mathematics, The Graduate school of the college of charleston.

National Academy of Sciences: 98, p. 13784–13789.

Higham, Desmond J, Gabriela K., J. Keith Vass. 2005. Analysis of the singular value

Kluger, Y., R Basri, J.T Chang, et al.(2003). Spectral Biclustering of Microarray Data: Coclustering Genes and Conditions. Genome Research.13, 703-716.

decomposition as a tool for processing microarray expression data. In: Proceedings of ALGORITMY 2005, 13-18 March 2005, p.250-259, Podbanské, Slovakia.

Higham, Desmond J, Gabriela K., J. Keith Vass. 2007. Spectral Analysis of Twosigned Microarray Expression Data. Mathematical Medicine and Biology: 24, p. 131-148 Garber, M. E., et.al.,(2001). Diversity of Gene Expression in Adenocarcinoma of The Lung. Procidings of The

Noviani, Evi, K. A. Sidarto, Y. S. Putra, (2012). Pengelompokan Pasien Kanker Liver Berdasarkan Data Ekspresi Gen dengan Struktur Papan Catur. Prosiding KNM XVI- 3-6 Juli 2012- UNPAD, Jatinangor. Noviani, E. dan Putra, Y.S., (2010) Pengklasteran Pasien Kanker Leukemia Berdasarkan Data Ekspresi Gen dengan Menggunakan Dekomposisi Nilai Singular. Limits. 7, 49-55.

Hal 191

Klustering Data Ekspresi Gen dengan Metoda-metoda Berbasis Dekomposisi Nilai Singular Studi Kasus: Data Ekspresi Gen Kanker Paru

Recommend Documents