Akselerasi Global Pairwise Alignment Dengan Skema Partisi Blocked Column-Wise Pada Sistem Memori Terdistribusi

Abstract

Algoritme global pairwise alignment (GPA) yang digunakan untuk menyejajarkan sepasang sekuens DNA perlu diparalelisasi untuk mempersingkat waktu eksekusi. Skema partisi berpengaruh terhadap kinerja algoritme GPA paralel mengingat algoritme ini mengadopsi metode pemrograman dinamis. Penelitian ini mempercepat algoritme GPA menggunakan skema partisi blocked column-wise pada sistem memori terdistribusi. Pararelisasi algoritme GPA dilakukan dengan model pemrograman message-passing menggunakan standar message passing interface (MPI). Parameter panjang sekuens yang digunakan bervariasi dari 1000 bp sampai paling panjang 30 000 bp. Hasil yang diperoleh menunjukkan speedup menggunakan 2, 3, dan 4 buah PC berturut-turut adalah 1.79, 2.58, dan 3.37 untuk panjang sekuens 30 000 bp. Sedangkan efisiensi menggunakan jumlah PC dan panjang sekuens yang sama berturut-turut mencapai 89.32%, 85.97%, dan 84.19%. Algoritme GPA paralel yang dikembangkan menunjukkan skalabilitas.