Efficient Two-Level Swarm Intelligence Approach for Multiple Sequence Alignment

keywords: Particle swarm optimization, multiple sequence alignment, average pairwise sequence identity, time complexity, scoring schemes
This paper proposes two-level particle swarm optimization (TL-PSO), an efficient PSO variant that addresses two levels of optimization problem. Level one works on optimizing dimension for entire swarm, whereas level two works for optimizing each particle's position. The issue addressed here is one of the most challenging multiple sequence alignment (MSA) problem. TL-PSO deals with the arduous task of determination of exact sequence length with most suitable gap positions in MSA. The two levels considered here are: to obtain optimal sequence length in level one and to attain optimum gap positions for maximal alignment score in level two. The performance of TL-PSO has been assessed through a comparative study with two kinds of benchmark dataset of DNA and RNA. The efficiency of the proposed approach is evaluated with four popular scoring schemes at specific parameters. TL-PSO alignments are compared with four PSO variants, i.e. S-PSO, M-PSO, ED-MPSO and CPSO-S_k, and two leading alignment software, i.e. ClustalW and T-Coffee, at different alignment scores. Hence obtained results prove the competence of TL-PSO at accuracy aspects and conclude better score scheme.
mathematics subject classification 2000: 68T10, 92B20
reference: Vol. 35, 2016, No. 4, pp. 963–985