Cellular Automata-Based PSO Algorithm for Aligning Multiple Molecular Sequences

In Bioinformatics, sequence analysis is the basic important concept that provides information for structural and functional analysis. Multiple Sequence Alignment (MSA) is a keystone problem in the sequence analysis that is used for constructing phylogenetic tree, finding motif, gene expression, etc. Basically, all biological computation issues are NP-complete problems. In this paper, a novel approach using Cellular Automata (CA) and Particle Swarm Optimization (PSO) techniques are proposed for MSA problem. Both of these techniques handle NP-complete problems very skillfully. For experimental analysis, the BaliBASE benchmark dataset and two scoring functions Sum of Pairs (SP) and Total Column (TC) are considered in this paper for calculating the similarity among the sequences. Using the Wilcoxon matched pair signed rank test the significance of the proposed algorithm (PSOCA) is explained. This algorithm is compared with PSO, genetic algorithm and the state-of-the-art techniques. The results show that the PSOCA approach yields better performance than other state-of-the-art algorithms.