Hmm...sebenarnya ada sedikit kekhawatiran dalam diri saia ketika ingin menulis mengenai topik ini. Pertama adalah karena notes-notes yang berjudul Bayesian sudah pernah saia tulisan sebelumnya. Menuliskannya kembali kali ini sepertinya terkesan mengulang-ngulang saja. Kedua adalah, saia khawatir para pembaca setia dan tidak setia seri Bukan Tulisan Ilmiah saia akan segera bosan. Yasuda, saia putuskan untuk melakukan semacam impruvisasi dalam tulisan ini. Judulnya mungkin mirip, tapi saia akan fokus untuk memperdalam isi materinya. Selamat membaca ^^
A. Sebuah Awalan
Bayangkan sebuah pertandingan/kompetisi tahunan tingkat dunia dan selama 14 tahun terakhir ini dimenangkan oleh 7 negara yang sama. Nah sekarang pertanyaannya adalah pada pertandingan ke-15 yang katakanlah diselenggarakan sekarang ini, negara manakah yang akan menang? Seorang yang setia mengikuti pertandingan tersebut pastinya punya pegangan kuat tim mana yang diprediksi akan menang. Namun bagi kita-kita yang mungkin tidak tahu apa-apa mengenai pertandingan tersebut sebenarnya juga bisa menentukan pilihan tim yang cukup meyakinkan untuk menang. Oke, sekarang anggaplah peluang kemenangan hanya terdapat pada 7 negara tersebut dan peluang dimenangkan oleh negara lainnya dapat diabaikan. Dengan memperhatikan sejarah perolehan kemenangan selama 14 tahun terakhir yang sama pada ke-7 negara tersebut, kita dapat memperkirakan bahwa pada pertandingan ke-15 ini satu negara memiliki peluang untuk menang sebanyak 1/7.
Pertandingan tahun ke-15 pun dimulai dan kita pun (mencoba) menonton dengan antusias. Perkiraan pun semakin mendekati kenyataan dan tidak terasa 2 diantara 7 negara tersebut ternyata masuk final!! Nah pertanyaannya sekarang adalah apakah peluang menang kedua negara yang bertarung di final tersebut masih 1/7? Tentunya peluang tersebut sudah meningkat menjadi 1/2 bukan?
Yup, logika Bayesian memang dicirikan dengan kemampuannya untuk memperbarui distribusi kemungkinan sedemikian rupa sehingga mendekati kebenaran. Pada cerita di atas, peluang 1/7 pada tiap negara itu kita sebut sebagai "prior" atau dapat saia definisikan sebagai "perkiraan awal". Sementara itu, peluang 1/7 yang kemudian meningkat menjadi 1/2 setelah diperbarui dengan data-data terkini disebut sebagai "posterior" atau yang dapat saia definisikan sebgai "perkiraan kemudian". Bayesian phylogentic inference dirumuskan sesuai dengan teorema Bayes, yakni:
Pr[tree|data] = (Pr[data|tree] x Pr[tree]) / Pr[data]
dimana tanda garis vertikal "|" dibaca sebagai "given". Saia langsung merujuk pada bahasa inggrisnya saja agar tidak membingungkan. Dengan demikian pembahasaan rumus diatas adalah: "probability of the tree given the data (posterior) equals the probability of the data given the tree (likelihood) times the probability of the tree and then divided by the probability of the data outcome". Konsekuensi dari pernyataan tersebut adalah bahwa untuk mendapatkan pohon filogenetik yang mencerminkan kekerabatan antar taksa yang sebenarnya (the posterior tree), kita harus mengintegrasikan probabilitas dari seluruh situs untuk sebuah pohon dan kemudian menjumlahkannya untuk keseluruhan kemungkinan pohon yang ada. Hal kedua mungkin untuk dilakukan karena kita tinggal hanya menjumlahkannya saja. Namun demikian, integrasi probabilitas situs antar sequence (Pr[data]) itu yang membuat masalah ini menjadi rumit.
B. Perbandingan antara Maximum Likelihood dengan Bayesian Inference
Tentunya para teman-teman pembaca masih ingat dengan tulisan saia sebelumnya yang menyinggung tentang metode Maximum Likelihood (ML). Kalau belum ingat atau belum baca, ya monggo ditengok. Nah membicarakan metode ML itu akan membawa kita kepada persamaan berikut ini:
L = L(1) x L(2) x L(3) x ... x L(n)
atau
lnL = lnL(1) + lnL(2) + lnL(3) + ... + lnL(n)
Perlu kita ketahui bahwa nilai likelihood L per situs diestimasi untuk sejumlah internal nodes yang terdapat pada pohon yang menghubungkan seluruh taksa. Suatu pohon dengan n taksa mengandung n-2 internal nodes. Mengingat bahwa ada 4 kombinasi jenis nukleotida yang mungkin per situs dalam setiap internal nodes, maka terdapat 4^(n-2) kombinasi nukleotida per situs untuk pohon dengan n taksa. Err..kita baru membicarakan likelihood untuk satu situs bukan? dan tentunya nilai likelihood suatu pohon dihitung dari nilai likelihood setiap situsnya. Nah jumlah internal nodes tersebut, pendek kata, setara dengan kelipatan integral untuk menghitung probabilitasnya. Nah proses integrasi yang berlipat-lipat inilah yang menjadikan metode ML sangat memakan waktu dari segi komputasi bahkan dengan komputer cepat sekalipun.
Metode Bayesian inference, sekalipun menggunakan nilai likelihood L dalam teorema Bayes-nya, tidak secara eksplisit menghitung nilai tersebut. Hal ini dapat dicapai akibat penerapan algoritme Markov Chain Monte Carlo (MCMC) mengestimasi nilai likelihood dari suatu pohon dengan branch length dan model tertentu. Dengan demikian, proses dalam Bayesian inference menjadi lebih cepat di dalam pencarian pohon terbaik (best tree) akibat penerapan MCMC ini.
C. Tahapan Bayesian Inference
Inti dari Bayesian inference adalah analisis probabilitas. Jika likelihood didefinisikan sebagai probabilitas dari suatu data jika diberikan sebuah hipotesis (pohon), maka Bayesian inference ini menggunakan rasio likelihood tersebut untuk menentukan hipotesis (pohon) mana yang lebih mampu menjelaskan data sequence yang kita miliki. Proses MCMC akan menghasilkan serangkaian hipotesis dalam rantaian-nya (chain), masing-masing dengan nilai likelihoodnya. Nilai-nilai likelihood ini dimasukan ke dalam teorema Bayes seperti yang telah dituliskan di atas. Sebagai contoh, anggaplah kita telah memiliki dua nilai likelihood (L1 dan L2) untuk dua hipotesis dan ingin membandingkannya menggunakan teorema Bayes. Dalam perbandingan ini, state yang baru diperoleh (new state / L2) dibandingkan dengan state awalan (current state / L1) untuk diperoleh nilai rasio r nya:
Perhatikan bahwa masing-masing penyebut dari kedua persamaan (Pr[data]) saling menghilangkan satu sama lain sehingga nilai r setara dengan perbandingan kedua nilai likelihhod (L2/L1) dari kedua hipotesis. Jika nilai r lebih besar dari 1 yang berarti state baru memiliki nilai likelihood yang lebih tinggi daripada current state, maka state baru tersebut akan dijadikan sebagai current state yang baru. Apabila nilai r lebih kecil dari 1 maka state yang baru akan diterima dengan probabilitas tertentu. Apabila masih tidak mungkin untuk diterima, maka state baru tersebut ditolak dan current state tetap menjadi current state untuk dibandingkan lagi dengan state baru yang lain.
Algoritme MCMC akan terus menyampling pohon hingga mencapai keadaan dimana tidak diperoleh lagi perbedaan nilai likelihood yang signifikan antar satu pohon dengan lainnya. Nah pada keadaan ini dapat kita katakan bahwa MCMC telah mencapai titik konvergensi. Pada titik konvergensi inilah pohon dengan distribusi posterior didapatkan. Pada umumnya akan terdapat lebih dari satu pohon yang mewakili distribusi posterior ini dan pada akhirnya kita juga yang harus menentukan pohon mana dari sejumlah pohon posterior tersebut yang terbaik menurut kita.
D. Optimasi MCMC
Apabila penjelasan pada sub-bagian C membuat teman-teman pembaca agak bingung, saia akan mencoba menjelaskan dengan sedikit gambar (lihat gambarnya). Telah kita ketahui bahwa akan terdapat sejumlah besar pohon (dengan topologi dan branch length masing-masing) yang mungkin dibuat untuk sejumlah taksa. Masing-masing pohon tersebut memiliki probabilitasnya sendiri untuk menjadi pohon yang benar (likelihood). Nah jika saia mendistribusikan seluruh pohon tersebut dalam sebuah histogram katakanlah, dengan sumbu-Y menyatakan nilai likelihood, maka akan terlihat sebuah topologi distribusi probabilitas antar pohon satu dengan lainnya. Ada puncak yang rendah (likelihhod kurang optimal), ada lembah (nilai likelihood sangat rendah) dan ada juga puncak tertinggi (nilai likelihood optimal).
Pohon dengan "puncak" tertinggi dalam histogram tersebut (memiliki nilai likelihood tertinggi) merupakan pohon posterior dan merupakan target kita. Nah sekarang permasalahannya adalah rantai MCMC mungkin bisa terjebak pada puncak non-optimal (disebut sebagai local optima) seperti contohnya terjebak di puncak C. Apabila current state likelihood sudah berada di local optima, pembandingannya dengan new state likelihood mungkin akan selalu dimenangkan oleh current state likelihood karena sudah mencapai daerah puncak. Nah pada situasi seperti inilah parameter-parameter tertentu perlu diperhatikan agar terhindar dari local optima.
Parameter pertama adalah mixing behavior. Secara sederhana, mixing behavior dapat disetarakan sebagai variansi antara satu nilai likelihood dengan lainnya. Variansi yang terlalu kecil menggambarkan bahwa pencarian new state likelihood dilakukan dengan jarak yang begitu dekat dengan current state likelihood sehingga rasio r yang dihasilkan tidak berbeda secara signifikan. Dengan demikian dapat dikatakan bahwa rantai MCMC berjalan di tempat dan tidak berlanjut ke daerah posterior. Variansi yang terlalu besar pada umumnya menyebabkan new state likelihood sangat berbeda dengan current state likelihood sehingga nilai rasio keduanya lebih kecil dari 1. Sebagai akibatnya, chain akan terus berada pada titik current state likelihood aibat new state likelihood yang selalu ditolak. Dengan demikian, rantai MCMC diam ditempat. Kedua fenomena ini menyebabkan mixing behavior yang buruk. Variansi sedang (adequate) merupakan pertanda yang bagus dalam menandakan bahwa rantai MCMC kita berjalan menuju ke arah posterior.
Parameter kedua adalah Metropolis Coupling MCMC (atau MCMCMC / MC3). Parameter ini berfungsi untuk menghindarkan rantai MCMC kita terjebak pada local optima. Ketidakhadiran MC3 akan cenderung membuat rantai MCMC kita terhenti ketika sudah mencapai suatu puncak tanpa memperdulikan apakah itu hanya sekedar puncak (local optima) atau puncak tertinggi (global optima). Metropolis Coupling MCMC memungkinkan rantai MCMC kita untuk "melompat" dari satu puncak ke daerah lainnya, sehingga membuat rantai MCMC bisa terus mencari daerah posterior yang menjadi global optima.
E. Kesimpulan
Jadi, setelah menuliskan secara panjang x lebar x dalam dibagi jari-jari kuadrat dan diintegralkan, maka dengan ini saia simpulkan bahwa pada intinya Bayesian Phylogenetic Inference mencari pohon terbaiknya (the best tree) berdasarkan distribusi probabilitas posterior diantara pohon-pohon yang ada. Pohon-pohon yang memiliki probabilitas posterior tertinggi diantara pohon lainnya dianggap merupakan serangkaian pohon yang dapat menggambarkan hubungan filogenetik taksa kajian dengan sama baiknya. Pada akhirnya, semua kembali kepada kita mengenai bagaimana menginterpretasikan distribusi probabiilitas posterior tersebut untuk menggambarkan hubungan kekerabatan antar taksa.
Regards,
KohVic
A. Sebuah Awalan
Bayangkan sebuah pertandingan/kompetisi tahunan tingkat dunia dan selama 14 tahun terakhir ini dimenangkan oleh 7 negara yang sama. Nah sekarang pertanyaannya adalah pada pertandingan ke-15 yang katakanlah diselenggarakan sekarang ini, negara manakah yang akan menang? Seorang yang setia mengikuti pertandingan tersebut pastinya punya pegangan kuat tim mana yang diprediksi akan menang. Namun bagi kita-kita yang mungkin tidak tahu apa-apa mengenai pertandingan tersebut sebenarnya juga bisa menentukan pilihan tim yang cukup meyakinkan untuk menang. Oke, sekarang anggaplah peluang kemenangan hanya terdapat pada 7 negara tersebut dan peluang dimenangkan oleh negara lainnya dapat diabaikan. Dengan memperhatikan sejarah perolehan kemenangan selama 14 tahun terakhir yang sama pada ke-7 negara tersebut, kita dapat memperkirakan bahwa pada pertandingan ke-15 ini satu negara memiliki peluang untuk menang sebanyak 1/7.
Pertandingan tahun ke-15 pun dimulai dan kita pun (mencoba) menonton dengan antusias. Perkiraan pun semakin mendekati kenyataan dan tidak terasa 2 diantara 7 negara tersebut ternyata masuk final!! Nah pertanyaannya sekarang adalah apakah peluang menang kedua negara yang bertarung di final tersebut masih 1/7? Tentunya peluang tersebut sudah meningkat menjadi 1/2 bukan?
Yup, logika Bayesian memang dicirikan dengan kemampuannya untuk memperbarui distribusi kemungkinan sedemikian rupa sehingga mendekati kebenaran. Pada cerita di atas, peluang 1/7 pada tiap negara itu kita sebut sebagai "prior" atau dapat saia definisikan sebagai "perkiraan awal". Sementara itu, peluang 1/7 yang kemudian meningkat menjadi 1/2 setelah diperbarui dengan data-data terkini disebut sebagai "posterior" atau yang dapat saia definisikan sebgai "perkiraan kemudian". Bayesian phylogentic inference dirumuskan sesuai dengan teorema Bayes, yakni:
Pr[tree|data] = (Pr[data|tree] x Pr[tree]) / Pr[data]
dimana tanda garis vertikal "|" dibaca sebagai "given". Saia langsung merujuk pada bahasa inggrisnya saja agar tidak membingungkan. Dengan demikian pembahasaan rumus diatas adalah: "probability of the tree given the data (posterior) equals the probability of the data given the tree (likelihood) times the probability of the tree and then divided by the probability of the data outcome". Konsekuensi dari pernyataan tersebut adalah bahwa untuk mendapatkan pohon filogenetik yang mencerminkan kekerabatan antar taksa yang sebenarnya (the posterior tree), kita harus mengintegrasikan probabilitas dari seluruh situs untuk sebuah pohon dan kemudian menjumlahkannya untuk keseluruhan kemungkinan pohon yang ada. Hal kedua mungkin untuk dilakukan karena kita tinggal hanya menjumlahkannya saja. Namun demikian, integrasi probabilitas situs antar sequence (Pr[data]) itu yang membuat masalah ini menjadi rumit.
B. Perbandingan antara Maximum Likelihood dengan Bayesian Inference
Tentunya para teman-teman pembaca masih ingat dengan tulisan saia sebelumnya yang menyinggung tentang metode Maximum Likelihood (ML). Kalau belum ingat atau belum baca, ya monggo ditengok. Nah membicarakan metode ML itu akan membawa kita kepada persamaan berikut ini:
L = L(1) x L(2) x L(3) x ... x L(n)
atau
lnL = lnL(1) + lnL(2) + lnL(3) + ... + lnL(n)
Perlu kita ketahui bahwa nilai likelihood L per situs diestimasi untuk sejumlah internal nodes yang terdapat pada pohon yang menghubungkan seluruh taksa. Suatu pohon dengan n taksa mengandung n-2 internal nodes. Mengingat bahwa ada 4 kombinasi jenis nukleotida yang mungkin per situs dalam setiap internal nodes, maka terdapat 4^(n-2) kombinasi nukleotida per situs untuk pohon dengan n taksa. Err..kita baru membicarakan likelihood untuk satu situs bukan? dan tentunya nilai likelihood suatu pohon dihitung dari nilai likelihood setiap situsnya. Nah jumlah internal nodes tersebut, pendek kata, setara dengan kelipatan integral untuk menghitung probabilitasnya. Nah proses integrasi yang berlipat-lipat inilah yang menjadikan metode ML sangat memakan waktu dari segi komputasi bahkan dengan komputer cepat sekalipun.
Metode Bayesian inference, sekalipun menggunakan nilai likelihood L dalam teorema Bayes-nya, tidak secara eksplisit menghitung nilai tersebut. Hal ini dapat dicapai akibat penerapan algoritme Markov Chain Monte Carlo (MCMC) mengestimasi nilai likelihood dari suatu pohon dengan branch length dan model tertentu. Dengan demikian, proses dalam Bayesian inference menjadi lebih cepat di dalam pencarian pohon terbaik (best tree) akibat penerapan MCMC ini.
C. Tahapan Bayesian Inference
Inti dari Bayesian inference adalah analisis probabilitas. Jika likelihood didefinisikan sebagai probabilitas dari suatu data jika diberikan sebuah hipotesis (pohon), maka Bayesian inference ini menggunakan rasio likelihood tersebut untuk menentukan hipotesis (pohon) mana yang lebih mampu menjelaskan data sequence yang kita miliki. Proses MCMC akan menghasilkan serangkaian hipotesis dalam rantaian-nya (chain), masing-masing dengan nilai likelihoodnya. Nilai-nilai likelihood ini dimasukan ke dalam teorema Bayes seperti yang telah dituliskan di atas. Sebagai contoh, anggaplah kita telah memiliki dua nilai likelihood (L1 dan L2) untuk dua hipotesis dan ingin membandingkannya menggunakan teorema Bayes. Dalam perbandingan ini, state yang baru diperoleh (new state / L2) dibandingkan dengan state awalan (current state / L1) untuk diperoleh nilai rasio r nya:
Perhatikan bahwa masing-masing penyebut dari kedua persamaan (Pr[data]) saling menghilangkan satu sama lain sehingga nilai r setara dengan perbandingan kedua nilai likelihhod (L2/L1) dari kedua hipotesis. Jika nilai r lebih besar dari 1 yang berarti state baru memiliki nilai likelihood yang lebih tinggi daripada current state, maka state baru tersebut akan dijadikan sebagai current state yang baru. Apabila nilai r lebih kecil dari 1 maka state yang baru akan diterima dengan probabilitas tertentu. Apabila masih tidak mungkin untuk diterima, maka state baru tersebut ditolak dan current state tetap menjadi current state untuk dibandingkan lagi dengan state baru yang lain.
Algoritme MCMC akan terus menyampling pohon hingga mencapai keadaan dimana tidak diperoleh lagi perbedaan nilai likelihood yang signifikan antar satu pohon dengan lainnya. Nah pada keadaan ini dapat kita katakan bahwa MCMC telah mencapai titik konvergensi. Pada titik konvergensi inilah pohon dengan distribusi posterior didapatkan. Pada umumnya akan terdapat lebih dari satu pohon yang mewakili distribusi posterior ini dan pada akhirnya kita juga yang harus menentukan pohon mana dari sejumlah pohon posterior tersebut yang terbaik menurut kita.
D. Optimasi MCMC
Apabila penjelasan pada sub-bagian C membuat teman-teman pembaca agak bingung, saia akan mencoba menjelaskan dengan sedikit gambar (lihat gambarnya). Telah kita ketahui bahwa akan terdapat sejumlah besar pohon (dengan topologi dan branch length masing-masing) yang mungkin dibuat untuk sejumlah taksa. Masing-masing pohon tersebut memiliki probabilitasnya sendiri untuk menjadi pohon yang benar (likelihood). Nah jika saia mendistribusikan seluruh pohon tersebut dalam sebuah histogram katakanlah, dengan sumbu-Y menyatakan nilai likelihood, maka akan terlihat sebuah topologi distribusi probabilitas antar pohon satu dengan lainnya. Ada puncak yang rendah (likelihhod kurang optimal), ada lembah (nilai likelihood sangat rendah) dan ada juga puncak tertinggi (nilai likelihood optimal).
Parameter pertama adalah mixing behavior. Secara sederhana, mixing behavior dapat disetarakan sebagai variansi antara satu nilai likelihood dengan lainnya. Variansi yang terlalu kecil menggambarkan bahwa pencarian new state likelihood dilakukan dengan jarak yang begitu dekat dengan current state likelihood sehingga rasio r yang dihasilkan tidak berbeda secara signifikan. Dengan demikian dapat dikatakan bahwa rantai MCMC berjalan di tempat dan tidak berlanjut ke daerah posterior. Variansi yang terlalu besar pada umumnya menyebabkan new state likelihood sangat berbeda dengan current state likelihood sehingga nilai rasio keduanya lebih kecil dari 1. Sebagai akibatnya, chain akan terus berada pada titik current state likelihood aibat new state likelihood yang selalu ditolak. Dengan demikian, rantai MCMC diam ditempat. Kedua fenomena ini menyebabkan mixing behavior yang buruk. Variansi sedang (adequate) merupakan pertanda yang bagus dalam menandakan bahwa rantai MCMC kita berjalan menuju ke arah posterior.
Parameter kedua adalah Metropolis Coupling MCMC (atau MCMCMC / MC3). Parameter ini berfungsi untuk menghindarkan rantai MCMC kita terjebak pada local optima. Ketidakhadiran MC3 akan cenderung membuat rantai MCMC kita terhenti ketika sudah mencapai suatu puncak tanpa memperdulikan apakah itu hanya sekedar puncak (local optima) atau puncak tertinggi (global optima). Metropolis Coupling MCMC memungkinkan rantai MCMC kita untuk "melompat" dari satu puncak ke daerah lainnya, sehingga membuat rantai MCMC bisa terus mencari daerah posterior yang menjadi global optima.
E. Kesimpulan
Jadi, setelah menuliskan secara panjang x lebar x dalam dibagi jari-jari kuadrat dan diintegralkan, maka dengan ini saia simpulkan bahwa pada intinya Bayesian Phylogenetic Inference mencari pohon terbaiknya (the best tree) berdasarkan distribusi probabilitas posterior diantara pohon-pohon yang ada. Pohon-pohon yang memiliki probabilitas posterior tertinggi diantara pohon lainnya dianggap merupakan serangkaian pohon yang dapat menggambarkan hubungan filogenetik taksa kajian dengan sama baiknya. Pada akhirnya, semua kembali kepada kita mengenai bagaimana menginterpretasikan distribusi probabiilitas posterior tersebut untuk menggambarkan hubungan kekerabatan antar taksa.
Regards,
KohVic
Further Readings:
- Ronquist, F., P. van der Mark, & J. P. Huelsenbeck. 2009. Bayesian phylogenetic analysis using MRBAYES. In The Phylogenetic Handbook: A Practical Approach to Phylogenetic Analysis and Hypothesis Testing 2nd Edition (P. Lemey, M. Salemi, & A-M. Vandamme eds.). Cambridge University Press: UK.
- Huelsenbeck, J. P., F. Ronquist, R. Nielsen, & J. P. Bollback. 2001. Bayesian Inference of Phylogeny and Its Impact on Evolutionary Biology. Science 294: 2310-2314.
- Yang, Z. & B. Rannala. 1997. Bayesian Phylogenetic Inference Using DNA Sequences: A Markov Chain Monte Carlo Method. Mol. Biol. Evol. 14 (7): 717-724.
- Rannala, B. & Z. Yang. 1996. Probability Distribution of Molecular Evolutionary Trees: A New Method of Phylogenetic Inference. J. Mol. Evol. 43: 304-311.
Tidak ada komentar:
Posting Komentar