Sebuah Tulisan Evolusi dan Filogeni: Phylogenetic Inference by Maximum Parsimony Method (In Depth)

Sekedar menyelesaikan sharing-sharing ria bersama mengenai proses inferensi filogenetik, kali ini saia mencoba membawakan satu lagi konsep yang melatarbelakangi algoritme Maximum Parsimony (MP). Yah sekian saja deh kata sambutan dari saia dan selamat membaca ^^/

A. Pengantar
Konsep parsimony dapat dikatakan merupakan konsep pertama yang mengawali analisis kekerabatan antar organisme. Konsep ini dikemukakan oleh Willi Henning, seorang entomolog Jerman, yang berpendapat bahwa hubungan kekerabatan antar organisme hanya dapat ditarik dari kemiripan/similaritas yang diturunkan dari nenek moyangnya. Hal ini tentu saja berbeda dengan pandangan fenetik pada saat itu yang menganggap kemiripan secara keseluruhan (overall similarity) harus dikaitkan semuanya dalam mengevaluasi suatu kekerabatan diantara organisme. Kemiripan karakter yang diturunkan dari nenek moyang tersebut diistilahkan sebagai "symplesiomorphy", sementara kemiripan yang didapatkan dari proses adaptasi diistilahkan sebagai "synapomorphy". Kedua kata tersebut secara berturut-turut diturunkan dari kata "plesiomorph" yang berarti karakter nenek moyang (ancient) dan "apomorph" yang berarti karakter yang didapatkan (derived).

Konsep parsimony berlaku hingga kini dan juga telah diterapkan untuk sequence molekular. Intinya adalah mencari pohon filogenetik yang memerlukan asumsi paling sedikit dalam menghubungakan semua organisme/taksa yang dikaji. Asumsi yang dimaksud dalam hal ini adalah proses substitusi nukleotida. Konsep yang sama juga berlaku ketika menggunakan sequence asam amino. Substitusi yang semakin sedikit juga berarti meminimalisir panjang branch length, sehingga pohon Maximum Parsimony (MP) adalah pohon yang dapat menghasilkan tree length (total branch length) minimum.

B. Situs Informatif (Parsimony Informative Sites)
Dalam algoritme Maximum Parsimony tidak semua situs dalam sequence menyediakan informasi mengenai jejak-jejak plesiomorph molekular. Gambar 1 dapat membantu menjelaskan perbedaan antara situs informatif, variabel, singleton (situs dimana hanya ada 1 taksa yang berbeda), dan invariabel. Situs variabel merupakan situs yang mengandung keempat jenis nukleotida (A, T, G, dan C). Situs ini tidak informatif karena tidak ada pohon parsimonius yang lebih mampu menjelaskan substitusi mana yang lebih sedikit dibandingkan yang lain. Situs singleton dan juga situs invariabel juga sama-sama tidak dapat memberikan informasi mengenai pohon mana yang bersifat parsimonius.

Gambar 1. Perbandingan antara situs informatif, variabel, singleton, dan invariabel.

Dengan demikian, syarat sebuh situs agar bersifat informatif adalah situs tersebut harus memungkinkan adanya perbedaan perhitungan jumlah substitusi antar topologi untuk menjelaskan variasi yang terdapat pada situs tersebut. Hal ini berarti bahwa sebuah situs informatif setidaknya harus memiliki dua jenis nukleotida dan keduanya harus muncul setidaknya dua kali pada situs tersebut. Gambar 1 memperlihatkan bahwa sebuah situs untuk 4 taksa yang mengandung A, A, G, G merupakan situs informatif. Hal ini dapat terlihat dari 3 jenis kandidat pohon yang dibuat bahwa pohon 1 merupakan pohon yang paling parsimonius (mengandung substitusi paling sedikit).

C. Tahap Rekonstruksi Pohon MP
Kita akan mencoba merekonstruksi pohon MP untuk 4 taksa terlebih dahulu. Jika diberikan 4 taksa dengan sequence alignment n, maka algoritme MP hanya akan menggunakan situs-situs informatif dari n-situs tersebut untuk rekonstruksi pohonnya. Nah tahapannya dapat saia simpulkan seperti ini:

