SEMINAR NASIONAL MATEMATIKA DAN PENDIDIKAN MATEMATIKA UNY 2015 T–1
Pensejajaran Rantai DNA Menggunakan Algoritma Dijkstra Abduh Riski1 1
Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Jember
[email protected]
Abstrak—Deoxyribonucleic Acid atau DNA adalah asam nukleat yang berisi informasi genetik dari setiap makhluk hidup. Pensejajaran rantai DNA merupakan metode untuk mengetahui tingkat kemiripan dua rantai DNA dari makhluk hidup yang berbeda. Dengan melakukan pensejajaraan rantai DNA dapat diperoleh informasi tentang fungsi, struktur atau evolusi kedua rantai DNA yang dibandingkan. Pada proses pensejajaran rantai DNA akan diperoleh skor-skor relasi dari kedua rantai DNA. Tujuan dari metode pensejajaran rantai DNA adalah mencari rangkaian rantai DNA dengan jumlah skor yang minimal. Pada penelitian ini proses pensejajaran rantai DNA akan dilakukan menggunakan algoritma djikstra. Algoritma djikstra adalah salah satu algoritma untuk mencari lintasan terpendek pada graf berbobot. Graf berbobot yang digunakan dibangkitkan berdasarkan skor-skor relasi rantai DNA yang dibandingkan, sehingga akan diperoleh graf dengan bobot positif. Hasil penelitian menunjukkan bahwa algoritma djikstra berhasil menghasilkan lintasan terpendek yang merupakan interpretasi rangkaian rantai DNA dengan skor minimal. Kata kunci: Algoritma Dijkstra, DNA, Graf Berbobot, Pensejajaran
I.
PENDAHULUAN
Pensejajaran rantai DNA merupakan teknik untuk mengetahui kemiripan dari himpunan rantai DNA [3]. Salah satu contoh penerapan metode ini adalah untuk identifikasi korban kecelakaan pesawat terbang. Prinsip dasar dari metode pensejajaran adalah dengan membandingkan satu persatu asam amino dari sebuah rantai DNA dengan asam amino dari rantai DNA yang lain. Sehingga diperoleh sebuah himpunan perluasan rantai DNA yang berisi perluasan rantai DNA dengan skor kemiripan yang besar atau dengan skor ketidak miripan yang kecil. Proses pensejajaran untuk rantai DNA berukuran panjang membutuhkan waktu yang relatif lama, sehingga dibutuhkan metode atau algoritma agar proses pensejaran yang dilakukan menjadi cepat. Beberapa metode yang pernah digunakan untuk melakukan pensejajaran di anataranya adalah pemrograman dinamis [2] dan algoritma genetika [3]. Dalam jurnal ini akan dilakukan pensejajaran rantai DNA menggunakan algoritma dijkstra. Algoritma dijkstra adalah algoritma yang sering dikenal sebagai algortima pencarian lintasan terpendek. Dengan terlebih dahulu membangun sebuah graf berbobot dari relasi antar rantai DNA dan kemudian menerapkan algortima dijkstra pada graf yang terbentuk, sehingga diharapkan dapat diperoleh lintasan terpendek yang merepresentasikan kesejajaran dari himpunan perluasan rantai DNA. II.
METODE PENELITIAN
A. Algoritma Dijkstra Algoritma Dijkstra ditemukan oleh E. W. Dijkstra pada tahun 1959 [1], algoritma ini merupakan algortima pencarian graf untuk menyelesaikan permasalahan single-source shortest path pada sebuah graf berbobot tak-negatif. Single-source shortest path adalah permasalahan untuk mencari lintasan terpendek dari sebuah titik ke semua titik lainnya dalam sebuah graf. Tetapi algoritma ini juga dapat digunakan untuk mencari lintasan terpendek dari sebuah titik ke sebuah titik lainnya dengan menghentikan proses algoritma ketika lintasan terpendek ke titik tujuan telah ditemukan. Algoritma Dijkstra Input:
Sebuah Graf berarah atau tak-berarah berbobot dan tidak memiliki loops. Order dari adalah . Dimana titik-titiknya diberi label 1 hingga , misalnya .
Sebuah titik awal
.
171
ISBN 978-602-73403-0-5
Output:
List
List
yang berisi jarak, dimana
adalah jarak lintasan terpendek dari ke .
yang berisi titik induk, dimana
adalah induk dari , misalnya
bertetangga dengan
. 1.
;
2.
;
3.
;
4.
;
(list titik yang akan dikunjungi)
5. 6.
Cari
dimana
7.
minimal; ;
(hapus
dari )
8. 9.
Jika
then
10.
;
11. 12.
; ;
Misalkan adalah sebuah graf (atau graf berarah) dengan bobot sisi non negatif, dan misalkan adalah titik awal. Algoritma di atas terdiri dari beberapa langkah yang secara mendasar setiap langkah diperuntukkan untuk masing-masing titik di . Langkah pertama, menginisialisasi dengan buah dan memberi nilai pada . Tujuan dari pemberian nilai1adalah untuk melambangkan bilangan yang sangat besar. Dimana fungsi adalah untuk menyimpan jarak semua lintasan terpendek dari titik ke sembarang titik lainnya di , dan jarak ke dirinya sendiri adalah . Sedangkan adalah titiktitik induk yang diinisialisasi kosong dan adalah titik-titik yang akan dikunjungi yang diinisialisasi sama dengan semua titik di . Sehingga sekarang yang dipertimbangkan adalah setiap titik di , dan hapus sembarang titik yang telah dikunjungi dari . Perulangan while pada baris ke-5 terus diproses hingga semua titik telah dikunjungi. Pada baris ke-6 dipilih titik mana yang akan dikunjungi, misalkan titik yang terpilih adalah dimana minimal. Setelah titik dikunjungi, titik dihapus dari . Perulangan for pada baris ke-8 berfungsi untuk menghitung ulang jarak setiap titik yang bertetangga dengan , dimana . Sedangkan kondisi pada baris ke-9 adalah untuk merubah jarak yang telah dihitung ulang. Perintah adalah jumlah jarak s ke v dan jarak v ke u, dan jika hasil penjumlahannya kurang dari jarak dari ke , maka hasil penjumlahan tersebut dimasukkan ke dan menjadi titik induk dari . Setiap perulangan while selesai, jumlah elemen di berkurang satu persatu. Pada akhirnya akan dihasilkan dan . Sebagai ilustrasi, algoritma dijkstra akan diterapkan pada Gambar 1(a). Dengan titik awal . Proses algoritma dijkstra pada Gambar 1(a) secara berurutan ditampilkan pada Gambar 1, dengan hasil akhir dari algoritma dijkstra ditampilkan pada Gambar 1(f) dan Tabel 1, dimana setiap 2-tupel bilangan dalam setiap kolom pada Tabel 1 merupakan jarak dan titik induk dari . Dalam setiap iterasi pada algortima dijkstra, jarak dan titik induk selalu diperbaharui, dimana 2-tupel yang digaris bawahi pada setiap iterasinya merupakan titik yang akan dikunjungi. Dari Tabel 1 dapat diperoleh jalur terpendek sebagai berikut:
(1)
Sebuah lintasan dari dapat diperoleh dengan proses backtracking dimulai dari titik induknya dan titik induknya lagi hingga sampai pada .
172
kemudian ke
SEMINAR NASIONAL MATEMATIKA DAN PENDIDIKAN MATEMATIKA UNY 2015
GAMBAR 1. ILUSTRASI ALGORITMA DIJKSTRA
TABEL 1. LANGKAH ALGORITMA DIJKSTRA
Sebuah lintasan dari dapat diperoleh dengan proses backtracking dimulai dari titik induknya dan titik induknya lagi hingga sampai pada .
kemudian ke
B. Pensejajaran Rantai DNA Sebuah rantai DNA merupakan untaian yang terdiri dari kumpulan empat nukleotida yaitu adenine, cytosine, guanine dan thymine. Dimana keempat nukleotida tersebut seraca berturut-turut dilambangkan dengan ; ; dan . Sehingga sebuah rantai DNA dapat dituliskan sebagai (2) Misalkan adalah himpunan rantai DNA dan , dimana dan adalah rantai DNA yang terdiri dari . Tujuan dari pensejajaran adalah untuk memperoleh dengan bobot kemiripan besar atau ketidak miripan kecil dan merupakan himpunan perluasan rantai DNA dan yaitu dan 173
ISBN 978-602-73403-0-5
dengan panjang rantai keduanya sama. Rantai perluasan dan diperoleh dengan menambahkan “gap” yang biasa dilambangkan dengan virtual simbol “ ” sehingga dan terdiri dari . Bobot dari ditentukan menggunakan penalti skor atau juga matriks skor, misalnya matriks Hamming (3) Misalkan terdapat dua buah rantai DNA sebagai berikut (4) Dengan menggunakan penalti skor 5 jika sesuai, -3 jika tidak sesuai dan -7 jika salah satunya gap. Dengan pemrograman dinamis akan diperoleh (5) Dengan bobot minimal sebesar 1. III.
HASIL DAN PEMBAHASAN
Sebelum menerapkan algoritma dijkstra pada pensejajaran rantai DNA, haruslah diperoleh graf yang merepresentasikan hubungan antar rantai DNA dalam pensejajaran sekuens. Graf tersebut terdiri dari titiktitik yang berasal dari semua kemungkinan pasangan nukleotida dari rantai DNA dan ditambah satu titik awal dan satu titik akhir, beberapa titik dihubungkan dengan sisi yang merepresenta sikan gap seperti pada Gambar 2.
GAMBAR 2. GRAF PENSEJAJARAN
Bobot dari tiap sisi sama dengan penalti skor yang bersesuaian dengan pasangan nukleotida yang dituju. Tidak hanya itu saja, keberadaan gap juga perlu dipertimbangkan, sehingga pasangan nukleotida yang tidak mempunyai gap seperti pada Gambar 2(b) mendapat tambahan skor 0. Sedangkan pasangan nukleotida yang mempunyai gap mendapat tambahan kelipatan dari skor gap sesuai dengan urutannya, jadi semakin jauh panjang sisi maka semakin besar kelipat skor gap yang ditambahkan. Penalti skor yang digunakan dibuat sedemikian rupa sehingga pasangan rantai DNA yang sama mendapat skor yang kecil, sedangkan pasangan yang tidak sama mendapat skor yang lebih besar. Sedangkan skor gap yang biasanya digunakan nilai negatif terkecil, pada metode ini skor gap dibuat positif terbesar. Tujuannya agar semakin banyak gap yang didapat, maka semakin besar pula bobot sisi yang menghubungkannya. Karena pada dasarnya prinsip pensejajaran rantai DNA adalah untuk mendapatkan hasil pensejajaran dengan penambahan gap minimal. Perhatikan kedua rantai DNA berikut (7)
174
SEMINAR NASIONAL MATEMATIKA DAN PENDIDIKAN MATEMATIKA UNY 2015
Misalnya penalti skor yang digunakan adalah (8) Sehingga didapatkan Tabel 2 TABEL 2. SKOR RANTAI DNA
0
1
1
1
1
0
DAN
Kemudian dapat dibangun graf dari hubungan rantai DNA dan seperti pada Gambar 3. Dimana titik 1 mewakili titik awal, titik 2 mewakili pasangan nukleotida , titik 3 mewakili pasangan nukleotida , titik 4 mewakili pasangan nukleotida , begitu seterusnya hingga titik 8 mewakili titik akhir/berhenti.
GAMBAR 3. GRAF G
Bobot dari tiap sisi graf pada Gambar 3 disajikan dalam Tabel 3. TABEL 3. BOBOT SISI GRAF G
1
2
3
4
5
6
1 2 3 4 5 6 7 8
Kemudian diperoleh graf
dengan bobot-bobot sisinya seperti pada Gambar 4.
175
7
8
ISBN 978-602-73403-0-5
GAMBAR 4. GRAF BERBOBOT G
Dengan menerapkan algoritma djikstra pada graf berbobot Gambar 5,
, akan diperoleh lintasan seperti pada
GAMBAR 5. LINTASAN TERPENDEK
yang dapat juga dituliskan dengan
. Sehingga diperoleh (9)
Secara intuitif hasil tersebut adalah himpunan perluasan rantai DNA dan dengan skor minimal yang diharapkan, karena gap masuk pada rantai DNA dan berpasangan dengan nukleotida pada rantai DNA . IV.
SIMPULAN DAN SARAN
Algoritma dijkstra adalah algoritma pencarian graf untuk menentukan lintasan terpendek dari titik awal tunggal, tetapi algortim dijkstra juga dapat digunakan untuk mencari lintasan terpendek dari titik awal tunggal dan titik akhir tunggal. Algoritma dijkstra dapat diterapkan dalam pensejajaran sekuens DNA dengan terlebih dahulu membangun graf yang merepresentasikan relasi dalam himpunan Rantai DNA. Pada penelitian selanjutnya dapat dilakukan dengan mencari metode lain yang lebih baik kinerja daripada aloritma dijkstra.
DAFTAR PUSTAKA [1] [2] [3]
E.W. Dijkstra, “A Note on Two Problem in Connexion with Graphs”, Numerische Mathematik, 1, 1959, pp. 269-271. S.N. Shen and J.A. Tuszynski, Theory and Mathematical Methods for Bioformatics, Springer: Verlag Berlin Heidelberg, 2008. J. Zhang and Z. Wang, “A New Genetic Algorithm Using Gap Matrixes for Multiple Sequence Alignment”, Comm. in Comp. and Inf. Sci. 201, pp. 232-240, 2011.
176
