Paralellization Multiple Sequence Alignment

Abstract

Sequence alignment (sequence alignment) is one of the problems in molecular biology that can be solved with the help of computer programs. The purpose of an alignment is to identify similarity region of sequence in Deoxyribonucleic acid (DNA), Ribonucleic acid (RNA), or protein. One of sequence alignment methods is Needleman-Wunsch which includes all sequences in its alignment. The Needleman-Wunsch method has high computational complexity with value of O(n2). Similarly, multiple sequence alignment (MSA) that processes k sequences one by one by using Star Alignment method has complexity of O(k2n2). Therefore, the main problem in MSA using Star Alignment method is computational time. However, the Star Alignment method can still obtain high accuracy. The time consuming problem faced by Star Alignment method can be solved by applying parallel computing technique implemented using multiple computers working together as a network system. This research focuses on finding a faster method to process MSA based on Star Alignment method using parallel computing. The proposed method is implemented using Message Passing Interface (MPI). The evaluation is conducted by calculating speed up. The experiment results show that the paralellization of the Star Alignment method can increase speed up 4-6 times faster than that of using single CPU.