1. Tentukan kemungkinan pohon yang dapat direkonstruksi dari sejumlah taksa yang diuji. Dalam contoh kali ini ada 4 taksa, sehingga terdapat 3 kandidat pohon.
2. Tentukan kombinasi nukleotida untuk penentuan character state pada nodus internal. Jumlah nodus internal untuk pohon dengan n-taksa adalah n-2. Dalam contoh kasus 4 taksa kita, maka ada 2 nodus internal. Nah karena ada 4 jenis nukleotida yang mungkin menempati nodus internal tersebut, maka kombinasi total kemungkinan nukleotida dirumuskan dengan 4^i dengan i sebagai jumlah nodus internal. Dengan demikian akan ada 16 kombinasi nukleotida pada nodus internal untuk kasus 4 taksa kita (Gambar 2). Kemudian dari 16 kombinasi tersebut, tentukan kombinasi nukleotida nodus internal dengan jumlah substitusi paling sedikit (Gambar 2, kotak).

Gambar 2. Kombinasi jenis nukleotida untuk dua nodus internal pada kasus filogeni 4 taksa.

3. Dengan menggunakan SETIAP situs informatif yang tersedia, tentukan pohon yang memberikan jumlah total substitusi paling sedikit.

Nah pohon dari seluruh kandidat pohon yang memberikan jumlah substitusi paling sedikit merupakan pohon terbaik menurut algoritme MP atau dapat disebut juga sebagai pohon MP. Dari tulisan sebelumnya kita mengetahui bahwa jumlah substitusi mencerminkan branch length, maka pohon MP merupakan pohon filogenetik yang meminimalisir branch length. Hal ini sesuai dengan filosofi Ockham Razor, "shave away all that is unnecessary". Petuah ini bermakna bahwa evolusi merupakan proses yang efisien, sehingga apabila terdapat lebih dari satu jalur untuk mengarah pada satu hasil maka jalu terpendek-lah yang akan dipilih.

Seiring dengan semakin banyaknya taksa yang ingin diselidiki hubungan kekerabatannya, jumlah kandidat pohon tentu saja meroket dengan cepat. Untuk itu, algoritme MP menggunakan beberapa metode pencarian pohon yang telah dijelaskan sebelumnya, yakni mulai dari Branch & Bound untuk 25 taksa dan Heuristic Approach untuk taksa lebih dari 25 (lihat pada artikel Sebuah Tulisan Evolusi dan Filogeni: Phylogenetic Inference by Maximum Likelihood Method (In Depth)).

D. Keuntungan dan Kerugian Algoritme Maximum Parsimony
Sebagai sebuah algoritme, tentu saja Maximum Parsimony memiliki aspek positif dan negatif.  Berikut saia berikan daftarnya:
- Keuntungan
1. Pohon MP yang direkonstruksi pada umumnya terbebas dari asumsi-asumsi model substitusi nukelotida yang diterapkan pada algoritme lainnya seperti algoritme distance-matrix atau maximum likelihood. Dengan kebebasan asumsi model substitusi ini, pohon MP dinilai lebih dapat menggambarkan hubungan kekerabatan yang sebenarnya ketika divergensi antar sequence cukup rendah.
2. Maximum Parsimony merupakan algoritme character-based yang cukup akurat dengan waktu komputasi yang relatif lebih cepat dari algoritme character-based lainnya seperti maximum likelihood.

- Kerugian
1. Pohon MP dikatakan cukup akurat atau mendekati pohon sebenarnya (true tree) apabila diterapkan dengan serangkaian syarat, yakni: (i) tidak ada back mutation atau parallelism; (ii) laju substitusi antar taksa relatif rendah; dan (iii) jumlah nukleotida dalam sequence sangat banyak. Pada kenyataanya ketiga syarat tersebut sulit untuk terpenuhi oleh dataset yang ada.
2. Adanya tendensi algoritme MP untuk menggabungkan 2 taksa yang memiliki kemiripan sequence nukleotida akibat proses back mutation, parallelism, dan konvergensi. Hal ini dapat terjadi juga akibat ketidaksetaraan laju evolusi antar taksa. Kedua faktor tersebut dapat berakibat pada efek "long branch attraction", yakni penggabungan dua taksa yang berbeda nenek moyang akibat kesamaan laju substitusi nukleotida (Gambar 3). Berdasarkan Gambar 3 tersebut, takson A dan C yang berbeda nenek moyang dalam hal ini bergabung pada nodus internal (nenek moyang) yang sama oleh algoritme MP. Hal ini disebabkan oleh karena perbedaan laju substitusi nukleotida antara takson A yang lebih mirip dengan takson C dibandingkan dengan takson B yang merupakan kerabat takson A yang sebenarnya.

Gambar 3. Long-Branch Attraction.

