Search

Motivation: Multiple sequence alignment (MSA) is an NP-complete optimization problem found in computational biology, where the time complexity of finding an optimal alignment raises exponentially along with the number of sequences and their lengths. Additionally, to assess the quality of a MSA, a number of objectives can be taken into account, such as maximizing the sum-of-pairs, maximizing the totally conserved columns, minimizing the number of gaps, or maximizing structural information based scores such as STRIKE. An approach to deal with MSA problems is to use multi-objective metaheuristics, which are non-exact stochastic optimization methods that can produce high quality solutions to complex problems having two or more objectives to be optimized at the same time. Our motivation is to provide a multi-objective metaheuristic for MSA that can run in parallel taking advantage of multi-core-based computers. Results: The software tool we propose, called M2Align (Multi-objective Multiple Sequence Alignment), is a parallel and more efficient version of the three-objective optimizer for sequence alignments MO-SAStrE, able of reducing the algorithm computing time by exploiting the computing capabilities of common multi-core CPU clusters. Our performance evaluation over datasets of the benchmark BAliBASE (v3.0) shows that significant time reductions can be achieved by using up to 20 cores. Even in sequential executions, M2Align is faster than MO-SAStrE, thanks to the encoding method used for the alignments. [ABSTRACT FROM AUTHOR]

Multiple sequence alignment (MSA) plays a core role in most bioinformatics studies and provides a framework for the analysis of evolution in biological systems. The MSA problem consists in finding an optimal alignment of three or more sequences of nucleotides or amino acids. Different scores have been defined to assess the quality of MSA solutions, so the problem can be formulated as a multiobjective optimization problem. The number of proposals focused on this approach in the literature is scarce, and most of the works take as base algorithm the NSGA-II metaheuristic. So, there is a lack of a study involving a set of representative multiobjective metaheuristics to deal with this complex problem. Our main goal in this paper is to carry out such study. We propose a biobjective formulation for the MSA and perform an exhaustive comparative study of six multiobjective algorithms. We have considered a number of problems taken from the benchmark BAliBASE (v3.0). Our experiments reveal that the classic NSGA-II algorithm and MOCell, a cellular metaheuristic, provide the best overall performance. [ABSTRACT FROM AUTHOR]

Molecular docking is a hard optimization problem that has been tackled in the past with metaheuristics, demonstrating new and challenging results when looking for one objective: the minimum binding energy. However, only a few papers can be found in the literature that deal with this problem by means of a multi-objective approach, and no experimental comparisons have been made in order to clarify which of them has the best overall performance. In this paper, we use and compare, for the first time, a set of representative multi-objective optimization algorithms applied to solve complex molecular docking problems. The approach followed is focused on optimizing the intermolecular and intramolecular energies as two main objectives to minimize. Specifically, these algorithms are: two variants of the non-dominated sorting genetic algorithm II (NSGA-II), speed modulation multi-objective particle swarm optimization (SMPSO), third evolution step of generalized differential evolution (GDE3), multi-objective evolutionary algorithm based on decomposition (MOEA/D) and S-metric evolutionary multi-objective optimization (SMS-EMOA). We assess the performance of the algorithms by applying quality indicators intended to measure convergence and the diversity of the generated Pareto front approximations. We carry out a comparison with another reference mono-objective algorithm in the problem domain (Lamarckian genetic algorithm (LGA) provided by the AutoDock tool). Furthermore, the ligand binding site and molecular interactions of computed solutions are analyzed, showing promising results for the multi-objective approaches. In addition, a case study of application for aeroplysinin-1 is performed, showing the effectiveness of our multi-objective approach in drug discovery. [ABSTRACT FROM AUTHOR]

