Sebuah Tulisan Evolusi dan Filogeni: Alignment Sequence Asam Amino Dengan Metode Dynamic Programming

Hmm...ga bisa tidur di malam hari itu sunggu gak asik. Jadi yasuda deh, kalo emang ini otak maunya mikir terus, saia kasi supaya mikir dah. Oke malam ini saia akan mencoba untuk menulis tentang tahapan dalam alignment sequence asam amino menggunakan metode dynamic programming.

Sebelum masuk ke dalam inti cerita, persilahkan saia untuk sedikit menjelaskan apa itu dynamic programming. Alignment atau pensejajaran pasangan sequence dalam prosesnya dapat memberikan banyak sekali kombinasi alignment yang mungkin dibuat. Untuk pasangan sequence dengan 300 residu saja, kombinasi tersebut dapat mencapai 10^88. Nah dalam hal ini, metode dynamic programming memungkinkan kita untuk mendapatkan suatu alignment yang optimal tanpa perlu mengevaluasi ke-10^88 kombinasi tersebut satu per satu. Salah satu algoritme yang didasarkan pada metode dynamic programming tersebut adalah algoritme Needleman-Wunsch. Dasar dari algoritme tersebut adalah prinsip optimalitas Bellman, yang berbunyi "any subsolution of an optimal solution is itself an optimal solution". Err..silahkan terjemahkan sendiri yak. Saia akan mempraktekan makna kalimat ini saja dalam contoh kita nanti.

Oke, sekarang mari kita masuk ke contoh menggunakan 2 sequence asam amino, yakni sequence X (GRQTAGL) dan sequence Y (GTAYDL). Perlu diketahui bahwa alignment sequence asam amino didasarkan pada similaritas biokimiawi rantai samping masing-masing asam amino. Terdapat pasangan-pasangan asam amino yang mirip secara biokimiawi yang cenderung lebih mudah tersubstitusi dibandingkan dengan asam amino lainnya. Preferensi substitusi masing-masing pasangan asam amino ini sudah dipetakan, dan salah satunya yang akan kita gunakan adalah matriks similaritas BLOSUM62 (Gambar 1). Nah, kembali kepada dua sequence asam amino yang ingin kita align sebelumnya. Pertama, kita letakan sequence X dan Y dalam sebuah matriks yang setiap elemen nya diisi dengan skor bedasarkan matriks similaritas BLOSUM62. Oh, jangan lupa untuk menyertakan kemungkinan pemberian gap pada ujung dari masing-masing sequence dengan memberikan complete gap column pada kolom dan baris pertama. Matriks tersebut dapat dilihat pada Gambar 2.

Gambar 1. Matriks BLOSUM62 untuk similaritas sifat biokimia antar pasangan asam amino.

Gambar 2. Matriks sequence asam amino dengan skor bedasarkan matriks BLOSUM62.

Selanjutnya, kita perlu membuat matriks F yang setiap elemennya diisi berdasarkan matriks pertama dengan mempertimbangkan tiga skenario:
1. Sebuah substitusi (Xi, Yi) yang bergerak dari elemen (i-1, j-1) ke elemen (i,j).
2. Insersi pada X (atau delesi pada Y) yang bergerak dari elemen (i-1, j) ke elemen (i,j).
3. Insersi pada Y (atau delesi pada X) yang bergerak dari elemen (i, j-1) ke elemen (i,j).
Dengan demikian, pencarian arah terbaik menuju suatu elemen (i,j) dapat dilakukan dengan mencari nilai maksimum dari fungsi berikut:

F(i,j) = max{F(i-1, j-1)+s(Xi, Yi); F(i-1, j)+g; F(i, j-1)+g}        (Pers 1)

Dimana: s(Xi, Yi) = skor similaritas pada elemen (i,j) berdasarkan matriks BLOSUM62 yang telah dituliskan pada matriks pertama; g = gap penalty (bernilai -8)

Menggunakan fungsi di atas, kita dapat mengisi matriks F secara bertahap dari kiri ke kanan lalu atas ke bawah. Perlu diingat juga, setiap skor yang telah diisikan pada elemen dalam matriks F harus juga diketahui dari elemen mana skor itu berasal. Elemen tersebut dinamakan pointer dan penandaan pointer dilakukan dengan memberikan tanda panah dari suatu elemen yang diisi ke pointer yang menjadi acuannya. Kolom pertama (i=1) hanya mengandung gap (*) dari atas ke bawah, sehingga pengisian untuk seluruh elemen dalam kolom tersebut hanya mengacu pada skenario 3 dan mereduksi Pers. 1 menjadi F(i,j) = {(F(i, j-1)+g)}. Hal yang sama juga berlaku pada baris pertama (j = 1), yakni mereduksi Pers. 1 menjadi F(i,j) = {(F(i-1, j)+g)}.