E. Kesimpulan
Algoritme MP dapat dikatakan sebagai algoritme tertua yang dikembangkan untuk mempelajari hubungan kekerabatan antar mahluk hidup. Seperti hal-nya algoritme lainnya, penerapan konsep parsimony dalam algoritme sequence molekular (DNA/protein) tentunya memiliki serangkaian asumsi sehingga mengakibatkan adanya keuntungan dan kerugian tersendiri dari algoritme ini. Sebagai algoritme character-based, Maximum Parsimony cukup cepat dan akurat dalam merekonstruksi hubungan kekerabatan antar taksa jika menggunakan sequence yang memiliki kekonstanan laju evolusi dan sedikit homoplasi.

Regards,
KohVic

Sebuah Tulisan Evolusi dan Filogeni: Bayesian Phylogenetic Inference (In Depth)

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

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.

Sebuah Tulisan Evolusi dan Filogeni: Phylogenetic Inference by Maximum Likelihood Method (In Depth)

Hai hai hai...kembali berjumpa dengan saia Chef Victor alias KohVic. Yaa lagi-lagi saia diprotes oleh salah satu pembaca karena lama tidak membuat tulisan terkait filogenetik. Jujur saja saia sampai saat ini belum ada ide untuk membuat tulisan dengan tema baru. Yaa silahkan pikir sendiri alasannya mengapa, bisa mulai dari sibuk mengerjakan tesis hingga sibuk cari teman kencan...hahahaha. Ehem..yaa dalam tulisan kali ini saia hanya ingin mencoba membahas secara lebih mendalam sebuah tulisan yang pernah saia buat pada serial Sebuah Tulisan Evolusi dan Filogeni yang lalu, yakni mengenai algoritme Maximum Likelihood (ML).

Pertama, ijinkan saia memaparkan alur pikiran saia dalam tulisan ini. Tulisan ini akan saia mulai dengan definisi konsep likelihood, kemudian dilanjutkan ke penerapan konsep likelihood tersebut dalam konteks filogenetik. Sederhana toh? Oke mari kita mulai dengan sebuah pertanyaan. Apakah itu tepatnya definisi kata "likelihood"? Well, secara intuitif ditambah sedikit pengalaman membuka kamus bahasa inggris tentunya kita akan menebak bahwa kata tersebut berhubungan dengan sesuatu yang cenderung (likely). Nah dalam konteks matematis, kecenderungan itu bisa dikatakan sepadan dengan peluang. Yap, konteks likelihood ini sangat berhubungan sekali dengan peluang. Nah peluang seperti apakah itu.

Mari saia jabarkan dengan satu contoh. Jika kita melempar koin sebanyak 100 kali dan mendapatkan bagian depan sebanyak 21 (d=21), kita dapat menuliskan bahwa peluang munculnya bagian depan adalah p=0,21. Sekarang saia tanya, berapakah peluang saia untuk mendapatkan hasil persis sama (d=21) dalam 100 lemparan koin berikutnya? Dalam hal ini kita dapat menghitungnya dengan persamaan distribusi binomial, yakni:

Prob[H=d] = (n, d) p^d . (1-p)^n-d

dimana: p^d merupakan peluang untuk mendapatkan bagian depan (d) dikalikan dengan peluang untuk tidak mendapatkan d. Karena koin hanya memiliki 2 sisi, maka peluang tidak mendapatkan d adalan 1-p. Nah dari persamaan di atas, kita dapat melihatnya dari dua sisi. Pertama, jika p diketahui maka kita dapat menghitung peluang untuk mendapatkan distribusi hasil yang sama (21 depan, 79 belakang) untuk 100 lemparan ke depan. Kedua adalah, kita telah mendapatkan distribusi hasil depan dan belakang dan nilai p inilah yang justru dicari. Konteks kedua inilah yang dinamakan sebagai likelihood, yakni menghitung probabilitas dari suatu kejadian yang sudah terjadi (probability of the known event) atau sering disebut sebagai reverse probability.

