Accelerating Computation of DNA Multiple Sequence Alignment in Distributed Environment

Abstract

Multiple sequence alignment (MSA) is a technique for finding similarity in many sequences. This technique is very important to support many Bioinformatics task such as identifying Single Nucleotide Polymorphism (SNP) and metagenome fragments binning. The simplest algorithm in MSA is Star Algorithm. The complexity of DNA multiple sequence alignment using dynamic programming technique is very high. This research aims to accelerate computation of Star Mutiple Sequence Alignment using Message Passing Interfaces (MPI). The performance of the proposed method was evaluated by calculating speedup. Experiment was conducted using 64 sequences of 800 bp Glycine-max-chromosome-9-BBI fragments yielded by randomly cut from reference sequence of Glycine-max-chromosome-9-BBI taken from NCBI (National Center for Biotechnology Information). The results showed that the proposed technique could obtain speedup three times using five computers when aligning 64 sequences of Glycine-max-chromosome-9-BBI fragments.  Moreover, the increasing of the number of computers would significantly increased speedup of the proposed.

http://dx.doi.org/10.11591/telkomnika.v12i12.6572