Mathematical Model for a Parallel Sequence Alignment

Needleman – Wunsch (NW) algorithms is a dynamic method for aligning bio-sequences. The arguments against NW are its high memory demands, a relatively slower response time and difficulties in producing a load-balanced parallelization. Also, the result gives the exact answer (exact method). This research develops a mathematical model for the runtime of a parallel implementation of the NW algorithm. The main objective is to develop a tool to determine the amount of processor needed to optimize the runtime and task distribution. The proposed tool is used to create a right balance runtime and computational cost. To test the parallel model algorithm, the implementation was made in C using MPI and was ran on an Ubuntu Beowulf cluster. In conclusion, the number of processor use is directly related to the ratio between network communication speed and computation cost. The parallel implementation shows an efficient job distribution, a low memory consume and good approximation to the expected runtime.