The main objective of the molecular docking problem is to find a conformation between a small molecule (ligand) and a receptor molecule with minimum binding energy. The quality of the docking score depends on two factors: the scoring function and the search method being used to find the lowest binding energy solution. In this context, AutoDock 4.2 is a popular C++ software package in the bioinformatics community providing both elements, including two genetic algorithms, one of them endowed with a local search strategy. This paper principally focuses on the search techniques for solving the docking problem. In using the AutoDock 4.2 scoring function, the approach in this study is twofold. On the one hand, a number of four metaheuristic techniques are analyzed within an extensive set of docking problems, looking for the best technique according to the quality of the binding energy solutions. These techniques are thoroughly evaluated and also compared with popular well-known docking algorithms in AutoDock 4.2. The metaheuristics selected are: generational and a steady-state Genetic Algorithm, Differential Evolution, and Particle Swarm Optimization. On the other hand, a C++ version of the jMetal optimization framework has been integrated inside AutoDock 4.2, so that all the algorithms included in jMetal are readily available to solve docking problems. The experiments reveal that Differential Evolution obtains the best overall results, even outperforming other existing algorithms specifically designed for molecular docking. [ABSTRACT FROM AUTHOR]

This paper describes jMetalPy, an object-oriented Python-based framework for multi-objective optimization with metaheuristic techniques. Building upon our experiences with the well-known jMetal framework, we have developed a new multi-objective optimization software platform aiming not only at replicating the former one in a different programming language, but also at taking advantage of the full feature set of Python, including its facilities for fast prototyping and the large amount of available libraries for data processing, data analysis, data visualization, and high-performance computing. As a result, jMetalPy provides an environment for solving multi-objective optimization problems focused not only on traditional metaheuristics, but also on techniques supporting preference articulation, constrained and dynamic problems, along with a rich set of features related to the automatic generation of statistical data from the results generated, as well as the real-time and interactive visualization of the Pareto front approximations produced by the algorithms. jMetalPy offers additionally support for parallel computing in multicore and cluster systems. We include some use cases to explore the main features of jMetalPy and to illustrate how to work with it. [ABSTRACT FROM AUTHOR]

• A semantic approach is proposed to inject problem domain knowledge in optimization. • A top-level ontology is developed to represent users preferences and constraints. • The semantic model is implemented and integrated with jMetal algorithmic library. • The proposal is validated on multi-objective optimization problems TSP and RND. • Domain experts are able to semantically annotate required knowledge in optimization. In the field of complex problem optimization with metaheuristics, semantics has been used for modeling different aspects, such as: problem characterization, parameters, decision-maker's preferences, or algorithms. However, there is a lack of approaches where ontologies are applied in a direct way into the optimization process, with the aim of enhancing it by allowing the systematic incorporation of additional domain knowledge. This is due to the high level of abstraction of ontologies, which makes them difficult to be mapped into the code implementing the problems and/or the specific operators of metaheuristics. In this paper, we present a strategy to inject domain knowledge (by reusing existing ontologies or creating a new one) into a problem implementation that will be optimized using a metaheuristic. Thus, this approach based on accepted ontologies enables building and exploiting complex computing systems in optimization problems. We describe a methodology to automatically induce user choices (taken from the ontology) into the problem implementations provided by the jMetal optimization framework. With the aim of illustrating our proposal, we focus on the urban domain. Concretely, we start from defining an ontology representing the domain semantics for a city (e.g., building, bridges, point of interest, routes, etc.) that allows defining a-priori preferences by a decision maker in a standard, reusable, and formal (logic-based) way. We validate our proposal with several instances of two use cases, consisting in bi-objective formulations of the Traveling Salesman Problem (TSP) and the Radio Network Design problem (RND), both in the context of an urban scenario. The results of the experiments conducted show how the semantic specification of domain constraints are effectively mapped into feasible solutions of the tackled TSP and RND scenarios. This proposal aims at representing a step forward towards the automatic modeling and adaptation of optimization problems guided by semantics, where the annotation of a human expert can be now considered during the optimization process. [ABSTRACT FROM AUTHOR]