Yup, KohVic kembali lagi dengan topik yang
sama. Masih seputar Hidden Markov Model, karena materi ini yang lagi in di
kepala saia…hehehe. So, gimana soal hitung-hitungan probabilitas lempar koin
nya? Atau adakah yang mencoba praktek lempar koin di rumah? Yaa, saia berharap
setelah membaca tulisan part 1 teman-teman mendapatkan konsep awal dari HMM.
Oke, sekarang kita akan mencoba menggunakan teknik HMM ini di dalam dunia
bioinformatika. Pada kennyataannya, banyak analisis di dalam bioinformatika
yang mengandalkan pemodelan HMM baik yang berdiri sendiri maupun sebagai bagian
dari keseluruhan analisis. Prediksi gen dan pengelompokan famili protein
merupakan dua analisis yang menggunakan HMM sebagai pondasi utamanya. Nah di
dalam tulisan part 2 ini, saia akan membahas tentang pengelompokan famili
protein. Mari lanjutttt…
Kita tahu bahwa protein terdiri dari asam amino
yang terangkai satu sama lain melalui ikatan peptida. Dari sekian banyak asam
amino, hanya 20 jenis yang digunakan oleh organisme untuk membentuk protein dan
mereka disebut sebagai asam amino standar. Dalam kebanyakan kasus, protein satu
dan lainnya biasanya dikelompokkan berdasarkan fungsi dan strukturnya. Jika dilihat
lebih seksama, protein yang fungsinya sangat mirip umumnya memiliki urutan yang
sangat mirip pula. Hal inilah yang menjadi dasar penggunaan data urutan asam
amino untuk prediksi struktur dan fungsi sehingga dapat dikelompokkan ke dalam
famili tertentu. Secara teknis, pengelompokkan urutan protein yang mirip satu
sama lain juga cukup sederhana dengan hanya mengandalkan penjajaran urutan
banyak dan penghitungan skor similaritas. Hmm..apakah ini artinya masalah telah
selesai? Tentu saja belum. Karena banyak kasus di dalam pengelompokan protein
dimana anggotanya memiliki urutan yang begitu berbeda sehingga sinyal
kemiripannya terlalu lemah untuk dideteksi oleh penjajaran urutan standar.
HMM dapat digunakan untuk menjawab permasalahan
pengelompokan famili protein ini. Secara konsep, HMM merupakan pemodelan
probabilistik yang dikonstruksi dari data jajaran kelompok protein dan kemudian
digunakan untuk memprediksi probabilitas apakah sebuah urutan protein merupakan
anggota dari kelompok tersebut atau tidak. Sekarang perhatikan jajaran protein
pada Gambar 1. Untuk mengkonstruksi model HMM, terlebih dahulu kita harus
menjajarkan urutan protein yang sudah diketahui termasuk ke dalam satu
kelompok. Di dalam HMM, kelompok urutan ini disebut juga sebagai dataset
training. Selanjutnya, dari dataset ini kita perlu menetapkan parameter theta
yang bertugas ‘menyaring’ jajaran awalan ini dari kolom kurang informatif yang
ditandai dengan banyak celah. Dalam hal ini kita mengatur nilai theta sebesar
satu, yang berarti kolom manapun yang memiliki celah lebih dari satu dianggap
tidak informatif dan tidak akan diikutsertakan pada konstruksi profil. Dengan
pengaturan tersebut, dua kolom yang terletak di antara kolom 5 dan 6 tidak akan
diikutsertakan dan profil yang dikonstruksi hanya memuat 8 kolom.
Hingga pada tahap ini teman-teman mungkin
merasa teknik ini mirip seperti pada konstruksi matriks position-specific
scoring matrix (PSSM) yang telah dikenalkan sebelumnya. Eitt nanti dulu…kita
ikuti saja ceritanya. Nah sekarang dengan mengandalkan profil pada Gambar 1,
hitung probabilitas bahwa urutan protein ADDAFFDF merupakan anggota dari
jajaran protein. Mudah saja, tinggal kalikan nilai frekuensi masing-masing asam
amino pada matriks profil sesuai dengan urutan asam amino. Disini, kita akan
mendapat 1 x 1/4 x 3/4 x 1/5 x 1 x 1/5 x 3/4 x 3/5 = 0,003375. Nilai tersebut
masih 13,5 kali lebih tinggi dibandingkan nilai probabilitas terendah (yaitu
0,00025) bagi sebuah urutan untuk bisa masuk ke dalam kelompok. Oke, masalah
selesai lalu dimana HMM-nya?
Coba perhatikan sekali lagi matriks profil pada
Gambar 1 dan renungkan apakah ada yang aneh? Ketemu? Oke, sekarang saia tanya
apakah kita bisa menghitung probabilitas yang sama untuk urutan ADDAFFDF dan AAFFDF?
Nah inilah kelemahannya, matriks profil tersebut tidak dapat mengakomodasi
urutan yang lebih pendek atau lebih panjang darinya. Dengan kata lain,
pemodelan yang dilakukan oleh profil tersebut tidak dapat mengakomodasi delesi
dan insersi yang jelas pasti ada di dalam urutan protein. Kembali kepada HMM
yang berfokus pada hidden states, apakah sekarang teman-teman sudah tahu apa
hidden states di dalam kasus ini? Yup, insersi dan delesi itulah hidden states
nya. Oke, sekarang kita konstruksi lagi pemodelan HMM yang mengikutsertakan
state insersi dan delesi. Pemodelan diagram HMM untuk mengakomodasi penjajaan
urutan cukup sederhana. Model tersebut hanya terdiri dari tiga state, yakni
match (M), insersi (I), dan delesi (D) yang dengan sejumlah tanda panah yang
mengarah ke masing-masing state (Gambar 2).
Gambar 2. Diagram HMM untuk penjajaran urutan. |
Well, seperti pada tulisan sebelumnya, kita
tentu harus mengkonversi diagram HMM ini menjadi semacam ‘grafik Viterbi’
sedemikian rupa sehingga dapat mengakomodasi setiap situs di dalam jajaran
dataset training. Kembali pada kasus penjajaran tiga urutan di atas, ‘grafik
Viterbi’ HMM setengah jadi pada Gambar 3 menyajikan pemodelan HMM untuk tiga
urutan: ADDAFFDF, AFDDAFFDF, dan AAFFDF. Terlihat bahwa ‘grafik Viterbi’ ini
mampu mengakomodasi jajaran urutan sekalipun ketiganya memiliki panjang yang
berbeda.
Gambar 3. Konstruksi model HMM untuk mengakomodasi urutan ADDAFFDF, AFDDAFFDF, dan AAFFDF. |
Nah, berbekal contoh pada Gambar 3 tersebut,
kita dapat mengeneralisir konstruksi ‘grafik Viterbi’ agar dapat mengakomodasi
dataset urutan secara umum. Konstruksi ‘grafik Viterbi HMM general’ tersebut
dapat dilihat pada Gambar 4. Mula-mula kita membuat state M sepanjang n residu
dari jajaran urutan banyak yang telah di-filter dengan parameter theta.
Selanjutnya, tambahkan sebanyak n+1 state I dan kemudian sebanyak n state D.
Perhatikan juga tanda panah yang
mengarah dari satu state ke state yang lain. Pastikan juga bahwa seluruh tanda
panah yang dibuat mengarah ke kanan. Terakhir, tambahkan state mula-mula (S)
dan state akhir (E).
Gambar 4. Tahapan konstruksi ‘grafik Viterbi HMM general’ untuk mengakomodasi dataset urutan. Dalam model ini, urutan yang dapat diakomodasi adalah sepanjang delapan residu. |
Setelah membuat ‘grafik Viterbi HMM general’,
kita dapat melihat bahwa ‘grafik Viterbi’ yang ada sekarang sudah dapat
mengakomodasi masing-masing urutan yang terdapat dalam dataset training (Gambar
5). Oke, selanjutnya adalah menghitung probabilitas transisi antar state dan
probabilitas emisi residu pada masing-masing posisi 1 hingga 8 menggunakan
dataset training. Serupa dengan model pelemparan koin, kita dapat menghitung
probabilitas transisi antar state (transition l,k) berdasarkan rasio
perpindahan state p1 ke p2 (Tl,k)
terhadap perpindahan state p1 ke state lainnya (Tl,j). Sebagai contoh, perhatikan bahwa terdapat empat jalur yang
melewati state M5. Tiga dari empat jalur tersebut bergerak menuju state I5,
sedangkan satu jalur terakhir langsung mengarah ke state M6. Dengan demikian,
hitungannya menjadi:
Transisi M5,I5 =
3/4
Transisi M5,M6 =
1/4
Transisi M5,D6 =
0
Perhitungan
probabilitas emisi (emisi k,b) dinyatakan sebagai probabilitas dari
HMM mengemisikan residu b pada state k. Nilai ini dapat dihitung dari rasio
jumlah residu b diemisikan oleh state
k terhadap asam amino lainnya pada
state yang sama. Sebagai contohnya:
Emisi M2,A =
0
Emisi M2,C =
1/2
Emisi M2,D =
1/4
Emisi M2,E =
0
Emisi M2,F =
1/4
Untuk state
insersi, jika menghadapi kasus dimana terdapat lebih dari dua daerah insersi
maka perhitungan probabilitas emisi untuk state tersebut menggunakan nilai
kumulatif dari seluruh situs yang dikategorikan ke dalam state tersebut.
Sebagai contohnya, state I5 memiliki dua kolom residu dengan total residu A
sebanyak 3 buah dan residu C dan D masing-masing 1 buah. Dengan demikian
perhitungan probabilitas emisinya menjadi:
Emisi I5,A =
3/5
Emisi I5,C =
1/5
Emisi I5,D =
1/5
Emisi I5,E =
0
Emisi I5,F =
0
Gambar 5. Pencocokan model HMM general terhadap lima urutan yang terdapat di dalam jajaran dataset training. |
Oke, jadi hitung semua probabilitas transisi
dan emisinya dengan cara di atas yak. Sudah selesai? Kalau belum silahkan lihat
Gambar 6 sajah..heheheh. Sip, dengan semua ini kita sudah siap untuk mengkalkulasi
nilai probabilitas urutan baru dan menentukan apakah dia akan ‘join to the club’
atau tidak. Kasus pertama, urutannya adalah A - - AFCCADF. Perhitungan
probabilitasnya sama dengan kasus pelemparan koin dan hasilnya adalah….jrengg..jrenggg…
0,00000073728. Yaa saia tahu kalau nilai ini cukup kecil, jadi biasanya
diekspresikan dalam skala minus logaritmik. Dengan demikian, -log (0,00000073728)
= 6.132367547. Setelah kita mendapatkan nilai probabilitas (atau lebih tepatnya
nilai likelihood) nya, lantas urutan baru ini ‘join to the club’ atau tidak.
Nah pertanyaan ini harus dijawab dengan menguji HMM terlebih dahulu menggunakan
kontrol positif dan negatif untuk menentukan ambang batas probabilitasnya.
Gambar 6. ‘Grafik Viterbi HMM general’ konsensus hasil penggabungan seluruh ‘grafik Viterbi’ pada Gambar 4 beserta nilai probabilitas transisi (l,k) dan emisi (k,b). |
Sebagai penutup, ada satu hal penting yang
perlu ditambahkan ke dalam model HMM pada Gambar 5. Kita perlu menghilangkan
angka probabilitas 0 pada nilai probabilitas transisi maupun emisi. Hal ini
perlu untuk mengantisipasi probabilitas akhir yang bernilai 0 apabila salah
satu residu di dalam urutannya mengenai state dengan probabilitas 0 di dalam
HMM. Teknik penghilangan angka 0 ini disebut dengan pseudocount (simbol sigma),
alias menambahkan semacam nilai probabilitas semu pada state dengan nilai
probabilitas 0. Terakhir, saia ingin bertanya apakah teman-teman pembaca tidak
merasa aneh dengan proses penghitungan probabilitas terhadap urutan baru yang
tadi dilakukan? Jika tidak, persilahkan saia untuk memberitahu satu hal. Di
dalam prosesnya, sebuah urutan baru tentu saja tidak datang dengan membawa
celah (gap) di dalamnya atau dengan kata lain, urutan pada kasus di atas hanya
dapat dilihat sebagai AAFCCADF. Hal ini menyulitkan karena kita sebenarnya
tidak tahu dimana letak celahnya. So, pada part berikutnya kita akan
mempelajari pemodelan yang lebih rinci lagi yang melibatkan konstruksi grafik
Viterbi yang sebenarnya (ingat kembali dari awal saya selalu menambahkan tanda
kutip pada setiap tulisan ‘grafik Viterbi’) sehingga kita dapat memberikan
pemodelan yang tepat untuk menangani celah pada urutan.
KohVic