Nah dalam konteks filogenetik, penerapan konsep likelihood ini dijabarkan dengan hipotesis (topologi pohon, branch length, dan model evolusi) seperti apa yang memiliki likelihood terbesar untuk menghasilkan sequence alignment yang kita miliki. Metode ML termasuk ke dalam salah satu metode character-based dengan fungsi optimality search criterion. Artinya adalah metode ini didasarkan pada suatu model evolusi tertentu (JC69, K80, TN93, GTR, dsb) untuk menganalisis likelihood setiap topologi pohon dari setiap situs nukleotida yang ada pada sequence alignment yang kita miliki. Jadi, dalam metode ML kita perlu memasukan model evolusi dan nantinya algoritme ML terebut yang menentukan pohon seperti apakah yang paling dapat 'menjelaskan' sequence alignment yang kita miliki berdasarkan model evolusi tersebut. Hal ini berarti bahwa perbedaan model evolusi yang digunakan dapat mengakibatkan perbedaan pohon yang didapatkan. Suatu pohon ML yang dihasilkan dapat dibandingkan satu sama lain berdasarkan nilai Maximum Likelihood Estimate (MLE) nya. Nilai MLE yang lebih besar menandakan bahwa pohon tersebut dapat menjelaskan sequence alignment kita dengan lebih baik.

Nah sekarang, bagaimana tepatnya tahapan dalam pembuatan pohon ML? Saia akan mencoba menjelaskannya dengan menggunakan 4 taxa/OTU. Berikut adalah sequence alignment untuk ke-4 OTU tersebut:

OTU 1    = AACGCCTTT...N
OTU 2    = AACGCGTTA...N
OTU 3    = AACCAGTTT...N
OTU 4    = AACCGGTTT...N
Sekarang coba lihat situs kelima. Disana secara berturut-turut OTU 1, 2, 3, dan 4 memiliki nukleotida C, C, A, dan G. Nah dengan contoh situs ke-5 ini metode ML merekonstruksi kekerabatan keempat OTU dengan membuat sebuah pohon unrooted dan kemudian memperhitungkan probabilitas nukleotida ancestor (5 & 6) yang menghasilkan state nukleotida seperti yang teramati sekarang ini.
(1)C--+            +--A(3)
           (5)----(6)
(2)C--+           +--G(4)

Kita ketahui bahwa ada 4 jenis nukleotida, yakni A, T, G, dan C. Dengan demikian, jumlah kombinasi nukleotida untuk dua ancestral state tersebut ada 16 (AA, AG, AC, AT...):
(1)C--+            +--A(3)  |  (1)C--+            +--A(3)  | (1)C--+            +--A(3)  |  (1)C--+            +--A(3)
           (A)----(A)            |            (A)----(T)              |           (A)----(C)             |            (A)----(G)
(2)C--+           +--G(4)   |  (2)C--+           +--G(4)   | (2)C--+           +--G(4)   |  (2)C--+         +--G(4) ....

Nah probabilitas dari seluruh kombinasi ini dihitung dengan bantuan data sequence alignment yang ada dan kemudian diakumulasi menjadi nilai likelihood untuk situs nomor 5 (L(5)). Selesai? Tentu saja belum. Metode ML akan menghitung nilai likelihood untuk satu pohon berdasarkan seluruh situs dalam alignment. Dengan demikian nilai likelihood (L) dari satu pohon dirumuskan dengan:

L = L(1) x L(2) x L(3) x ... x L(n)     dengan 1-n = jumlah situs dalam sequence alignment

Pada umumnya nilai L ini begitu kecilnya sehingga dinyatakan dalam bentuk logaritmik (lnL). Dengan demikian, rumusnya menjadi:

lnL = lnL(1) + lnL(2) + lnL(3) +...+ lnL(n)   dengan 1-n = jumlah situs dalam sequence alignment

Oke, sekarang kita telah mendapatkan nilai likelihood L untuk SATU pohon. Selesai? hahaha...tentu saja BELUM. Perlu kita ingat bahwa jumlah kandidat pohon untuk sejumlah OTU itu dirumuskan dengan:

N(U) = (2n-5)! / 2^n-3 . (n-3)! dengan n = jumlah OTU/taxa

Bingung? yaa gambaran mudahnya begini saja. Pada tingkat 4 OTU ada 3 kandidat pohon yang mungkin dibuat [(AB;CD), (AC;BD), & (AD);(BC)]. Nah meningkat ke 10 OTU akan ada 2.027.025 dan pada 20 OTU akan ada 221.643.095.476.699.771.875 kandidat pohon! Cukup banyak bukan? Nah misalnya kita menggunakan metode ML untuk merekonstruksi kekerabatan 20 OTU, itu artinya perhitungan nilai MLE harus dilakukan terhadap total sekitar 2x10^20 pohon tersebut. Komputer cepat pada saat ini pun akaan kewalahan jika disuruh hal seperti itu.

