Minggu, 16 Desember 2012

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)

2 komentar:

Waktunya Belajar mengatakan...

Salam kenal.

Saya pernah belajar pemodelan probabilistik begini, tapi untuk kasus2 ekonomi/industri.

Dan saya diberitahu oleh dosen saya bahwa model2 seperti kebanyakan lebih berguna sebagai "brain teaser" alias cuma untuk asah otak saja, sulit diterapkan untuk masalah praktis.

Nah, pertanyaan saya, seberapa jauh model ini bisa menggambarkan pohon evolusi makhluk hidup? Bagaimana cara memvalidasi-nya (memastikan bahwa model yg dibuat merupakan model yg terdekat dalam merepresentasikan keadaan aslinya)?

eniwei nice article...

Da Owl mengatakan...

Thanks for the comment.

Well, semua pohon filogenetik itu pada akhirnya merupakan pohon hipotetikal yang hanya bersifat prediktif-konfirmatif. Hal ini karena pohon2 tsb direkonstruksi menggunakan data yang tidak lengkap dan asumsi-asumsi yang diterapkan.

Cara yang paling banyak diterapkan oleh orang untuk menguji kebenaran pohon filogenetik yang direkonstruksi menggunakan data molekular (DNA/protein) adalah dengan membandingkannya menggunakan data fosil. Dari sana dapat terlihat bagaimana konsistensi pohon filogenetik molekular dalam menggambarkan kekerabatan antar organisme serta waktu divergensi antar spesies satu dengan yang lain.

Namun demikian, toh ga semua organisme punya catatan fosil. Ambil kasus bakteri ato virus misalnya. Nah dalam hal ini, konfirmasi kebenaran suatu pohon dilakukan secara relatif dengan menguji asumsi2 yang diterapkan pada pohon tersebut terhadap suatu data simulasi. Apabila hasil rekonstruksi data simulasi sangat mirip atau sama dengan rekonstruksi kasus nyata, maka pada titik ini kita bisa mempercayai pohon tersebut.

Salam,
Victor