Kamis, 30 Juli 2015

Sebuah Tulisan Bioinformatika – Menujum Motif Urutan

Melanjutkan dari topik tulisan sebelumnya, kali ini saia ingin membahas salah satu aplikasi pemodelan statistik urutan yang banyak dipakai dalam dunia bioinformatik. Yaa seperti judul yang tertera, aplikasi tersebut adalah menujum atau memprediksi motif urutan…hahaha. Jadi, setelah teman-teman membaca tulisan ini, saia berharap setidaknya teman-teman punya gambaran tentang bagaimana menjadi seorang ahli nujum bioinformatika itu. Yasuda, kita mulai saja yak.

Asal muasal dari munculnya ilmu nujum motif urutan ini berawal dari dua faktor, yakni kemelimpahan data urutan namun sedikit yang mengurus dan keterbatasan teknologi untuk membuktikan informmasi yang terkandung di dalam urutan. Yaa seperti yang kita tahu dalam pelajaran biologi molekular, sebuah genom pada organisme itu mengandung seluruh informasi yang mencakup ekspresi gen, regulasi ekspresi gen, dan juga yang tidak memiliki informasi sama sekali alias DNA sampah. Nah impian para ahli biologi molekuler adalah mengungkap seluruh informasi tersebut di dalam urutan DNA dan protein. Untuk apa? “Mengungkap rahasia alam”, katanya “…dan mendapat hadiah Nobel”, sambungnya. Caranya sebenarnya mudah saja. Untuk setiap potongan atau genom secara keseluruhan, lakukan pengujian:
  • Apakah segmen ini menghasilkan protein atau tidak
  •  Apakah segmen itu mengatur penghasilan protein atau tidak
  • Apakah segmen ini itu memiliki fungsi atau tidak
Yaa..kira-kira begitulah. Tapi lantas kenapa kita perlu mempelajari ilmu nujum ini jikalau solusinya begitu sederhana? Saia punya 3 kata untuk menjawab hal itu: SULIT, MAHAL, dan LAMA. Jadi daripada kita langsung melakukan pengujian untuk seluruh genom secara membabibuta, ada baiknya kita mencari wangsit dulu mengenai baiknya segmen mana yang harus diuji…hehehe.

Oke, jadi apa yang dimaksud dengan motif? Motif adalah sebuah segmen pada urutan dengan pola tertentu pada sejumlah urutan dan biasanya mengindikasikan fungsi tertentu. Dalam prediksi motif ini, kita memberlakukan dua asumsi untuknya: (i) motif merupakan segmen dengan panjang tertentu yang bersifat tetap antar urutan satu dengan lainnya dan (ii) motif terdapat di seluruh urutan yang digunakan dalam proses prediksinya. Dengan kata lain, jika kita dapat mencari segmen motif ini, hal tersebut dapat mengantarkan kita lebih cepat mengenai pengungkapan fungsi suatu daerah di dalam DNA atau protein dan karena sebab inilah prediksinya menjadi penting. Dengan semakin melimpahnya data urutan DNA dan protein, prediksi motif menjadi semakin mungkin untuk dilakukan dan hasil yang diberikan pun semakin akurat. Terdapat dua kelompok metode yang digunakan untuk memprediksi motif ini. Kelompok metode pertama menggunakan pendekatan berbasis jajaran urutan banyak sedangkan kelompok kedua menggunakan pendekatan tanpa jajaran urutan. Hmm…mungkin jajaran urutan sudah terlalu mainstream tampaknya.

Saia rasa kelompok pertama mungkin akan lebih familiar dalam bayangan teman-teman. Dua jenis metode yang menggunakan pendekatan ini adalah metode ekspresi regular dan metode model statistik. Metode ekspresi regular memprediksi motif dengan terlebih dahulu membuat konsensus dari segmen di dalam jajaran yang dianggap memiliki pola tertentu (Gambar 1). Terkait dengan ekspresi regular ini terdapat beberapa aturan penulisan yang harus dipatuhi. Setiap karakter di dalam motif harus dipisahkan dengan tanda “–”. Sebuah posisi yang hanya ditempati oleh satu jenis residu saja dituliskan dengan menggunakan residu yang bersangkutan. Apabila posisi tersebut ditempati oleh lebih dari satu residu, maka redisu yang bersangkutan dituliskan menggunakan tanda kurung kotak [ ]. Kemudian, jika sebuah posisi memiliki seluruh kecuali satu residu saja, maka residu yang bersangkutan dituliskan menggunakan tanda kurung kurawal { }. Posisi yang tidak memiliki residu yang spesifik dituliskan dengan tanda N (untuk urutan DNA) atau X (untuk asam amino). Jumlah repetisi dari sebuah pola dituliskan menggunakan tanda kurung ( ).
Gambar 1. Contoh motif yang dihasilkan dari jajaran urutan.