Elemen pertama pada matriks F yang perlu dievaluasi untuk keseluruhan 3 skenario adalah elemen (2,2), dimana:

F(2,2)    = max{F(1, 1)+s(Xi, Yi); F(1, 2)+g; F(2, 1)+g}
              = max{0+6; -8+(-8); -8+(-8)}
              = max{6; -16; -16}

memberikan skenario pertama (substitusi) dengan skor tertinggi. Skor ini diisikan ke dalam matriks F untuk elemen (2,2). Sebuah tanda panah juga diberikan dari elemen (2,2) ke pointer yang berupa elemen (1,1). Berikutnya, elemen (i=3, j=2) dapat dihitung dengan:

F(2,3)    = max{F(1, 2)+s(Xi, Yi); F(1, 3)+g; F(2, 2)+g}
              = max{-8+(-2); -8+(-8); 6+(-8)}
              = max{-10; -16; -2}

Gambar 3. Matriks F untuk dua sequence asam amino. Alignment optimal untuk kedua sequence ditunjukan dengan tanda panah merah dan biru.

yang dalam hal ini memberikan skenario kedua (insersi ada X atau delesi pada Y). Sebuah tanda panah juga diberikan dari elemen (2,3) ke elemen (2,2). Perhitungan ini terus dilanjutkan hingga semua elemen matriks F terisi penuh (Gambar 3). Perhatikan bahwa ada elemen (contohnya elemen (3,4)) dengan lebih dari satu pointer (memiliki >1 tanda panah), yang artinya adalah ada lebih dari satu skenario yang memberikan nilai sama besar.

Nah, berdasarkan matriks F ini kita akan menggambarkan alignment antara sequence X dan Y ini. Proses penggambaran alignment dimulai dari elemen terakhir dengan nilai terbesar, yakni elemen (7,8). Dari elemen tersebut kita tinggal menggambarkan alignment dengan mengikuti tanda panah hingga ke elemen awal. Proses ini disebut dengan proses traceback yang didasarkan pada prinsip optimalitas Bellman. Jika suatu elemen terakhir memberikan nilai optimal, maka elemen-elemen yang menuju ke arah sana juga merupakan elemen dengan nilai optimal.

Dari proses traceback ini kita mendapatkan dua alignment, yakni:
Alignment 1
GRQTAGL
GT-AYDL

Alignment 2
GRQTAGL
G-TAYDL

Ada pertanyaan?

Regards,
Victor Apriel (KohVic)

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.

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

Wuoooo...lama sudah saia menghilang dari dunia ini dalam rangka mencari pencerahan penelitian tesis saia. Hari ini, yaa tepatnya malam ini saia pun ingin mencoba peruntungan saia dalam membuat tulisan salah satu dalam serial Sebuah Tulisan Evolusi dan Filogeni. Well, judulnya masih terkait dengan tulisan sebelumnya yang berjudul "Sebuah Tulisan Evolusi dan Filogeni: Homologi dan Alignment". Namun pada tulisan kali ini saia ingin menekankan kepada alignment itu sendiri. Yasuda, kita mulai saja yak :)

Sequence alignment dapat didefinisikan sebagai sebuah proses penjejeran dua atau lebih sequence (nukleotida atau asam amino) sehingga keduanya memiliki kemiripan setinggi mungkin dalam hal posisi karakter penyusun sequence-nya. Dengan demikian, sequence alignment merupakan proses yang dilakukan berdasarkan asumsi homologi, yakni sebuah pandangan bahwa sequence homolog dulunya berasal dari satu sequence nenek moyang yang berdivergensi akibat mutasi dan seleksi.

Nah, sekarang ketika kita menghadapi sebuah dataset berisi sequence, bagaimana caranya kita untuk meng-align sequence-sequence tersebut satu sama lain hingga tercapai kemiripan tertinggi secara keseluruhan? Oh ya mudah saja, tinggal masukan ke program komputer, klik "OK" atau "Compute", tunggu beberapa saat dan cling...wuala this is it!! sequence alignment ala chef...oops...ehem. Yaa mungkin kita bisa dengan mudahnya langsung menggunakan cara tersebut. Namun, tahukah kita bahwa akurasi dari sebuah analisis filogenetik yang paling mendasar justru terletak pada sequence alignment yang digunakan? Nah untuk itulah memahami bagaimana sebuah proses sequence alignment ini menjadi sangat penting, sekalipun nantinya kita akan meminta bantuan komputer untuk melakukan sisanya. Dalam menangani dataset sequence proses alignment dibagi menjadi dua tahap, yakni alignment pasangan sequence (pairwise sequence alignment) dan alignment banyak sequence (multiple sequence alignment). Dalam tulisan ini saia akan membahas mengenai Pairwise Sequence Alignment terlebih dahulu.

