Modul ini memperkenalkan dynamic programming untuk menyelaraskan dua sekuen secara global. Fokusnya adalah memahami tabel DP, aturan scoring, dan traceback tanpa membebani mahasiswa dengan implementasi kode.
Misalkan terdapat dua fragmen sekuen DNA pendek. Pertanyaan biologisnya tampak sederhana: seberapa mirip kedua sekuen tersebut? Untuk menjawab secara objektif, diperlukan aturan alignment dan sistem scoring.
Secara visual keduanya tampak memiliki kemiripan, tetapi komputer membutuhkan aturan yang eksplisit. Apakah karakter harus disejajarkan langsung, digeser, atau diberi gap? Setiap pilihan memengaruhi skor akhir.
Dua pasien dapat memiliki riwayat yang mirip tetapi tidak identik. Satu pasien mengalami demam, batuk, dan sesak. Pasien lain mengalami demam, batuk, mual, lalu sesak. Pertanyaannya: apakah perbedaannya hanya satu gejala tambahan, atau mengarah pada kondisi yang berbeda?
Sequence alignment menerapkan logika serupa pada DNA, RNA, atau protein. Setiap mismatch dan gap dapat merepresentasikan kemungkinan variasi biologis, termasuk substitusi, insersi, atau delesi.
Jumlah kemungkinan alignment bertambah sangat cepat ketika panjang sekuen meningkat. Karena itu, mencoba semua kemungkinan bukan pendekatan yang efisien untuk data biologis skala besar.
Dynamic programming (DP) memecah masalah besar menjadi sub-masalah kecil. Skor terbaik pada setiap posisi disimpan dalam tabel sehingga hasil sebelumnya dapat digunakan kembali.
Ketika dokter menerima pasien rujukan, informasi dari rekam medis sebelumnya menjadi dasar pengambilan keputusan berikutnya. Dynamic programming bekerja dengan prinsip serupa: hasil yang sudah dihitung disimpan dan digunakan kembali.
Setiap sel pada tabel DP menyimpan skor terbaik untuk sub-alignment tertentu. Sel berikutnya cukup melihat tiga tetangga: diagonal, atas, dan kiri.
Sebelum kita bisa menghitung apa pun, kita harus menyepakati nilai untuk tiga kejadian: ketika dua karakter cocok, ketika dua karakter berbeda, dan ketika kita harus menyisipkan gap.
Dalam biologi, insertion/deletion (indel) lebih merusak daripada single nucleotide polymorphism (SNP). Indel sering menyebabkan frameshift mutation, seluruh asam amino sesudahnya berubah. Mismatch (SNP) hanya mengubah satu kodon, dan kadang malah silent (tidak mengubah protein).
Itulah kenapa scoring untuk gap kita buat lebih negatif dari mismatch. Algoritma akan "ragu" untuk memasukkan gap kecuali memang sangat menguntungkan.
Untuk setiap sel (i, j) di tabel, nilainya adalah maksimum dari tiga pilihan:
Kita pilih yang nilainya paling besar. Itu saja. Tabel akan terisi dengan sendirinya mengikuti aturan ini, kotak demi kotak, mulai dari pojok kiri atas.
Pilih mode latihan, lalu isi tabel dengan mengklik sel kosong. Mode terpandu menampilkan formula untuk sel aktif, sedangkan mode mandiri digunakan untuk evaluasi dan persiapan ujian.
Mulai dari pojok kiri atas dan kerjakan ke kanan-bawah. Sel yang sudah benar akan terkunci (warna hijau).
Skor akhir:
Tabel terisi adalah setengah dari pekerjaan. Bagian kedua adalah traceback: menelusuri kembali dari pojok kanan bawah ke pojok kiri atas, mengikuti panah yang menunjukkan pilihan optimal di setiap langkah.
Mulai dari sel pojok kanan bawah F(m, n). Di setiap sel, lihat dari mana nilainya berasal:
Diagonal → kedua karakter sejajar (match atau mismatch).
Atas → karakter dari sekuen vertikal sejajar dengan gap.
Kiri → karakter dari sekuen horizontal sejajar dengan gap.
Setelah Anda menyelesaikan tabel di atas, tombol "Tampilkan Traceback" akan aktif. Klik untuk melihat jalur optimal divisualisasikan dengan warna merah-koral, dan alignment akhirnya muncul di bawah.
Setelah menyelesaikan modul ini, Anda harus bisa:
✓ Menjelaskan mengapa naive approach (coba semua alignment) tidak feasible.
✓ Mengisi tabel DP 5×5 atau 6×6 secara manual dengan scoring matrix yang diberikan.
✓ Melakukan traceback dari pojok kanan bawah dan menuliskan alignment akhir.
✓ Menjelaskan secara biologis kenapa gap penalty lebih besar dari mismatch.
✓ Menghubungkan konsep DP dengan analogi rekam medis (tidak menghitung ulang dari nol).
Pada UAS, Anda akan mendapat soal seperti: "Diberikan dua sekuen pendek dan scoring matrix, isi tabel DP berikut dan tentukan alignment optimal beserta skornya." Latihan mandiri dengan tabel di atas (mode mandiri) adalah persiapan terbaik.