ANALISIS PERBANDINGAN ALGORITMA PENCARIAN STRING BOYER-MOORE DAN KNUTH-MORRIS-PRATT PADA PENCARIAN ENZIM RESTRIKSI

Abstract

Pencocokan string merupakan masalah yang hampir ditemukan dalam kegiatan sehari-hari, yaitu berhubungan dengan  text-processing. Hal ini dimulai dari permasalahan sederhana sampai pada permasalahan yang kompleks.

Pencocokan string fokus pada pencarian satu atau lebih pola, semua kehadiran pola (lebih umum disebut pattern) dalam sebuah teks. Masalah dalam algoritma pencarian adalah mencari kata yang mempunyai panjang m, yang disebut pattern, dalam sebuah teks dengan panjang n. Algoritma yang digunakan yaitu Boyer-Moore dan Knuth-Morris-Pratt. Boyer-moore mencocokan pola dari kanan ke kiri sedangkan Knuth-Morris-Pratt mencocokan pola dari kiri ke kanan. Dalam makalah ini akan dijelaskan mengenai cara kerja algoritma Boyer-Moore dan algoritma Knuth-Morris-Pratt dalam pencarian enzim restriksi pada sequence DNA serta analisis running time dan turn around time yang dimiliki kedua algoritma tersebut.