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)