Secara umum terdapat tiga teknik dalam pairwise sequence alignment, yakni: (1) secara visual, (2) menggunakan dot-matrix, dan (3) menggunakan dynamic programming algorithm. Kita akan membahasa satu per satu. Alignment secara visual merupakan teknik yang paling sederhana, cepat, sekaligus akurat. Hal ini disebabkan karena otak kita mampu mengintegrasikan seluruh informasi tambahan kepada pasangan sequence yang sedang di-align. Namun demikian, alignment secara visual-manual ini juga memiliki keterbatasan  terhadap panjang sequence dan juga keteraturannya. Ketika seuatu pasangan sequence terlalu panjang dan semakin tidak teratur, maka dijamin otak kita akan overheat dibuatnya.

Teknik kedua adalah dengan alat bantu yang bernama dot-matrix. Ini merupakan suatu matriks dimana kita bisa menempatkan pasangan sequence pada bagian kolom dan baris sehingga kita bisa mencocokannya sekaligus juga membuat alignment darinya. Cara melakukannya akan dijelaskan di bawah ini dan untuk lebih jelasnya dapat dilihat pada Gambar 1:
1. Letakkan sequence pertama pada bagian atas matriks (kolom) dan sequence kedua pada bagian kiri matriks (baris).
2. Berikan tanda titik (dot) pada setiap karakter yang cocok antara kedua sequence tersebut.
3. Hubungkan antara titik satu dengan lainnya. Apabila pasangan sequence tersebut adalah identik atau mirip antara satu dengan lainnya, maka akan terbentuk sebuah garis diagonal pad matriks tersebut.
Perlu diketahui bahwa garis penghubung antar titik dalam dot-matrix tidak selamanya diagonal. Adanya insersi-delesi (indel) pada sequence dapat mengubah garis tersebut menjadi vertikal atau horizontal. Garis vertikal mencerminkan adanya delesi pada sequence pertama atau insersi pada sequence kedua dan garis horizontal adalah sebaliknya. Terkadang garis diagonal yang dibuat pun tidak selalu melewati seluruh titik yang ada. Apabila ada suatu elemen kosong (tanpa tanda titik) dalam matriks yang dilewati oleh garis, maka itu menandakan adanya substitusi pada yang terjadi antara kedua sequence yang dibandingkan.

Gambar 1. Dot-matrix sequence alignment.

Penarikan garis dalam dot-matrix terkadang juga menghasilkan lebih dari satu garis. Hal ini berarti ada lebih dari satu skenario alignment yang perlu dipertimbangkan. Gambar 2 memberikan contoh kasus dimana terdapat dua skenario yang dapat dipakai dalam alignment pasangan sequence. Skenario pertama memberikan alignment dengan dua buah substitusi dan satu buah gap, sementara skenario kedua memberikan alignment dengan lima buah gap dan tanpa substitusi.

Gambar 2. Two possible alignment scenarios.

Penggunaan dot-matrix dalam alignment pasangan sequence cukup bagus untuk dilakukan pada sequence yang pendek. Seiring dengan semakin bertambahnya panjang sequence, maka titik yang muncul dalam dot-matrix akan semakin banyak. Hal ini disebabkan suatu pasangan sequence nukleotida yang hanya memiliki empat karakter (A, T, G, dan C) memiliki probabilitas kesamaan posisi nukleotida sebesar 25%. Dengan demikian, seiring dengan semakin panjangnya suatu sequence, akan semakin banyak terdapat garis-garis diagonal atau alignment semu akibat kemiripan nukleotida secara kebetulan ini.

Untuk mengatasi masalah ini, dikembangkan metode pemberian skor (scoring) untuk menghasilkan sebuah alignment yang bagus. Salah satu metode yang umum digunakan didasarkan pada nilai similaritas nukleotida antar pasangan sequence yang kemudian diadaptasi dalam program komputer. Metode ini disebut juga dengan Needleman-Wunsch Dynamic Programming Algoritm atau yang lebih sering disebut sebagai Dynamic Programming.  Algoritme ini mengikuti Bellman's Optimality Principle yang berbunyi "if the final element reports the score for the best path, then the sub-solution leading to this element is also lying on the optimal path."

