Comparing multi-objective metaheuristics for solving a three-objective formulation of multiple sequence alignment

摘要

Abstract Multiple sequence alignment (MSA) is an optimization problem consisting in finding the best alignment of more than two biological sequences according to a number of scores or objectives. In this paper, we consider a three-objective formulation of MSA, which includes the STRIKE score, the percentage of aligned columns, and the percentage of non-gap symbols. The two last objectives introduce many plateaus in the search space, thus increasing the complexity of the problem. By taking as benchmark the BAliBASE data set, we carry out a rigorous comparative study by using four multi-objective metaheuristics, including the classical NSGA-II evolutionary algorithm and the more recent ones MOCell, GWASF-GA, and NSGA-III. Our study concludes that NSGA-II provides the best overall performance.