DETEKSI GENOMIC REPEATS MENGGUNAKAN ALGORITMA BOYER-MOORE DENGAN APACHE SPARK STREAMING - Farhan Dhiyaa Pratama, - (2019)
Dalam satu dekade terakhir para ilmuwan harus melakukan penelitian laboratorium selama 3 tahun untuk menganalisa DNA. Salah satu kasus dari analisa DNA yang membutuhkan waktu dan tenaga dalam skala besar tersebut adalah untuk menganalisa penyakit yang disebabkan oleh pola genom yang berulang atau disebut dengan genomic repeats. Dalam menganalisa masalah genomic repeats dilakukan analisa string matching atau pattern matching dimana akan mencari sebuah pola dalam sebuah teks yang berukuran besar. Algoritma Boyer-Moore memproses pola dan membuat dua tabel, yang dikenal sebagai tabel Boyer-Moore Bad Character (bmBc) dan tabel Boyer-Moore good-suffix (bmGs). Untuk setiap karakter dalam set alfabet, tabel bad character menyimpan nilai pergeseran berdasarkan kemunculan karakter dalam pola. Algoritma ini membentuk dasar untuk beberapa algoritma pencocokan pola. Untuk itu, penelitian ini membuat sebuah model komputasi untuk mendapatkan pola genom yang berulang atau genomic repeats secara cepat dan efektif dengan memodifikasi dan mengimplementasikan algoritma Boyer-Moore pada Big Data Platform yaitu Apache Spark Streaming. Hasil penelitian ini menunjukkan adanya percepatan antara penggunaan Big Data platform dengan perancangan 2 skenario. Skenario pertama yaitu penggunaan cluster dengan 4 cores dan beberapa worker node dan skenario kedua yaitu penggunaan cluster dengan 2 worker node dan beberapa jumlah core. Penelitian ini juga membuktikan bahwa model komputasi yang dibangun menunjukkan adanya percepatan terhadap penelitian terdahulu dengan menggunakan stand alone. In the past decade scientists have been doing laboratory research for 3 years to analyze DNA. One of the cases of DNA analysis that requires time and effort on a large scale is to analyze diseases caused by repetitive genomic patterns or called genomic repeats. In analyzing the problem of genomic repeats an analysis of string matching or pattern matching is carried out which will look for a pattern in a large text. The Boyer-Moore algorithm processes patterns and creates two tables, known as the Boyer-Moore Bad Character (bmBc) table and the Boyer-Moore good-suffix (bmGs) table. For each character in the alphabet set, bad character tables store shift values based on the appearance of characters in the pattern. This algorithm forms the basis for several pattern matching algorithms. For this reason, this research creates a computational model to get repetitive genomic patterns or genomic repeats quickly and effectively by modifying and implementing the Boyer- Moore algorithm on the Big Data Platform, namely Apache Spark Streaming. The results of this study indicate an acceleration between the use of Big Data platforms with the design of 2 scenarios. The first scenario is the use of clusters with 4 cores and several worker nodes and the second scenario is the use of clusters with 2 worker nodes and a number of cores. This study also proves that the computational model that was built shows the acceleration of previous research using stand alone.