Nah berdasarkan prinsip Oom Bellman tersebut tentunya skor perlu diberikan dalam setiap elemen di dalam matriks alignment nya. Terdapat sedikit perbedaan dalam pemberian skor untuk alignment sequence nukleotida dan asam amino, dimana pemberian skor dalam sequence nukleotida biasanya bernilai 1 dan kelipatannya. Hal ini didasarkan pada asumsi bahwa substitusi pada nukleotida bersifat simetris/sama dari satu nukleotida ke nukleotida lainnya. Asumsi ini tidak berlaku pada sequence asam amino karena adanya pertimbangan sifat biokimia rantai sampingnya. Dalam tulisan ini saia akan memakan sequence nukleotida sebagai contohnya.

Gambar 3. Dynamic programming sequence alignment.

Pemberian skor didasarkan pada kesamaan nukleotida dari sequence pertama dengan sequence kedua. Apabila sama, maka elemen dalam matriks mendapatkan tambahan nilai 1. Apabila tidak maka skornya 0. Pemberian skor ini dilakukan secara berurut dari kiri ke kanan dan atas ke bawah. Nah sekarang coba perhatikan Gambar 3. Skor 1 diberikan pada elemen baris pertama kolom pertama di dalam matriks karena kedua sequence sama-sama memiliki nukleotida A. Kenapa nilainya 1? itu karena nilai awal dalam mengisi suatu alignment adalah nol akibat tidak ada yang dibandingkan, sehingga nilai 1 pada elemen pertama itu adalah hasil dari penjumlahan 0+1=1. Selanjutnya kita akan mengisi elemen lainnya dari kiri ke kanan. Elemen lainnya pada baris pertama diisi dengan nilai 0 karena selain seperti hal di atas yakni tidak ada nukleotida sebelumnya yang bisa dibandingkan, nukleotida A pada sequence kedua (baris pertama) tidak cocok dengan nukleotida lainnya pada sequence pertama (kolom kedua hingga kelima). Masih bertahan di Gambar 3, sekarang coba perhatikan elemen pada baris kedua kolom kedua. Kedua sequence sama-sama memiliki nukleotida T dan itu berarti cocok. Dengan demikian skor tambahan 1 diberikan pada elemen ini. Perhatikan bahwa ada elemen yang sebelumnya telah mendapat nilai 1. Hal ini berarti elemen pada baris kedua kolom kedua bernilai 2 sebagai akibat dari skor 1 dari elemen sebelumnya tersebut ditambah skor 1 dari kecocokan nukleotida pada elemen ini. Pengisian elemen ini dilakukan dengan cara seperti itu hingga semuanya terisi.

Setelah semuanya terisi, maka selanjutnya kita akan menggambarkan penunjuk (pointer) untuk membantu kita mengarahkan dari elemen mana skor-skor tersebut berasal. Suatu penunjuk digambar dari elemen pojok kanan bawah ke elemen yang terletak di sebelah kiri atasnya yang memiliki skor sama atau lebih rendah dari elemen tersebut (Gambar 3, tengah). Sesudah itu kita kemudian dapat menentukan mana alignment yang terbaik berdasarkan penunjuk ini. Sebuah prosedur yang dinamakan sebagai Traceback untuk menghasilkan suatu grafik arah (Path Graph). Prinsip traceback ini didasarkan pada prinsip Oom Bellman di atas dan dimulai dari elemen ujung kanan bawah yang memiliki skor tertinggi. Pada Gambar 3 (kanan) kita melihat bahwa elemen ujung kanan bawah dengan skor tertinggi adalah 4, maka dari titik inilah kita membuat alignment untuk kedua sequence yang dibandingkan. Yup, sequence alignment menggunakan metode ini dibuat dari kanan ke kiri. Berdasarkan path graph yang dihasilkan dari proses traceback, maka kita dapat menghasilkan alignment nya.

Perlu diketahui bahwa proses alignment yang dijelaskan di atas belum mengikutsertakan gap penalty akibat adanya gap/indel yang terbentuk selama proses alignment. Umumnya kita menganggap bahwa indel lebih jarang terjadi dibandingkan dengan substitusi, sehingga sebuah alignment dengan jumlah gap yang lebih banyak ketimbang residu nukleotidanya seperti contoh di bawah ini tentu tidak masuk akal:

VHLTPEEKSAVTALWGKVNVDEVGGEAL...
V-----------------NEEEVGGEAL...
Nah untuk menghindari adanya alignment seperti ini, gap penalty perlu dintegrasikan ke dalam algoritme alignment. Detail mengenai gap penalty dapat dibaca lebih lanjut dalam buku-buku analisis filogenetik lainnya seperti Graur & Li (1991) atau Nei & Kumar (2000).

Oke, saia rasa tulisan kali ini saia cukupkan hingga disini dulu. Selanjutnya saia akan membahas tentang multiple sequence alignment, yakni bagaimana proses alignment untuk lebih dari dua sequence. Ditunggu yak!!

Regards,
Victor Apriel (KohVic)