A Multi-Objective Optimization Framework for Multiple Sequence Alignment with Metaheuristics

Abstract

The alignment of more than two biological sequences is a widely used technique in a number of areas of computational biology. However, finding an optimal alignment has been shown to be an NP-complete optimization problem. Furthermore, Multiple Sequence Alignment (MSA) can be formulated according to more than one score function, leading to multi-objective formulations of this problem. Due to these reasons, metaheuristics have been proposed to deal with MSA problems. In this paper, we present jMetalMSA, an Open Source software tool for solving MSA problems with multi-objective metaheuristics. Our motivation here is to offer to the scientific community in computational biology, a platform including state-of-the-art optimization algorithms aimed at solving different formulations of the MSA. We describe the main features of jMetalMSA, including the metaheuristics and scores that are currently available. In addition, we show a working example for illustration purposes.