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

Sebuah Tulisan Bioinformatika – Pemodelan Statistik Urutan (Part 2)

Tulisan di dalam part 2 ini lebih merupakan transisi antara pemodelan PSSM yang telah saia jelaskan sebelumnya di dalam part 1 dengan yang akan saia jelaskan kemudian di part 3. Dengan demikian, disini saia akan meneruskan tentang aplikasi pemodelan statistik PSSM dan kemudian mengenalkan tentang Markov model sebelum kita memasuki inti cerita berikutnya yang bertemakan hidden Markov model. So? Let’s get started…

A.        Position-Specific Iterated BLAST (PSI-BLAST)

Pada tulisan sebelumnya saia telah menyinggung bahwa terdapat sebuah program atau lebih tepatnya algoritma yang didedikasikan untuk menghasilkan matriks PSSM dari sebuah jajaran urutan banyak (multiple sequence alignment). Ya, algoritma tersebut adalah PSI-BLAST yang merupakan singkatan dari position-specific iterated BLAST. PSI-BLAST merupakan salah satu dari empat algoritma BLAST protein bersama dengan BLASTP, PHI-BLAST, dan DELTA-BLAST yang dapat dilihat pada tautan berikut:

http://blast.ncbi.nlm.nih.gov/Blast.cgi?PROGRAM=BLASTP&PAGE_TYPE=BlastSearch&LINK_LOC=blasthome

Seperti yang tersemat di dalam judulnya, PSI-BLAST mengkonstruksi matriks PSSM dari sebuah jajaran dan kemudian menggunakannya untuk pencarian similaritas database. Tahapannya terdiri atas dua jenis BLAST, yakni BLAST urutan (sequence BLAST) dan BLAST profil (profile BLAST). Keseluruhan proses PSI-BLAST dapat dilihat pada Gambar 1. Mula-mula, urutan query protein yang dimasukkan akan dicarikan urutan homolognya menggunakan BLASTP dan kemudian hasil pencarian tersebut dijajarkan bersama dengan urutan query membentuk jajaran urutan banyak. Setelah itu, jajaran ini dibuat menjadi sebuah matriks PSSM yang berisi frekuensi setiap residu asam amino pada setiap posisi. Matriks PSSM yang telah dikonstruksi kemudian digunakan dalam pencarian berikutnya yang disebut sebagai BLAST profil, yakni menyisir urutan di dalam database menggunakan profil PSSM.

Gambar 1. Skema PSI-BLAST.

Seperti yang telah kita pelajari sebelumnya, matriks PSSM lebih mewakili konsensus urutan yang ada di dalam jajaran, sehingga metode pencarian BLAST profil jauh lebih sensitif dibandingkan algoritma BLASTP. Lebih sensitif disini diartikan sebagai lebih mampu mendeteksi urutan homolog yang sinyal homologinya lemah. Urutan tambahan hasil pencarian kemudian dimasukkan ke dalam fase iterasi dimana urutan tersebut diintegrasikan ke dalam profil dan kemudian profil baru ini digunakan untuk pencarian lanjutan. Fase iterasi ini dapat diulang untuk jumlah tertentu atau terus diulang hingga tidak ada lagi urutan tambahan yang didapatkan.

Keunggulan dari PSI–BLAST ini terletak pada kemampuannya untuk menyusun profil dan terus menyempurnakannya seiring dengan setiap perulangan. Program tersebut juga dilengkapi dengan skema pembobotan untuk meningkatkan sensitivitas pencarian. Namun demikian, sensitivitas yang meningkat ini juga harus diiringi dengan penurunan spesifisitas/selektivitas. Tidak menutup kemungkinan bahwa BLAST profil ini akan memberikan urutan tambahan yang bersifat positif semu (false positif), yang artinya urutan tersebut cocok dengan profil namun tidak homolog (hayoo..ingat-ingat lagi perbedaan antara homologi dengan similaritas). Urutan positif semu ini, jika terus diintegrasikan akan berakibat pada terbentuknya matriks PSSM yang akan mengintegrasikan lebih banyak lagi urutan positif semu. Gejala ini disebut juga sebagai profile drift, sehingga pada umumnya fase iteratif PSI-BLAST dibatasi sebanyak 2-3 siklus saja dan urutan hasil pencarian juga perlu diinspeksi secara manual. Rincian mengenai PSI-BLAST dapat dibaca lebih lanjut di:

