Sebuah Tulisan Evolusi dan Filogeni: Sequence Alignment (In Depth) Part 2

Oke, this is part 2 haa. Setelah kita tahu mengenai bagaimana logika dan proses alignment pasangan sequence seperti yang telah dijelaskan dalam Part 1, sekarang kita akan menuju ke Part 2. Tulisan dalam Part 2 ini akan berisi tentang alignment lebih dari dua sequence yang berbasis pada dynamic programming seperti metode Needleman-Wunsch. Oke, langsung saja ke inti ceritanya yak.

Metode dynamic programming dapat dimodifikasi sedikit agar dapat mengakomodasi lebih dari dua buah sequence. Inti cerita dari multiple sequence alignment sebenarnya cukup sederhana, yakni menemukan sebuah alignment yang dapat memberikan nilai maksimal untuk setiap kombinasi pasangan sequencenya serta juga meminimalisir jumlah maupun panjang gap yang ada. Secara matematis, alignment tersebut harus memberikan nilai terbaik untuk rumus WSP (weighted sum of pairs) objective function [1], dimana Dij merupakan skor terbaik untuk seluruh kombinasi pasangan sequence i dan j. Variabel Wij (extra term weight) digunakan untuk memberikan bobot tambahan kepada pasangan atau kelompok sequence tertentu berdasarkan informasi tambahan lainnya seperti kejelasan bahwa pasangan sequence tersebut memang berkerabat dekat, dan lainnya.

WSP Objective Function

