ANALISA PERBANDINGAN DAN IMPLEMENTASI ALGORITMA DNA PAIRWISE SEQUENCE ALIGNMENT NEEDLEMAN-WUNSCH DAN LEMPEL-ZIV

Mikhael Avner Malendes, Hendra Bunyamin

Abstract


Bioinformatics research is currently working on the changing of the DNA information, and marking the mutation for the DNA. For comparing DNA and finding out how two DNA can have similarities, bioinformatics using algorithms that works in global alignment and local alignment. The global alignment is comparing all the characters in sequence while the local only take a piece of characters from the alignment.  This study proposes two algorithms for processing the DNA sequence in global alignment. The akgorithms are Needleman-Wunsch and Lempel-Ziv algorithms. These algorithms work with building a scoring matrix and create an alignment based on the matrix. The experiment is conducted by testing DNA sequences randomly with the length less than 1000 characters and more than 1000 characters. Needleman-Wunsch leading with processing speed up to 1 miliseconds for less than 1000 character dataset and 42 miliseconds for more than 1000 characters dataset, while Lempel-Ziv is leading the processing speed on specific case of perfect phrase in DNA sequence.

Full Text:

PDF

References


Z. R. Yang, Machine Learning Approaches to Bioinformatics, Singapore: World Scientific Publishing Co. Pte. Ltd., 2010.

W. S. Susan Elrod, Schaum's Genetika, Jakarta: Erlangga, 2007.

J. Simarmata, Rekayasa Perangkat Lunak, Yogyakarta: Penerbit ANDI, 2010.

S. J. P. J. Z. Shanika Kuruppu, "Optimized Relative Lempel-Ziv Compression of Genomes," vol. XXXIV, pp. 1-8, 2011.

V. Likic, "The Needleman-Wunsch Algorithm for Sequence Alignment," in Bio21 Molecular Science and Biotechnology Institute, Melbourne, 2008.

R. S. Harris, Improved Pairwise Alignment Of Genomic DNA, Pennsylvania: Pennylvania State University, 2007.

D. P. A. P. Ernawati, "Implementasi Algoritma Smith-Waterman Pada Local Alignment Dalam Pencarian Kesamaan Pensejajaran Barisan DNA (Studi Kasus : DNA Tumor Wilms)," Jurnal Pseudocode, pp. 170-177, 2014.

S. J. P. Dominik Kempa, "Lempel-Ziv Factorization: Simple, Fast, Practical," Algorithm Engineering and Experiments (ALENEX), pp. 103-112, 2013.

J. C. G. C. N. L. J. L. J. F. D. B. S. C. L. Dandan Song, "Parameterized BLOSUM Matrices for Protein Alignment," Transactions on Computational Biology and Bioinformatics, vol. 12, no. 3, pp. 686-694, 2015.

A. Chan, "Stanford Project," 2004. [Online]. Available: biochem218.stanford.edu/Projects%202004.Chan.pdf.

W. H. B. R. Alex Aravind, "Pairwise sequence alignment algorithms : a survey," Association for Computing Machinery Journal, 2016.

D. Agashe, "Large-Effect Beneficial Synonymous Mutations Mediate Rapid and Parallel Adaptation in a Bacterium," Molecular Biology and Evolution, vol. 33, no. 6, pp. 1542-1553, 2016.




DOI: http://dx.doi.org/10.28932/jutisi.v3i1.568

Refbacks

  • There are currently no refbacks.


Copyright (c) 2017 Jurnal Teknik Informatika dan Sistem Informasi