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), creating phylogenetic tree, and metagenome fragments binning. The simplest algorithm in MSA is Star Algorithm. This algorithm consists of aligning all possible pairs of sequences, finding a sequence Star chosen from sequence that has maximum alignment score, and aligning all sequences refered to the sequence Star. Each of pairwise alignments is conducted using dynamic programming technique. The complexity of DNA multiple sequence alignment using dynamic programming technique is very high. The computation time is increased exponentially due to the increasing of the number and the length of DNA sequences. This research aims to accelerate computation of Star Mutiple Sequence Alignment using Message Passing Interfaces (MP/). The performance of the proposed method was evaluated by calculating speedup. Experiment was conducted using 64 sequences of 800 bp G/ycinemax- chromosome-9-881 fragments yielded by randomly cut from reference sequence of Glycine-maxchromosome- 9-881 taken from NCBI (National Center for Biotechnology Information). The results showed that the proposed technique could obtain speed up three times using five computers when aligning 64 sequences of G/ycine-max-chromosome-9-BBI fragments. Moreover, the increasing of the number of computers would significantly increase speed up of the proposed method.