Sebuah Tulisan Bioinformatika – Pemodelan Statistik Urutan (Part 3)

Hmm…sudah part 3 yak. Saatnya mulai serius nih berarti. Tentang part 3 ini saia berencana membahas tentang hidden Markov model (HMM) yang mencakup konsep dan aplikasinya. Enaknya mulai darimana yak? Gini aja deh, karena di luar sana banyak yang bilang HMM itu bagus, tentunya itu pernyataan yang sangat relatif toh. Kalau bagus itu, lebih bagus dari apa? Oke, fixed!! Saia akan mulai dengan membahas kelemahan PSSM dan kemudian membahas bagaimana pemodelan dengan HMM dapat menanggulangi kelemahan tersebut.

A.        Kelemahan PSSM

Kita tahu bahwa PSSM merupakan sebuah pemodelan secara sederhana dengan menyimpan informasi frekuensi setiap residu nukleotida/asam amino pada setiap posisi di dalam jajaran tak bercelah (ungapped alignment). Beberapa kelemahan PSSM antara lain:

1.         Tidak dapat menangkap sinyal keterkaitan antar posisi

PSSM hanya merangkum probabilitas untuk masing-masing posisi dan dengan demikian mengasumsikan tidak ada kaitan (demikian juga probabilitasnya) antar posisi. Untuk lebih jelasnya, perhatikan Gambar 1 di bawah ini:

Gambar 1. Konstruksi PSSM untuk sebuah jajaran protein.

 Jika kita menghitung probabilitas antar posisi, kita mendapatkan bahwa P(RD) = 0,36 dan P(QH) = 0,16 karena itu yang terobservasi pada jajaran kita. Namun perhatikan bahwa P(QD) dan P(RH) yang tidak ada pada jajaran sama-sama bernilai 0,24; lebih tinggi dari P(QH) yang terobservasi pada jajaran. Ini berarti motif berakhiran QD atau RH lebih mungkin untuk muncul di dalam urutan, namun perhitungan probabilitas semacam ini tidak dilakukan di PSSM.

2.         Sulit mengenali pola urutan yang mengandung insersi-delesi (indel)

Sebagai konsekuensi dari konstruksinya yang menggunakan jajaran tak bercelah, pola urutan yang dibuat dengan PSSM mengandung panjang tertentu yang sifatnya tetap. Pola demikian akan sulit digunakan untuk urutan dengan motif yang mengandung indel (Gambar 2).

Gambar 2. Kesulitas PSSM untuk mengenali motif yang mengandung indel.

Lebih luas lagi, konsekuensi yang diakibatkan oleh kekakuan PSSM ini adalah bahwa pemodelan ini tidak dapat mengenali motif dengan panjang yang bervariasi serta sulit membedakan sebuah motif di dalam urutan dari background noise.

B.        Hidden Markov Model (HMM)

Well, sepertinya jagoan kita dalam pemodelan statistik urutan kali ini harus bisa menangani kedua masalah tersebut agar bisa kita katakan “lebih hebat”. Permasalahan pertama jelas sudah ditangani dari Markov model itu sendiri yang memang mengintegrasikan keterkaitan antara probabilitas antar posisi. Pemasalahan kedua inilah yang menuntut pengembangan Markov model untuk dapat mengakomodasi indel sehingga menjadi hidden Markov model. Namun sebelum kita memasuki inti cerita, perkenankan saia untuk mengenalkan beberapa istilah berikut:

• Probabilitas awal (initial probability; π): Probabilitas sebuah residu untuk muncul mengawali sebuah HMM.
• Probabilitas emisi (emission probability; e): Probabilitas munculnya sebuah residu pada posisi tertentu.
• Probabilitas transisi (transition probability; a): probabilitas transisi dari sebuah posisi ke posisi berikutnya (jangan dikacaukan dengan mutasi transisi & pada DNA loh).

Oke, pertanyaannya jelas…apa bedanya Markov model dengan HMM? Pada part sebelumnya saia menjelaskan bahwa Markov model membuat pemodelan probabilitas sebuah posisi ditentukan dari probabilitas posisi sebelumnya. Nah terdapat dua asumsi pada definisi tersebut. Asumsi pertama adalah bahwa jajaran yang digunakan adalah jajaran tak bercelah sama seperti pada PSSM, yang berarti Markov model tidak terima indel. Kedua, sifat linear (korespondensi 1-1) dari Markov model mencerminkan bahwa satu-satunya penentu probabilitas pada sebuah posisi adalah dari probabilitas posisi sebelumnya yang hanya satu. Kedua asumsi ini tidak membuat Markov model lebih hebat dari PSSM, sehingga kita perlu membuat pemodelan yang lebih umum lagi.