Namun demikian, fakta di lapangan ternyata tidak semudah penjelasan di atas serta rumus yang menyertainya. Waktu dan memori komputer yang diperlukan untuk mencari alignment terbaik meningkat dengan cepat seiring dengan bertambahnya jumlah sequence. Pertambahan waktu dan memori tersebut sesuai dengan rumus O(N^M), dimana N adalah panjang sequence dan M adalah jumlah seqeunce. Nah jika kita ingin mencari alignment terbaik dari 15 sequence dengan panjang masing-masing sequence mencapai 1500 nukleotida, kira-kira waktu (dalam detik yang dibutuhkan akan setara dengan O(1500^15). Kesimpulannya adalah, mencari alignment tersebut satu per satu (exhaustive search) dapat dikatakan hampir tidak mungkin. Oleh karena itu dibutuhkan metode pencarian yang lebih cepat namun tetap akurat.

Program MSA dan FastMSA (Lipman et al. 1989) menggunakan teknik Branch and Bound untuk mencari alignment tersebut dan menjamin bahwa alignment terbaik pasti ditemukan. Namun demikian, program ini hanya mampu mengakomodasi maksimal hingga 15 sequence. Ketika kita ingin meng-align >15 sequence, kita perlu beralih ke metode heuristik. Metode-metode heuristik merupakan metode berbasis sampling yang menjadikannya lebih cepat, namun tidak menjamin akan mendapatkan alignment yang terbaik. Beberapa metode heuristik yang umum digunakan dalam multiple sequence alignment meliputi:

1. Progressive Alignment
Adanya hubungan timbal balik antara alignment dan hubungan filogenetik antar sequence di dalamnya memunculkan ide bahwa suatu alignment yang baik dapat dibuat berdasarkan hubungan filogenetiknya dalam bentuk sebuah pohon (Sankoff 1985). Namun demikian, penghasilan alignment sekaligus juga pohon filogenetik dari suatu sequence yang belum di-align merupakan hal yang rumit. Pendekatan nya adalah dengan menghasilkan suatu alignment sementara lalu membuat pohon (guide tree) dari alignment sementara tersebut, kemudian mengoptimasi alignment tersebut berdasarkan informasi kekerabatan antar sequence yang terdapat dalam pohon (Hogeweg & Hesper 1984). Metode ini terbukti relatif cepat dalam analisisnya sehingga dapat diaplikasikan untuk menangani dataset sequence yang besar. Namun demikian, metode ini tidak sepenuhnya memenuhi optimalitas sebagaimana yang dipersyaratkan dalam WSP objective function.

Salah satu program yang didasarkan pada metode progressive alignment ini adalah ClustalX atau ClustalW (Thompson et al. 1997; 1994). Perbedaan diantara keduanya hanya terletak pada tampilan saja. Bagi yang sering bermain dengan analisis filogenetik pasti telah akrab dengan program ini. Seperti yang telah dijelaskan sebelumnya, program clustal akan menghasilkan sebuah matriks Dij untuk semua kombinasi pasangan sequence. Setelah itu sebuah pohon neighbor-joining (NJ) akan dibuat berdasarkan matriks Dij tersebut dan selanjutnya disebut dengan guide tree (file dengan format .dnd). Guide tree ini akan menampilkan kedekatan antara sequence satu dengan lainnya, sehingga berdasarkan pohon inilah alignment antar sequence dilakukan. Pertama, sequence dengan sequence yang memiliki kekerabatan dekat di-align. Kemudian pasangan sequence yang telah di-align tersebut akan di-fix-kan dan kemudian di-align kembali dengan sequence lainnya yang dekat sesuai dengan yang tergambar pada guide tree. Proses ini terus dilakukan hingga penggabungan dua kelompok besar alignment sequence menjadi satu dataset alignment yang utuh.

2. Consistency-based Scoring
Progressive alignment memang menyediakan solusi cepat untuk multiple sequence alignment. Namun demikian, metode ini seringkali terjebak dalam kondisi optimal lokal (local optima) karena metode tersebut tidak mengevaluasi kembali alignment yang telah dilakukan seiring dengan pemasukan sequence baru untuk di-align berikutnya. Singkat kata, metode progressive alignment yang terlebih dahulu menggabungkan A dengan B akan langsung melakukan alignment antara AB dengan C tanpa mempertimbangkan bagaimana kedekatan AC atau BC. Hal inilah yang dicoba untuk diatasi oleh metode berbasis Consistency-based Scoring. Pada contoh di atas, metode Consistency-based scoring akan menggunakan informasi hasil alignment AB dan akan mempertimbangkan hasil alignment AC dan BC untuk menghasilkan alignment yang paling optimal untuk ABC (Kececioglu 1993).

Program T-COFFEE (Tree-based consistency objective function for alignment evaluation) dibuat berdasarkan metode ini (Notredame et al. 2000). Seperti yang telah dijelaskan di atas, metode ini berupaya untuk mencari alignment terbaik yang paling konsisten terhadap seluruh anggota sequence yang berada di dalamnya. Dalam hal kecepatan, program ini relatif lambat jika dibandingkan dengan program berbasis progressive alignment seperti Clustal. Namun demikian, metode ini dapat diandalkan untuk menghasilkan alignment yang lebih akurat.

3. Iterative Refinement Methods
Sebuah pandangan lain mengenai bagaimana menghasilkan sebuah multiple sequence alignment yang akurat didasarkan pada metode perulangan (iteration). Pada metode ini, dataset sequence dibagi secara acak ke dalam dua kelompok dan masing-masing di-align secara terpisah. Tahap ini diulang secara terus-menerus hingga dihasilkan sub-alignment dengan skor yang tinggi. Setelah itu kedua sub-alignment ini di-fix-kan dan kemudian di-align satu sama lain .

Program yang didasarkan pada metode Iterative Refinement Methods diantaranya adalah MAFFT (Multiple Alignment using Fast Fourier Transform) (Katoh et al. 2002; 2005) dan MUSCLE (Multiple Sequence Comparison by Log-Expectation) (Edgar 2004a,b). Alignment oleh kedua program ini relatif lebih cepat dari T-COFFEE dan juga mampu digunakan untuk menangani dataset yang besar.

Nah setelah kita sedikit mengenal tentang beberapa program multiple sequence alignment, kita pun kemudian bertanya mengenai program manakah yang sebaiknya kita gunakan. Pertimbangan terpenting untuk memilih program alignment haruslah kualitas hasil yang diberikan. Setelah itu barulah kita mempertimbangkan kemudahan dalam penggunaan serta cara mendapatkan program tersebut. Sebuah panduan oleh Edgar & Batzoglou (2006) merekomendasikan program alignment yang cocok dengan data yang dimiliki dari segi hasil dan waktu komputasi dapat membantu kita dalam memilih program tersebut.

Terakhir, ketika kita telah selesai melakukan alignment secara tekomputerisasi ada kalanya kita perlu menginspeksi hasil yang muncul dan melakukan alignment secara manual. Biar bagaimanapun, alignment secara manual tetap lebih baik dibandingkan secara otomatis menggunakan komputer karena kemampuannya dalam mengintegrasikan tambahan informasi. Selain itu daerah di dalam alignment yang terkesan mis-informatif juga dapat diketahui dan diproses hanya dengan alignment secara manual ini.

Oke, saia rasa sekian dulu tulisan saia mengenai sequence alignment. Semoga tulisan ini dapat membantu teman-teman yang penasaran dan ingin tahu proses apa yang berada di balik tombol "OK" atau "Compute" program-program alignment yang digunakan. Untuk lebih lengkapnya, bisa ditelusuri lebih lanjut pada referensi yang ada.

Regards,
Victor Apriel (KohVic)

Referensi
A. Buku
Higgins, D. & P. Lemey. 2009. Multiple Sequence Alignment. In The Phylogenetic Handbook: A Practical Approach to Phylogenetic Analysis and Hypothesis Testing 2nd Edition (P. Lemey, M. Salemi, & A. Vandamme eds.). Cambridge University Press: UK.

B. Jurnal

1. Edgar, R. C. 2004a. MUSCLE: a multiple sequence alignment method with reduced time and space complexity. BMC Bioinformatics 5: 113.
2. Edgar, R. C. 2004b. MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Research 32(5): 1792–1797.
3. Edgar, R. C. & S. Batzoglou. 2006. Multiple sequence alignment. Current opinions on Structural Biology 16 (3): 368–373.
4. Hogeweg, P. & B. Hesper. 1984. The alignment of sets of sequences and the construction of phylogenetic trees: An integrated method. Journal of Molecular Evolution 20: 175–186.
5. Katoh, K., K. Misawa, K. Kuma, & T.  Miyata. 2002. MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform. Nucleic Acids Research 30 (14): 3059–3066.
6. Katoh, K., K. Kuma, H. Toh, & T. Miyata. 2005. MAFFT version 5: improvement in accuracy of multiple sequence alignment. Nucleic Acids Research 33 (2): 511–518.
7. Kececioglu, J. 1993. The maximum weight trace problem in multiple sequence alignment.  Proceedings of the 4th Symposium on Combinatorial Pattern Matching, Springer-Verlag Lecture Notes in Computer Science 684: 106–119.
8. Lipman, D. J., S. F. Altschul, & J. D. Kececioglu. 1989. A tool for multiple sequence  alignment. Proceedings of the National Academy of Sciences 86: 4412–4415.
9. Notredame, C., D. G. Higgins, & J. Heringa. 2000. T-Coffee: a novel method for fast and  accurate multiple sequence alignment. Journal of Molecular Biology 302: 205–217.
10. Sankoff, D. (1985). Simultaneous solution of the RNA folding, alignment and protosequence  problems. SIAM Journal on Applied Mathematics 45: 810–825.
11. Thompson, J. D., D.G. Higgins, & T. J. Gibson. 1994. CLUSTALW: improving the sensitivity  of progressivemultiple sequence alignment through sequence weighting, position-specific gap  penalties and weight matrix choice. Nucleic Acids Research 22: 4673–4680.
12. Thompson, J. D., T. J. Gibson, F. Plewniak, F. Jeanmougin, & D. G. Higgins. 1997. The  CLUSTAL X windows interface: flexible strategies for multiple sequence alignment aided by  quality analysis tools. Nucleic Acids Research 25: 4876–4882.