Implementasi Dan Analisis Bit-parallelism Untuk Mengefisienkan Komputasi Dynamic Programming

Abstract

Terdapat kebutuhan analisis biologi dengan melakukan pencarian similaritas pada sequence biologi (RNA, DNA, protein). Pencarian similaritas dalam permasalahan ilmu komputer adalah permasalahan string matching. String matching pada kebutuhan analisis biologi bisa dilakukan dengan membandingkan pasangan string atau sequence biologi (pairwise sequence alignment) atau membandingkan kelompok sequence biologi (multiple sequence alignment). Algoritma utama dalam pairwise alignment ataupun multiple sequence alignment adalah Dynamic programming (DP). Bit-parallelism atau Bit-Vector merupakan salah satu algoritma yang dikembangkan dari algoritma DP, yang mengadaptasi cara kerja pemrosesan word di dalam sistem komputer. Word merupakan unit yang terdiri dari kumpulan data biner. Bit-parallelism melakukan transformasi unit komputasi pada DP matrix menjadi unitunit word. Dalam penelitian ini telah diimplementasikan algoritma Bit-parallelism dan dibandingkan dengan algoritma DP Matrix dan diteliti efek efisiensi bit-parallelism jika diterapkan pada suatu lingkungan komputasi tertentu. Hasil dari penelitian ini adalah bit-parallelism memiliki waktu yang lebih cepat dibandingkan dengan DP Matrix dan mendapatkan efisiensi 98% lebih baik. Kata Kunci : Pencocokan kata, Bit-Parallelism, Dynamic Programming Matrix.