A novel two-level particle swarm optimization approach for efficient multiple sequence alignment

This paper presents two-level particle swarm optimization (TL-PSO) algorithm as an effective framework for providing the solution of complex natured problems. Proposed approach is employed to solve a challenging problem of bioinformatics i.e. multiple sequence alignment (MSA) of proteins. The major challenge in MSA is the increasing complexity of the problem as soon as the number of sequences increases and average pairwise sequence identity (APSI) score decreases. Proposed TLPSO-MSA firstly maximizes the matched columns in level one followed by maximization of pairwise similarities in level two at the gbest solutions of level one. TLPSO-MSA efficiently handles the premature convergence and trapping in local optima related issues. The benchmark dataset for MSA of protein sequences are extracted from BAliBASE3.0. The special features of proposed algorithm is its prediction accuracy at very lower APSI scores. Proposed approach significantly outperforms the compared state-of-art competitive algorithms i.e. ALIGNER, MUSCLE, T-Coffee, MAFFT, ClustalW, DIALIGN-TX, ProbAlign and standard PSO algorithm. The claim is supported by the statistical significance testing using one way ANOVA followed by Bonferroni post-hoc analysis.