Penerapan String Alignment menggunakan Dynamic Programming pada Pengecekan DNA Manusia

 Penerapan String Alignment menggunakan Dynamic Programming pada Pengecekan DNA Manusia

 

Rahmat Ridha Mustakim (1103130065)

Wildan Pratama Saputra (1103130045)

Prodi S1Teknik Informatika Telkom University

Jl. Telekomunikasi no 1 Bandung

e-mail: beingbadfeelsgood@gmail.com

ABSTRAK

Pengecekan DNA manusia pada jaman sekarang termasuk kedalam hal yang sangat vital. Dalam beberapa kasus criminal hingga merenggut nyawa seseorang terkadang menjadikan tugas para penegak hukum semakin berat. Tak jarang korban ditinggalkan oleh sang pelaku tanpa identitas satupun. Satu-satunya cara untuk mengungkap identitas sang korban adalah dengan cara tes DNA. Tes DNA dilakukan dengan cara menyocokkan DNA korban dengan DNA tester, yaitu bisa didapat dari terduga keluarga korban. Dalam program ini akan mencoba membangun sebuah aplikasi untuk menyocokkan rantai DNA sample dengan rantai DNA tester menggunakan algoritma dynamic programming, yang nantinya akan mengeluarkan kecocokan antara kedua DNA yang telah diuji.

Kata kunci: kriminal, DNA, rantai DNA, dynamic programming.

1.  PENDAHULUAN

Saat ini sering terdengar ditelinga kita sebuah istilah kedokteran forensik modern yakni pengecekan DNA Manusia. Sederhananya, pengecekan DNA manusia ini merupakan salah satu metode untuk mengenali garis keturunan seseorang  dengan mengambil sampel DNA. Pengecekan DNA ini merupakan suatu hal yang penting di dunia kedokteran, salah satunya ketika ditemukannya mayat tanpa identitas, ataupun kasus kepemilikan anak, dll sehingga pihak berwajib kesulitan dalam memutuskan kasus-kasus tersebut. Oleh karena itu diperlukannya pengecekan DNA orang tersebut dengan DNA orang yang diklaim.

DNA didunia Informatika biasa direpresentasikan dengan sebuah array dengan beragam jenis tipe data masukan, salah satunya dengan huruf atau alfabet. Secara sederhana kita juga dapat coba menghitung tingkat kecocokan DNA yang direpresentasikan dengan alfabet tersebut atau istilah informatikanya yakni Sequences Aligment/String Matching dengan menggunakan teknik Dynamic Programming. Tujuannya, kita bisa mencoba mencari urutan DNA yang nilai kecocokannya paling tinggi/optimal dengan DNA klaim.

             Penyejajaran sekuens (sequence alignment) adalah proses penyusunan/pengaturan dua atau lebih sekuens sehingga persamaan sekuens-sekuens tersebut tampak nyata. Hasil dari proses tersebut juga disebut sebagai sequence alignment atau alignment saja. Baris sekuens dalam suatu alignment diberi sisipan (umumnya dengan tanda "–") sedemikian rupa sehingga kolom-kolomnya memuat karakter yang identik atau sama di antara sekuens-sekuens tersebut. String alignment adalah sebuah metode yg diadaptasi dari metode sequence alignment. Yang membedakan adalah penggunaan variable string dalam sequence. Berikut adalah contoh alignment DNA dari dua sekuens pendek DNA yang berbeda, "ccatcaac" dan "caatgggcaac" (tanda "|" menunjukkan kecocokan atau match di antara kedua sekuens),

Contoh penerapan string alignment

2.  METODE

Terdapat beberapa metode untuk menyocokkan antara kedua rantai DNA yang akan diuji. Salah satunya dengan menggunakan algoritma dynamic programming. Penggunaan Dynamic Programming merupakan metode yang sangat cocok  dalam pemecahan masalah String Aligment untuk kasus DNA ini. Menginputkan array DNA klaim dan selanjutnya dilakukan pengecekan terhadap array DNA yang mau diuji dengan cara melakukan penggeseran deret array DNA yang mau diuji sehingga memiliki nilai kecocokan terhadap DNA klaim. karena solusi yang akan keluar tidak hanya satu sehingga perlunya pencarian solusi yang dianggap nilai kecocokannya paling optimal diantara solusi yang lainnya atau dari setiap rangkaian solusi sebelumnya 

