Abstract
Algoritma Needleman-Wunsch telah banyak digunakan untuk melakukan penjajaran sekuen protein. Algoritma ini merupakan algoritma untuk penjajaran sekuen global yang dapat memberikan hasil optimal. Pada penelitian ini dilakukan modifikasi pada algoritma Needleman-Wunsch yang bertujuan dapat mempercepat waktu komputasi dan mengurangi kompleksitas algoritma Needleman-Wunsch. Cara modifikasinya adalah dengan mengisi sebagian daerah matriks penjajaran yang telah ditandai. Hasil akhir penjajaran akan dihitung apakah kedua sekuen yang disejajarkan mirip atau tidak mirip dengan menggunakan kurva HSSP (Homology-derived Secondary Structure of Proteins). Pada 215 sekuen protein albumin pada manusia, menggunakan skema linear dengan parameter match 1, mismatch -1 dan gap -11 algoritma ini memberikan hasil kemiripan sebesar 99.99% dan berjalan lebih cepat sebanyak 24.43%. Sedangkan menggunakan skema affine dengan parameter matriks substitusi BLOSUM62, gap opening 14 dan gap extension 1 algoritma ini memberikan hasil kemiripan sebesar 98.35% dan berjalan 32.24% lebih cepat. Kompleksitas ruang dan waktu pengisian matriks dengan menggunakan algoritma Needleman-Wunsch yang telah dimodifikasi adalah O(N), lebih sederhana dibandingkan algoritma Needleman-Wunsch yang asli O(MN).