Algoritma Needleman-Wunsch dalam Menentukan Tingkat Kemiripan Urutan DNA Rusa Timor (Cervus timorensis) dan Rusa Merah (Cervus elaphus)

Hibban Kholiq; Mamika Ujianita Romdhini; Marliadi Susanto

doi:10.29303/emj.v3i2.65

Algoritma Needleman-Wunsch dalam Menentukan Tingkat Kemiripan Urutan DNA Rusa Timor (Cervus timorensis) dan Rusa Merah (Cervus elaphus)

Hibban Kholiq, Mamika Ujianita Romdhini, Marliadi Susanto

Abstract

Sequence alignment is a basic method in sequence analysis. This method is used to determine the similaritiy level of DNA sequences. The Needleman-Wunsch algorithm is an algorithm that can be used to solve the problem of sequence alignment. This research shows that the relation T (i, j) used in the Needleman-Wunsch algorithm is a function where T: (ℕ₀ ℕ₀) → ℤ. The function T (i, j) is a recursive function. Moreover, DNA sequence data used are DNA sequences from the Timor Deer, which are the identities of the provinces of West Nusa Tenggara and Red Deer, which are typical deer from the European continent as a comparison. The DNA sequence data was obtained from BLAST (Basic Local Alignment Search Tool). Based on the alignment, the most optimal alignment is obtained by forming 666 base pairs sequences with 322 matches, 230 missmatches and 114 gaps, meaning that the two DNA sequences have a 48% similarity (322/666).

Keywords

DNA; Sequence Alignment; Needleman-Wunsch Algorithm; Dynamic Programming; Recursive Function; Similarities

Full Text:

PDF

References

Aminah, Aidawayati, R., Kreanajaya, A., 2013, Model Antrean Pesawat Terbang di Bandar Udara Internasional Hasanuddin Makassar, Jurnal Matematika,Statistika&Komputasi Volume I : 11.

Bu’ulölö, I. C., Simamora, N., Tampubolon, S., Pinem, A., 2010, Sequence Alignment Menggunakan Algoritma Smith Waterman, Seminar Nasional Politeknik Batam, Sumatera Utara 2010 Volume 2 No. 2.

Khairunnisa, A., 2014, Matematika Dasar, Jakarta: PT Rajagrafindo Persada.

Kusuma, W. A., 2019, Sequence Alignment, Multiple Sequence Alignment, dan Pencarian Homologi, MIPANet School Series, Bogor, 11-13 Januari 2019.

Lokawati, H., 2016, Program Dinamis untuk Menyelesaikan Sequence Alignment, http://docplayer.info, diunduh jam 14.32 WITA, tanggal 24/10/2019.

Malendes, M. A., Bunyamin, H., 2017, Perbandingan Needleman-Wunsch dan Lempel-Ziv dalam Teknik Global Sequence Alignment: Keunggulan Faktorisasi Sempurna, Jurnal Teknik Informatika dan Sistem Informasi Volume 3 No. 1 : 57-68.

Munir, Rinaldi., 2010, Matematika Diskrit Revisi Keempat, Bandung: Informatika.

Ratnadewi, Prijono, A., Hendrianto, H., Pasaribu, N. T., Hasugian, M. J., 2016, Matematika Teknik untuk Perguruan Tinggi, Bandung: Rekayasa Sains.

Satra, R., Fuad, M., Hestriyandi, H., Iqbal, M., Iqbal, M., 2015, Analisis Performa Algoritma Needleman-Wunsch (NW) Urutanial pada Raspberry Pi, Seminar Nasional Riset Ilmu Komputer, Makassar, 3 April 2015.

Siagian, P., 1987, Penelitian Operasional : Teori dan Praktek, Jakarta : Universitas Indonesia Press.

Sukiman., 2006, Logika Himpunan, Yogyakarta: Hanggar Kreator.

Supranto, J., 1998, Pengantar Matriks, Jakarta: PT Rineka Cipta.

Torres, A., Cabada, A., Nieto, J.J., 2003, An Exact Formula for the Number of Alignments Between Two DNA Sequences, Taylor & Francis Health Sciences Volume - : 1-4.

Wikipedia, Asam deoksiribonukleat(https://id.wikipedia.org), diunduh jam 14.20 WITA, tanggal 28/03/2019.

Wikipedia, Bioinformatika(https://id.wikipedia.org), diunduh jam 14.32 WITA, tanggal 28/03/2019.

Zen, M. R. F., Putri, S. W., Rasyid, M. F., 2006, Penerapan Algoritma Needlman-Wunsch sebagai Salah Satu Implementasi Program Dinamis pada Penjajaran DNA dan Protein, http://informatika.stei.itb.ac.id , diunduh jam 15.00 WITA, tanggal 25/05/2019.

DOI: https://doi.org/10.29303/emj.v3i2.65