Saia ingin mengingatkan lagi bahwa celah yang terdapat di dalam jajaran dan merupakan HIPOTESIS mengenai adanya peristiwa insersi atau delesi di masa lalu. Karena kedua fenomena ini terjadi di masa lalu, jelas kita tidak mengobservasinya di dalam urutan (yang kita lihat di dalam jajaran itulah HIPOTESIS-nya, bukan FAKTA nya). Nah kedua hal inilah yang disebut sebagai hidden states di dalam HMM. Dengan tambahan ini, kita dapat memodifikasi skema Markov model seperti pada Gambar 3.

Gambar 3. Mengkonstruksi HMM dari Markov model. I = insersi; D = delesi; M = match (cocok).

Terdapat tiga jenis ketegori states di dalam pemodelan statistik urutan menggunakan HMM, yakni match/cocok (M); insersi (I) dan delesi (D). Perhatikan bahwa residu berbeda dalam sebuah posisi juga termasuk ke dalam kategori M. Di dalam HMM, perpindahan dari state satu ke state lainnya mengikuti probabilitas transisi (a) tertentu; dan setiap state memiliki simbol yang memiliki probabilitas emisi (e) nya masing-masing. Untuk lebih jelasnya, perhatikan contoh kasus pada Gambar 4.

Gambar 4. Pemodelan HMM untuk jajaran protein. Perhatikan bahwa terdapat dua alternatif model HMM yang dapat dibuat dari jajaran urutan yang sama.

Model HMM yang terdapat pada Gambar 4 jelas menggambarkan kondisi yang diperlukan untuk menghasilkan seluruh urutan yang terdapat pada jajaran di sebelah kirinya. Namun demikian, lebih dari satu model HMM dapat dikonstruksi dari jajaran urutan yang sama. Pada akhirnya, probabilitas dari masing-masing state-lah yang akan menentukan model mana yang akan dikonstruksi. Pada Gambar 4, model HMM sebelah atas lebih cenderung untuk dipilih karena posisi ketiga lebih banyak mengandung celah dibandingkan dengan residu T, yang artinya probabilitas bahwa T merupakan residu hasil insersi lebih tinggi dibandingkan dengan probabilitas T sudah ada disana dan urutan lainnya yang mengalami delesi T.

C.        Algoritma Konstruksi HMM

Terdapat tiga jenis algoritma yang digunakan dalam ilmu ke-HMM-an ini. Algoritma pertama merupakan algoritma Baum-Welch yang digunakan untuk mengkonstruksi model HMM dan mengestimasi setiap parameter probabilitasnya. Setelah HMM dikonstruksi, sebuah urutan (berikut dengan celahnya) dengan probabilitas tertinggi dapat dihasilkan dengan menghitung produk probabilitas transisi dan emisi setiap posisinya menggunakan algoritma Viterbi. Urutan beserta probabilitas tertinggi menurut model HMM ini kemudian dapat digunakan untuk pencarian database menggunakan algoritma forward.

Ketiga algoritma tersebut terdapat dalam program HMMER (dibaca hammer). Program ini tersedia dalam bentuk executable yang dapat diunduh di:

http://hmmer.janelia.org/ atau secara online (hanya pencarian berbasis HMM) di:

http://www.ebi.ac.uk/Tools/hmmer/

Well, saia rasa segitu dulu tulisan tentang HMM nya. Untuk berikutnya saia masih mikir-mikir apakah ingin memperdalam materi HMM dengan detail kalkulasi probabilitas nya atau tidak. Yaa ditunggu saja deh, kalau misalnya ada part berikutnya berarti jadi diadakan…hehehehe.

Ucapan Terima Kasih dan Referensi Lanjutan

Dalam tulisan kali ini saia ingin mengucapkan terima kasih kepada Oom Barry Grant dari University of Michigan, Ann Harbor atas slide kuliah Lecture 13 & 14 nya yang begitu inspiratip tentang pemodelan statistik urutan ini (link nya dapat dikunjungi di: http://thegrantlab.org/). Teman-teman dapat mengunduh slide PPT yang bersangkutan untuk pembelajaran lebih lanjut. Untuk teman-teman yang tertarik untuk mempelajari lebih lanjut, saia sangat menyarankan untuk membaca bukunya Durbin et al. (1998).

Pustaka

1.         Durbin, R., S. Eddy, A. Krogh, & G. Mitchinson. 1998. Biological Sequence Analysis: Probabilistic Models of Protein and Nucleic Acids. Cambridge University Press: UK.

2.         Grant, B. 2011. Advanced database searching: sequence patterns, profiles & hidden Markov models; lecture 13. http://thegrantlab.org. Diakses pada 27 Juni 2015.

3.         Grant, B. 2011. Advanced database searching: sequence patterns, profiles & hidden Markov models; lecture 14. http://thegrantlab.org. Diakses pada 27 Juni 2015.

Salam,

KohVic