Binary Particle Swarm Optimization Algorithm with Mutation for Multiple Sequence Alignment

Multiple sequence alignment (MSA) is a fundamental and challenging problem in the analysis of biologic sequence. The MSA problem is hard to be solved directly, for it always results in exponential complexity with the scale of the problem. In this paper, we propose mutation-based binary particle swarm optimization (M-BPSO) for MSA solving. In the proposed M-BPSO algorithm, BPSO algorithm is conducted to provide alignments. Thereafter, mutation operator is performed to move out of local optima and speed up convergence. From simulation results of nucleic acid and amino acid sequences, it is shown that the proposed M-BPSO algorithm has superior performance when compared to other existing algorithms. Furthermore, this algorithm can be used quickly and efficiently for smaller and medium size sequences.