A Chance and Control-Based Multi-Population Genetic Algorithm for Solving Large-Scale Multiple Sequence Alignment Problem

Multiple Sequence Alignment (MSA) is a fundamental challenge in bioinformatics, forming the basis for addressing numerous computational biology problems, e.g., protein structure prediction and phylogenetic modeling. Evolutionary computation (EC) has been used to deal with the MSA due to its remarkable ability to unearth optimal or near-optimal solutions and various EC-based MSA methods have been proposed. However, the accuracy of existing EC-based MSA methods can be further improved by leveraging a novel evolutionary framework and designing evolutionary operators that align with the unique characteristics of MSA. Moreover, as the length and number of sequences increase, the MSA problem scales up, making it challenging for existing EC-based methods to achieve high accuracy within a reasonable timeframe. In this article, we propose a chance and control-based multi-population genetic algorithm (CC-MPGA), which incorporates a novel multi-population framework with genetic algorithm (GA). Moreover, according to the characteristics of MSA problems, the chance-based crossover operator and control-based mutation operator are designed to boost the accuracy. The proposed CC-MPGA is tested on well-known benchmark Balibase and large-scale benchmark ExtHomfam and compared with diverse MSA approaches. Experimental results show the superiority of CC-MPGA with a good balance of accuracy and speed, indicating the effectiveness and efficiency of CC-MPGA on large-scale MSA problems.