http://www.ncbi.nlm.nih.gov/books/NBK2590/

B.        Markov Model

Oke…seperti yang telah saia katakan, sebelum kita memasuki pemodelan statistik yang lebih umum yakni hidden Markov model (HMM), perkenankan saia untuk mengenalkan Markov model terlebih dahulu. Penggunaan Markov model sebagai pemodelan statistik urutan muncul karena terdapat kasus yang tidak mampu dimodelkan menggunakan PSSM. Pemodelan menggunakan PSSM tidak mampu untuk:

1.       mengenal keterkaitan antar posisi di dalam urutan,

2.       membuat pemodelan yang mengintegrasikan indel di dalamnya, atau

3.       mengenali cakupan suatu motif di dalam urutan.

Seperti yang telah kita ketahui dalam biologi molekular, terdapat kasus dimana kemunculah sebuah residu pada posisi tertentu mempengaruhi probabilitas kemunculan redisu pada posisi setelahnya. Ambil contoh pada kasus CpG island, sebuah daerah di dalam genom yang ditandai dengan perulangan dimerik C dan G. Kita dapat memancang ini sebagai sebuah Markov model, dimana adanya C pada sebuah situs akan mempengaruhi probabilitas munculnya G pada situs berikutnya. Apakah transisi semacam ini dapat ditangkap dalam pemodelan PSSM? Tentu saja tidak, karena PSSM hanya menangkap frekuensi kemunculan redisu pada setiap posisi tanpa memperdulikan probabilitas keterkaitan antara posisi satu dengan posisi berikutnya.

Oke, cerita sejarahnya selesai dan sekarang mari kita definisikan. Markov model merupakan distribusi probabilitas terkondisi untuk sebuah sistem dimana probabilitas sebuah kondisi x di waktu t hanya bergantung pada kondisi di waktu t–1  dan tidak pada kondisi di t–2 atau seterusnya. Dengan demikian, setiap kejadian menentukan probabilitas dari kejadian berikutnya yang dikuantifikasi dalam parameter probabilitas transisi. Untuk mendapatkan bayangan yang lebih jelas, lihatlah skema pada Gambar 2.

Gambar 2. Skema Markov Model.

Markov model dapat dibuat ke dalam berbagai tingkatan (orde) bergantung dari seberapa banyaknya posisi yang ingin dikaitkan. Sebagai contoh, Markov model orde nol menerangkan probabilitas kondisi saat ini tidak bergantung pada kondisi sebelumnya. Pemodelan ini umum digunakan terhadap urutan acak dimana setiap residu muncul dengan frekuensi yang setara. Markov model orde satu menerangkan probabilitas kondisi saat ini ditentukan oleh kondisi sebelumnya. Sama halnya seperti orde satu, Markov model orde dua menerangkan probabilitas kondisi saat ini ditentukan oleh dua kondisi sebelumnya. Pemodelan ini umum digunakan dalam pemodelan triplet nukleotida yang tentunya akan memiliki perbedaan pola antara urutan penyandi protein dengan urutan bukan penyandi protein.

Hingga pada saat ini mungkin ada di antara teman-teman yang bertanya, lantas apa makna dari kata “hidden” di dalam hidden Markov model. Well, dari apa yang saia jelaskan, kita mengasumsikan bahwa jajaran yang digunakan untuk pemodelan markov model merupakan sebuah jajaran yang tidak bercelah (ungapped). Padahal kenyataannya, kita sering menjumpai celah di dalam sebuah jajaran. Nah celah inilah yang dikatakan sebagai hidden states dari sebuah urutan atau dengan kata lain, kita membuat serta pemodelan probabilitas insersi dan delesi yang menyusun sebuah celah di dalam jajaran menggunakan HMM. Oke, kira-kira begitu dulu deh ceritanya. Pada cerita berikutnya, saia akan memfokuskan cerita pada hidden Markov model (HMM) yang tentunya lebih seru lagi.

Salam,

KohVic