Nah lalu bagaimana solusinya? Saat ini ada dikembangkan 3 metode untuk evaluasi cepat dalam mencari pohon ML tersebut. Metode tersebut adalah (1) Exhaustive Search, (2) Branch & Bound Method, dan (3) Heuristic Approach. Metode Exhaustive Search telah saia jelaskan sebelumnya, yakni membuat seluruh kemungkinan topologi pohon dan mengevaluasi serta membandingkan nilai MLE antar satu pohon dengan yang lain. Metode ini menjamin bahwa pohon ML optimum akan didapatkan, namun demikian butuh waktu yang lama dan metode ini hanya efektif untuk rekonstruksi maksimal 10 OTU.

Ketika rekonstruksi melibatkan 12-25 OTU, maka metode Branch & Bound diterapkan menggantikan Exhaustive Search. Metode ini pada dasarnya mengevaluasi seluruh kemungkinan pohon namun juga memotong jalur rekonstruksi pohon ketika dipastikan bahwa pohon tersebut pastinya memiliki nilai MLE yang lebih rendah. Pemotongan jalur rekonstruksi ini dapat menghemat sebagian waktu komputasi, sehingga memungkinkan metode Branch & Bound cukup efektif hingga 25 OTU. Tahapannya adalah dengan merekonstruksi 1 pohon awal (initial tree) dari 3 OTU hingga n-OTU. Setiap penambahan OTU ke dalam pohon (growing tree) akan diestimasi nilai MLE nya dan terus demikian hingga mencapai 1 pohon lengkap (full tree). Selanjutnya, metode tersebut akan mengulang rekonstruksi dari tahapan 3 OTU. Namun kali ini nilai MLE pada penambahan OTU ke-4 akan dibandingkan dengan nilai MLE pada initial tree. Apabila nilai MLE nya lebih rendah, maka jalur rekonstruksi tersebut tidak akan dilanjutkan dan demikian sebaliknya.

Nah sekarang, bagaimana jika kita ingin merekonstruksi filogeni dengan OTU > 25? Dikatakan bahwa metode Branch & Bound kurang efektif jika diterapkan pada lebih dari 25 OTU. Pada kasus ini pencarian optimal ML tree akan diserahkan pada algoritme berbasis Heuristic Approach. Inti dari algoritme ini adalah berbasis sampling, yakni hanya menggunakan sebagian kandidat pohon dari total pohon yang mungkin direkonstruksi. Berbagai macam algoritme berbasis Heuristic Approach telah dikembangkan, diantaranya meliputi Stepwise Addition, Star Decomposition, dan Branch Perturbations. Saat ini algoritme yang paling umum digunakan adalah berbasis Branch Perturbations, yang selanjutnya terbagi lagi menjadi 3, yakni (1) Nearest Neighborhood Interchange (NNI), (2) Subtree Prunning and Regrafting (SPR), dan (3) Tree Bisection and Reconnection (TBR). Em, saia rasa terlalu panjang untuk membahasnya satu per satu, tapi saia akan kemukakan logika umumnya. Intinya adalah metode Branch Perturbation ini akan merekonstruksi sebuah pohon dan mengestimasi nilai MLE-nya untuk dijadikan sebagai patokan awal. Selanjutnya topologi pohon akan dirubah sedemikian rupa dan kemudian nilai MLE diestimasi kembali. Nilai MLE yang lebih tinggi menandakan bahwa topologi pohon tersebut lebih mampu menjelaskan data dan akan disimpan sebagai patokan yang baru. Branch Perturbation ini akan terus dilakukan hingga tidak didapatkan pohon dengan nilai MLE yang lebih tinggi lagi. Nah perbedaan antara NNI, SPR, dan TBR terletak pada jumlah kombinasi Branch Pertubation yang dapat dibuat. Sebagai hitungan kasar, apabila dengan NNI dapat menghasilkan n kombinasi sampel, maka SPR akan menghasilkan kuadrat-n, dan terakhir TBR akan menghasilkan kubik-n kombinasi sampel. Hmm...TBR kedengarannya cukup meyakinkan bukan. Namun jangan lupa bahwa semakin banyak kombinasi yang dibuat itu berarti waktu komputasi yang semakin lama loh...hehehe

Oke deh, sekian dulu mengenai Maximum Likelihood nya. Semoga dengan tulisan iseng-iseng saia ini kita jadi lebih bisa mengerti dan memahami mengenai algoritme Maximum Likelihood yang terkenal.....lama akan waktu komputasinya itu.

Regrads,
Victor Apriel (KohVic)