Sequence Alignment by Dynamic Programing [ArgorBio]

       Sequence Alignment merupakan cara mengetahui kemiripan dua buah sequence dimana sequence-sequence yang ingin dibandingkan akan disejajarkan. Cara yang paling mudah untuk mengetahui kemiripan dua buah sequence yaitu dengan cara melihat dan langsung menetapkan apakah sequence tersebut similar atau tidak. cara lain yang dapat digunakan untuk mengetahui kemiripannya yaitu dengan menggunakan Dinamic Programing. pada tulisan kali ini saya akan membahas tentang cara menggunakan Dynamic Programing untuk membandingkan dua sequence.

dalam Sequence Alignment terdapat dua hal yang dibandingkan, yaitu
A. Global Alignment
B. Local Alignment

A. Pertama akan kita bahas Global Alignment terlebih dahulu.
[Algoritma] terdapat tiga tahap dalam kasus ini:
1. Inisialisasi (cell kuning)
    Isi tepi matriks dengan nilai nol.

2. mengisi nilai matriks (cell biru)
    isi matriks

3. Trace back
 Pada Global Alignment dilakukan dari score yang optimal yaitu dari nilai matrik M[m,n] menuju inisalisasi cell (0) yang mana saja.

 

contoh soal:

 jawab:

trace back:

B. kedua akan kita bahas local Alignment.
perbedaan yang paling mendasar antara global alignment dan local alignment terdapat pada step ketiga yaitu pada proses traceback, dimana proses traceback awal dilakukan dimilai dari nilai maksimal dari matrik tersebut bukan dari nilai optimalnya. tetapi tidak memiliki nilai negatif alias memiliki nilai minimal 0.