2.1  Dynamic Programming

Dynamic Programming (biasa disingkat DP) adalah suatu teknik algoritma untuk memecahkan masalah dimana solusi optimal dari masalah tersebut dapat dipandang sebagai suatu deret keputusan dengan solusi optimalnya diperoleh berdasarkan rangkaian keputusan sebelumnya yang dilakukan secara simultan.

Dalam kasus penyocokan rantai DNA ini kita menggunakan algoritma dynamic programming dengan cara menselaraskan (menyamakan) string antar rantai DNA. Jadi rantai DNA nantinya akan diumpamakan sebagai sebuah string yang nantinya akan dicocokkan dengan string lainnya agar ditemukan kesamaan antar satu dengan string lainnya. Dalam kasus ini, inputan string DNA hanya terdapat 4 karakter; C (cytosine), G (guanine), A (adenine), T (thyimine).

Sekarang kita coba ambil contoh pada uji coba pencocokan 2 rantai DNA. Misalkan kita memiliki dua string DNA, TCGAGC dan AAGCTA. Dua string DNA tadi akan dimisalkan dengan string S dan string T dengan masing - masing memiliki panjang string N dan M.

s: = ' TCGAGCAT’; t: = ' AAGCTA ';

s: = TCGAGCAT

t: = AAGCTA

n: = panjang (s); m: = panjang (t);

n: = 8

m: = 6

     Lalu kita akan menyimpan kedua string ini dalam satu matriks yang kita beri nama matriks D. Matriks D dibuat untuk menyimpan hasil paling optimal dari perhitungan dynamic programming untuk setiap pasangan substring hingga saat itu. Matriks ini memiliki dimensi (m + 1) dan (n + 1). Pada awalnya matriks terlihat seperti ini:

Tabel awal matriks D

		T	C	G	A	G	C	A	T
	0
A
A
G
C
T
A

Cara untuk mengisi tabel matriks diatas adalah dengan mengacu pada tata aturan rantai DNA yang dinamakan Scroing Matrix. Scoring Matrix ini dibuat sesuai kebutuhan peneliti tetapi sebaiknya penilaiannya berdasarkan dasar-dasar pada kondisi yang sebenarnya. Karena objek dari string alignment ini adalah DNA maka scoring matrix ini dibuat berdasarkan prinsip-prinsip dalam pencocokan DNA yaitu: Empat basa DNA terdiri dari dua jenis, purin (A dan G) dan pirimidin (T dan C). Purin secara kimiawi mirip satu sama lain dan pirimidin secara kimiawi mirip satu sama lain. Oleh karena itu, kami akan menentukan substitusi antara purin dan purin atau pirimidin antara dan pirimidin (transisi) terlalu besar dibandingkan dengan substitusi antara purin dan pirimidin (transversi). Kami akan menggunakan matriks berikut untuk substitusi dan manyocokkan. Bernilai 2 jika bertemu basa DNA yg sama, bernilai 1 untuk purin dengan purin atau pirimidin dengan pirimidin, dan bernilai -1 jika purin bertemu dengan pirimidin dan sebaliknya.

Tabel sim_mat hasil dari Scoring Matrix

Buat sebuah yang kita namakan sim_mat dengan nilai-nilai hasil dari perhitungan tabel diatas. Variabel gap_score ditugaskan dengan hukuman kesenjangan -2.

                Selanjutnya, kita perlu melakukan inisiasi perhitungan. Insiasi perhitungan memiliki aturan elemen pertama dari matriks yg diisi adalah D[1,1] dan diisi dg nilai 0. Diisi dengan nilai 0 karena tidak ada aturan penalty nilai untuk alignment karakter kosong. Lalu gunakan nilai dari D[i-1, j-1], D[i, j-1] dan D[i-1, j] untuk menentukan nilai dari setiap D[i,j]. Kolom dan baris pertama dari matriks D merupakan nilai dari alignment sub-string s[1..j} dan t[1..i] dengan panjang gap_string j atau i. Lalu kita lakukan rekursif pada kolom dan baris pertama dengan aturan sbb;

                D[1,j] = D[1,j-1] + gap_score

                D[I,1] = D[i-1,1] + gap_score

