Komputasi Paralel Multiple Sequence Alignment menggunakan Message Passing Interface

Abstract

Multiple sequence alignment (MSA) adalah teknik untuk menemukan kesamaan dalam banyak sekuen. Teknik ini sangat penting untuk mendukung banyak tugas bioinformatika seperti mengidentifikasi single nucleotide polymorphism (SNP), membuat phylogenetic tree, dan metagenome fragments binning. Algoritma sederhana untuk MSA adalah Algoritma Star. Algoritma ini terdiri atas tiga tahap, yaitu menjajarkan semua kemungkinan pasangan sekuen, menentukan sekuen star yang dipilih dari sekuen yang memiliki nilai penjajaran maksimum, dan menjajarkan semua sekuen terhadap sekuen star. Setiap pasangan sekuen dijajarkan dengan menggunakan teknik pemrograman dinamis. Kompleksitas penjajaran sekuen DNA menggunakan teknik pemrograman dinamis mengikuti fungsi eksponensial. Waktu komputasi meningkat secara eksponensial seiring dengan meningkatnya jumlah dan panjang sekuen DNA. Penelitian ini bertujuan untuk mempercepat perhitungan MSA menggunakan message passing interface (MPI). Evaluasi kinerja dari metode yang diusulkan dilakukan dengan menghitung speedup. Percobaan dilakukan dengan menggunakan data Glycine max-kromosom-9-BBI dengan jumlah 64 sekuen yang memiliki panjang seragam, yaitu 800 base pair (bp). Sekuens ini dihasilkan dengan cara memotong secara acak sekuen referensi dari Glycine max-kromosom-9-BBI yang bersumber dari national center for biotechnology information (NCBI). Hasil penelitian menunjukkan bahwa teknik yang diusulkan mampu menghasilkan speedup sebesar tiga kali, dengan menggunakan lima komputer. Selain itu, dapat ditarik kesimpulan bahwa peningkatan jumlah komputer akan meningkatkan speedup. Kata kunci : multiple sequence alignment, message passing interfaces, komputasi paralel, DNA.