Jadi, bermodalkan ekspresi regular ini, kita mencari motif yang direpresentasikannya di dalam urutan lainnya. Ketemu? Bisa ya bisa tidak. Ya jika memang terdapat segmen dengan pola serupa dengan ekspresi reguler dan tidak jika segmennya berbeda. Pada kebanyakan kasus, ternyata motif itu agak fleksibel dan agak sulit jika sebuah motif harus mengikuti persis seperti yang ada di ekspresi regular. Pengembangan lebih lanjut untuk mengatasi masalah ini adalah dengan menggunakan pemodelan statistik, yakni memodelkan jajaran segmen bukan sebagai sebuah ekspresi reguler, namun sebagai profil urutan. Pemodelan statistik yang digunakan bisa berupa PSSM atau HMM (baca tulisan sebelumnya), namun HMM lebih umum digunakan.

Selesai cerita? Tidak juga. Walaupun HMM itu hebat, namun akurasi dari metode model statistik tersebut sangat bergantung dari kualitas jajaran urutan yang dihasilkan. Padahal pada tulisan yang sebelum-sebelumnya kita mengetahui bahwa sebuah jajaran urutan banyak dihasilkan menggunakan metode heuristik yang tidak menjamin akurasinya. Selain daripada itu, seandainya jajarannya cukup akurat sekalipun, kelompok metode berbasis jajaran ini agak sulit dalam mengakomodasi urutan yang berkerabat jauh. Jika urutan-urutan berkerabat jauh tersebut dimasukkan ke dalam pemodelan, maka besar kemungkinan prediksi motif yang dihasilkan akan banyak mengandung hasil positif semu, yakni urutan yang dianggap sebagai motif padahal sebenarnya tidak.

Jika memang begitu keadaannya, berarti apakah ada metode prediksi motif yang tidak mengandalkan jajaran urutan banyak sebagai masukan datanya? Untungnya di jaman serba ada ini, jawabannya ya ada (kalau ngga ya bubar deh, ga jadi posting tulisan ini). Oke, sekarang kita memasuki pendekatan kedua, yakni kelompok metode prediksi motif tanpa jajaran urutan. Konon katanya, metode dalam kelompok ini diilhami oleh permainan dadu loh. Ada tiga metode yang tergolong ke dalam kelompok ini, yakni randomized algorithm, expectation maximization (EM), dan Gibbs sampling. Pendekatan yang dilakukan ketiga metode ini sebenarnya mirip satu dengan lainnya, yakni pendekatan berbasis perulangan (iterasi) dengan perbaikan dari fase satu ke fase berikutnnya. Inspirasi dari kelompok metode ini adalah, jika iterasinya dilakukan cukup banyak, mungkin jutaan kali, yaaa mungkin saja motif umum antar urutan bisa ditemukan. Cukup…optimistis kan? Heheheh. Nah coba lihat Gambar 2 dulu deh.

Gambar 2. Skema proses algoritma expectation maximization (EM).

Saia tidak ingin membahas detil prosesnya yang cukup panjang, namun saia ingin fokus kepada optimisme yang saia sebutkan barusan. Well, mengapa si pembuat algoritma tersebut bisa begitu optimis bisa menemukan motif umum antar urutan hanya dengan mengulang-ulang pencarian? Kita melihat proses yang tampaknya sia-sia ini karena kita memiliki asumsi bahwa keteracakan posisi antar urutan satu dengan lainnya. Agak mustahil sepertinya untuk mencari pola umum tanpa menjajarkan posisi antar urutan terlebih dahulu. Namun demikian, satu hal yang perlu kita yakini dalam al inni adalah, pola umum yang tersemat sebenarnya membuat seluruh urutan tersebut menjadi tidak acak seluruhnya. Hal ini akan tergambarkan dalam statistik frekuensi posisi jika kita membuat profil dari segmen yang diambil dari masing-masing urutan, sekalipun jika segmen-segmen tersebut dicuplik secara acak. Atas dasar inilah, jika diberikan cukup perulangan maka terdapat kemungkinan bahwa pola umum antar urutan tersebut dapat ditemukan. So, pesan moral dari algoritma ini adalah never give up trying...hohoho.

Hmm…kalau untuk algoritma penujumannya saia rasa segini saja dulu deh. Pada tulisan berikutnya saia ingin memperkenalkan beberapa database yang menggunakan motif dalam pencariannya.

Salam,
KohVic

Jumat, 24 Juli 2015

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:


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