Relasi ini nantinya akan digunakan pada perhitungan untuk mengisi nilai kolom dan baris pertama,

Sehingga nantinya matriks D akan terisi sebagai berikut :

		T	C	G	A	G	C	A	T
	0	-2	-4	-6	-8	-10	-12	-14	-16
A	-2	0	0	0	0	0	0	0	0
A	-4	0	0	0	0	0	0	0	0
G	-6	0	0	0	0	0	0	0	0
C	-8	0	0	0	0	0	0	0	0
T	-10	0	0	0	0	0	0	0	0
A	-12	0	0	0	0	0	0	0	0

             Langkah selanjutnya yaitu mengisi setiap D[i,j] dengan menggunakan prinsip rekursif untuk menyelesaikan sisa dari matriks D

1. Apabila nilai tertinggi berasal dari element D[i-1,j-1] maka karakter pada s[i] dan t[j] cocok.

2. Apabila nilai tertinggi berasal dari elemen D[i-1,j] maka gap pada string s akan bertemu karakter pada string t.

3. Apabila nilai tertinggi berasal dari elemen D[I,j-1] maka gap pada string akan bertemu karakter pada string s.

Ulangi langkah tersebut hingga i dan j dan nilai dari ketiga kemungkinan, lalu simpan nilai maksimumnya pada D[i,j]. Setelah semua elemen D[i,j] terisi, nilai dari alignment umum akan berada pada matriks D[m+1, n+1]

Sehingga isi matriks D menjadi:

		T	C	G	A	G	C	A	T
	0	-2	-4	-6	-8	-10	-12	-14	-16
A	-2	-1	-3	-3	-4	-6	-8	-10	-12
A	-4	-3	-2	-2	-1	-3	-5	-6	-8
G	-6	-5	-4	0	-1	1	-1	-3	-5
C	-8	-5	-3	-2	-1	-1	3	1	-1
T	-10	-6	-4	-4	-3	-2	1	2	3
A	-12	-8	-6	-3	-2	-2	-1	3	1

Setelah matriks D terisi oleh semua nilai, langkah selanjutnya adalah membentuk alignment. Untuk membuat alignment kita harus melakukan penelusuran ulang untuk membuat suatu pola baru dari posisi D[m+1, n+1] menuju D[1,1] yang akan menghasilkan nilai maksimal.

Pada akhir dari proses I dan j akan bernilai 1. Jika belum bernilai 1 maka akhiri dengan menambahkan gap pada sisa - sisa string  hingga bernilai 1.

Sehingga hasil akhir string yang telah dilakukan proses membentuk alignment sebagai berikut:

Contoh output pada program

IV. KESIMPULAN

Kesimpulan yg dapat kami ambil berdasarkan paper yang kami buat adalah dynamic programming dapat digunakan sebagai algoritma dalam pembuatan mesin untuk menyocokkan rantai DNA. Dynamic Programming ini memiliki beberapa kelebihan diantaranya mampu bekerja lebih optimal karena menguraikan permasalahan menjadi sub-sub masalah yang lebih kecil serta lebih fleksibel dibandingkan dengan algoritma lainnya.

 REFERENSI

[1]     Sitanggang, Jujur Soaloon. (2015, December 9^th). Retrieved from http://soalparna.blogspot.co.id: http://soalparna.blogspot.co.id/2015/03/teori-system-dynamic-programming.html 

[2]     Cannarozzi, Gina. (2015, December 9^th). Retrieved from http://biorecipes.com:

http://biorecipes.com/DynProgBasic/code.html

[3]     Varian, Edria Albert,  Aplikasi Program Dinamis Dalam String Alignment Untuk Melakukan Penyocokan DNA,Program Studi Informatika, Institut Teknologi Bandung. 2009

[4]     Penyejajaran Sekuens. (2015, December 21^st). Retrieved from https://id.wikipedia.org/wiki/Bioinformatika#Penyejajaran_sekuens