Multiple Sequence Alignment with Multiobjective Metaheuristics. A Comparative Study

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.     

Multiple sequence alignment using the Hidden Markov Model trained by an improved quantum-behaved particle swarm optimization

Multiple sequence alignment (MSA) is an NP-complete and important problem in bioinformatics. For MSA, Hidden Markov Models (HMMs) are known to be powerful tools. However, the training of HMMs is computationally hard so that metaheuristic methods such as simulated annealing (SA), evolutionary algorithms (EAs) and particle swarm optimization (PSO), have been employed to tackle the training problem. In this paper, quantum-behaved particle swarm optimization (QPSO), a variant of PSO, is analyzed mathematically firstly, and then an improved version is proposed to train the HMMs for MSA. The proposed method, called diversity-maintained QPSO (DMQPO), is based on the analysis of QPSO and integrates a diversity control strategy into QPSO to enhance the global search ability of the particle swarm. To evaluate the performance of the proposed method, we use DMQPSO, QPSO and other algorithms to train the HMMs for MSA on three benchmark datasets. The experiment results show that the HMMs trained with DMQPSO and QPSO yield better alignments for the benchmark datasets than other most commonly used HMM training methods such as Baum–Welch and PSO.     

Multiple Sequence Alignment with Evolutionary Computation

In this paper we provide a brief review of current work in the area of multiple sequence alignment (MSA) for DNA and protein sequences using evolutionary computation (EC). We detail the strengths and weaknesses of EC techniques for MSA. In addition, we present two novel approaches for inferring MSA using genetic algorithms. Our first novel approach utilizes a GA to evolve an optimal guide tree in a progressive alignment algorithm and serves as an alternative to the more traditional heuristic techniques such as neighbor-joining. The second novel approach facilitates the optimization of a consensus sequence with a GA using a vertically scalable encoding scheme in which the number of iterations needed to find the optimal solution is approximately the same regardless the number of sequences being aligned. We compare both of our novel approaches to the popular progressive alignment program Clustal W. Experiments have confirmed that EC constitutes an attractive and promising alternative to traditional heuristic algorithms for MSA.     

Multiobjective evolutionary algorithms for electric power dispatch problem

The potential and effectiveness of the newly developed Pareto-based multiobjective evolutionary algorithms (MOEA) for solving a real-world power system multiobjective nonlinear optimization problem are comprehensively discussed and evaluated in this paper. Specifically, nondominated sorting genetic algorithm, niched Pareto genetic algorithm, and strength Pareto evolutionary algorithm (SPEA) have been developed and successfully applied to an environmental/economic electric power dispatch problem. A new procedure for quality measure is proposed in this paper in order to evaluate different techniques. A feasibility check procedure has been developed and superimposed on MOEA to restrict the search to the feasible region of the problem space. A hierarchical clustering algorithm is also imposed to provide the power system operator with a representative and manageable Pareto-optimal set. Moreover, an approach based on fuzzy set theory is developed to extract one of the Pareto-optimal solutions as the best compromise one. These multiobjective evolutionary algorithms have been individually examined and applied to the standard IEEE 30-bus six-generator test system. Several optimization runs have been carried out on different cases of problem complexity. The results of MOEA have been compared to those reported in the literature. The results confirm the potential and effectiveness of MOEA compared to the traditional multiobjective optimization techniques. In addition, the results demonstrate the superiority of the SPEA as a promising multiobjective evolutionary algorithm to solve different power system multiobjective optimization problems.     

On the design of high-performance algorithms for aligning multiple protein sequences on mesh-based multiprocessor architectures

In this paper, we address the problem of multiple sequence alignment (MSA) for handling very large number of proteins sequences on mesh-based multiprocessor architectures. As the problem has been conclusively shown to be computationally complex, we employ divisible load paradigm (also, referred to as divisible load theory, DLT) to handle such large number of sequences. We design an efficient computational engine that is capable of conducting MSAs by exploiting the underlying parallelism embedded in the computational steps of multiple sequence algorithms. Specifically, we consider the standard Smith–Waterman (SW) algorithm in our implementation, however, our approach is by no means restrictive to SW class of algorithms alone. The treatment used in this paper is generic to a class of similar dynamic programming problems. Our approach is recursive in the sense that the quality of solutions can be refined continuously till an acceptable level of quality is achieved. After first phase of computation, we design a heuristic scheme that renders the final solution for MSA. We conduct rigorous simulation experiments using several hundreds of homologous protein sequences derived from the Rattus Norvegicus and Mus Musculus databases of olfactory receptors. We quantify the performance based on speed-up metric. We compare our algorithms to serial or single machine processing approaches. We testify our findings by comparing with conventional equal load partitioning (ELP) strategy that is commonly used in the parallel processing literature. Based on our extensive simulation study, we observe that DLT paradigm offers an excellent speed-up characteristics and provides avenues for its use in several other biological sequence processing related problem. This study is a first time attempt in using the DLT paradigm to devise efficient strategies to handle large scale multiple protein sequence alignment problem on mesh-based multiprocessor systems.     

Combining convergence and diversity in evolutionary multiobjective optimization

Over the past few years, the research on evolutionary algorithms has demonstrated their niche in solving multiobjective optimization problems, where the goal is to find a number of Pareto-optimal solutions in a single simulation run. Many studies have depicted different ways evolutionary algorithms can progress towards the Pareto-optimal set with a widely spread distribution of solutions. However, none of the multiobjective evolutionary algorithms (MOEAs) has a proof of convergence to the true Pareto-optimal solutions with a wide diversity among the solutions. In this paper, we discuss why a number of earlier MOEAs do not have such properties. Based on the concept of epsilon-dominance, new archiving strategies are proposed that overcome this fundamental problem and provably lead to MOEAs that have both the desired convergence and distribution properties. A number of modifications to the baseline algorithm are also suggested. The concept of epsilon-dominance introduced in this paper is practical and should make the proposed algorithms useful to researchers and practitioners alike.     

Performance evaluation of evolutionary multiobjective optimization algorithms for multiobjective fuzzy genetics-based machine learning

Recently, evolutionary multiobjective optimization (EMO) algorithms have been utilized for the design of accurate and interpretable fuzzy rule-based systems. This research area is often referred to as multiobjective genetic fuzzy systems (MoGFS), where EMO algorithms are used to search for non-dominated fuzzy rule-based systems with respect to their accuracy and interpretability. In this paper, we examine the ability of EMO algorithms to efficiently search for Pareto optimal or near Pareto optimal fuzzy rule-based systems for classification problems. We use NSGA-II (elitist non-dominated sorting genetic algorithm), its variants, and MOEA/D (multiobjective evolutionary algorithm based on decomposition) in our multiobjective fuzzy genetics-based machine learning (MoFGBML) algorithm. Classification performance of obtained fuzzy rule-based systems by each EMO algorithm is evaluated for training data and test data under various settings of the available computation load and the granularity of fuzzy partitions. Experimental results in this paper suggest that reported classification performance of MoGFS in the literature can be further improved using more computation load, more efficient EMO algorithms, and/or more antecedent fuzzy sets from finer fuzzy partitions.     

A review of multiobjective test problems and a scalable test problem toolkit

When attempting to better understand the strengths and weaknesses of an algorithm, it is important to have a strong understanding of the problem at hand. This is true for the field of multiobjective evolutionary algorithms (EAs) as it is for any other field. Many of the multiobjective test problems employed in the EA literature have not been rigorously analyzed, which makes it difficult to draw accurate conclusions about the strengths and weaknesses of the algorithms tested on them. In this paper, we systematically review and analyze many problems from the EA literature, each belonging to the important class of real-valued, unconstrained, multiobjective test problems. To support this, we first introduce a set of test problem criteria, which are in turn supported by a set of definitions. Our analysis of test problems highlights a number of areas requiring attention. Not only are many test problems poorly constructed but also the important class of nonseparable problems, particularly nonseparable multimodal problems, is poorly represented. Motivated by these findings, we present a flexible toolkit for constructing well-designed test problems. We also present empirical results demonstrating how the toolkit can be used to test an optimizer in ways that existing test suites do not.     

Multiobjective optimization using population-based extremal optimization

In recent years, a general-purpose local-search heuristic method called Extremal Optimization (EO) has been successfully applied in some NP-hard combinatorial optimization problems. In this paper, we present a novel Pareto-based algorithm, which can be regarded as an extension of EO, to solve multiobjective optimization problems. The proposed method, called Multiobjective Population-based Extremal Optimization (MOPEO), is validated by using five benchmark functions and metrics taken from the standard literature on multiobjective evolutionary optimization. The experimental results demonstrate that MOPEO is competitive with the state-of-the-art multiobjective evolutionary algorithms. Thus MOPEO can be considered as a viable alternative to solve multiobjective optimization problems.     

An Evolutionary Approach to Multiobjective Clustering

The framework of multiobjective optimization is used to tackle the unsupervised learning problem, data clustering, following a formulation first proposed in the statistics literature. The conceptual advantages of the multiobjective formulation are discussed and an evolutionary approach to the problem is developed. The resulting algorithm, multiobjective clustering with automatic k-determination, is compared with a number of well-established single-objective clustering algorithms, a modern ensemble technique, and two methods of model selection. The experiments demonstrate that the conceptual advantages of multiobjective clustering translate into practical and scalable performance benefits     

Comparing multiobjective swarm intelligence metaheuristics for DNA motif discovery

In recent years, a huge number of biological problems have been successfully addressed through computational techniques, among all these computational techniques we highlight metaheuristics. Also, most of these biological problems are directly related to genomic, studying the microorganisms, plants, and animals genomes. In this work, we solve a DNA sequence analysis problem called Motif Discovery Problem (MDP) by using two novel algorithms based on swarm intelligence: Artificial Bee Colony (ABC) and Gravitational Search Algorithm (GSA). To guide the pattern search to solutions that have a better biological relevance, we have redefined the problem formulation and incorporated several biological constraints that should be satisfied by each solution. One of the most important characteristics of the problem definition is the application of multiobjective optimization (MOO), maximizing three conflicting objectives: motif length, support, and similarity. So, we have adapted our algorithms to the multiobjective context. This paper presents an exhaustive comparison of both multiobjective proposals on instances of different nature: real instances, generic instances, and instances generated according to a Markov chain. To analyze their operations we have used several indicators and statistics, comparing their results with those obtained by standard algorithms in multiobjective computation, and by 14 well-known biological methods.     

A multiobjective swarm intelligence approach based on artificial bee colony for reliable DNA sequence design

The design of reliable DNA sequences is crucial in many engineering applications which depend on DNA-based technologies, such as nanotechnology or DNA computing. In these cases, two of the most important properties that must be controlled to obtain reliable sequences are self-assembly and self-complementary hybridization. These processes have to be restricted to avoid undesirable reactions, because in the specific case of DNA computing, undesirable reactions usually lead to incorrect computations. Therefore, it is important to design robust sets of sequences which provide efficient and reliable computations. The design of reliable DNA sequences involves heterogeneous and conflicting design criteria that do not fit traditional optimization methods. In this paper, DNA sequence design has been formulated as a multiobjective optimization problem and a novel multiobjective approach based on swarm intelligence has been proposed to solve it. Specifically, a multiobjective version of the Artificial Bee Colony metaheuristics (MO-ABC) is developed to tackle the problem. MO-ABC takes in consideration six different conflicting design criteria to generate reliable DNA sequences that can be used for bio-molecular computing. Moreover, in order to verify the effectiveness of the novel multiobjective proposal, formal comparisons with the well-known multiobjective standard NSGA-II (fast non-dominated sorting genetic algorithm) were performed. After a detailed study, results indicate that our artificial swarm intelligence approach obtains satisfactory reliable DNA sequences. Two multiobjective indicators were used in order to compare the developed algorithms: hypervolume and set coverage. Finally, other relevant works published in the literature were also studied to validate our results. To this respect the conclusion that can be drawn is that the novel approach proposed in this paper obtains very promising DNA sequences that significantly surpass other results previously published.     

Multiobjective evolutionary algorithm based on multimethod with dynamic resources allocation

In the last two decades, multiobjective optimization has become main stream and various multiobjective evolutionary algorithms (MOEAs) have been suggested in the field of evolutionary computing (EC) for solving hard combinatorial and continuous multiobjective optimization problems. Most MOEAs employ single evolutionary operators such as crossover, mutation and selection for population evolution. In this paper, we suggest a multiobjective evolutionary algorithm based on multimethods (MMTD) with dynamic resource allocation for coping with continuous multi-objective optimization problems (MOPs). The suggested algorithm employs two well known population based stochastic algorithms namely MOEA/D and NSGA-II as constituent algorithms for population evolution with a dynamic resource allocation scheme. We have examined the performance of the proposed MMTD on two different MOPs test suites: the widely used ZDT problems and the recently formulated test instances for the special session on MOEAs competition of the 2009 IEEE congress on evolutionary computation (CEC’09). Experimental results obtained by the suggested MMTD are more promising than those of some state-of-the-art MOEAs in terms of the inverted generational distance (IGD)-metric on most test problems.     

Performance analysis of computational approaches to solve Multiple Sequence Alignment

In the biotechnology field, the deployment of the Multiple Sequence Alignment (MSA) problem, which is a high performance computing demanding process, is one of the new challenges to address on the new parallel systems. The aim of this problem is to find similar regions on biological sequences. Furthermore, the goal of MSA applications is to align as much sequences as possible with a level of quality that makes the alignment biologically meaningful. An efficiency study of different MSA implementations, based on T-Coffee (one of the most used MSA aligners), has been performed in order to find new optimizations that may improve the average execution time on multi-core systems. We found that the current parallel implementations have some performance issues, affecting negatively the scalability of the process. Finally, the proposed implementation based on the usage of threads in conjunction with a message-passing library is presented, with the aim to optimize the execution of the MSA problem in multi-core-based clusters.     

Multiobjective evolutionary algorithms: a comparative case studyand the strength Pareto approach

Evolutionary algorithms (EAs) are often well-suited for optimization problems involving several, often conflicting objectives. Since 1985, various evolutionary approaches to multiobjective optimization have been developed that are capable of searching for multiple solutions concurrently in a single run. However, the few comparative studies of different methods presented up to now remain mostly qualitative and are often restricted to a few approaches. In this paper, four multiobjective EAs are compared quantitatively where an extended 0/1 knapsack problem is taken as a basis. Furthermore, we introduce a new evolutionary approach to multicriteria optimization, the strength Pareto EA (SPEA), that combines several features of previous multiobjective EAs in a unique manner. It is characterized by (a) storing nondominated solutions externally in a second, continuously updated population, (b) evaluating an individual's fitness dependent on the number of external nondominated points that dominate it, (c) preserving population diversity using the Pareto dominance relationship, and (d) incorporating a clustering procedure in order to reduce the nondominated set without destroying its characteristics. The proof-of-principle results obtained on two artificial problems as well as a larger problem, the synthesis of a digital hardware-software multiprocessor system, suggest that SPEA can be very effective in sampling from along the entire Pareto-optimal front and distributing the generated solutions over the tradeoff surface. Moreover, SPEA clearly outperforms the other four multiobjective EAs on the 0/1 knapsack problem     

Designing a parallel cloud based comparative genomics workflow to improve phylogenetic analyses

Over the last years, comparative genomics analyses have become more compute-intensive due to the explosive number of available genome sequences. Comparative genomics analysis is an important a prioristep for experiments in various bioinformatics domains. This analysis can be used to enhance the performance and quality of experiments in areas such as evolution and phylogeny. A common phylogenetic analysis makes extensive use of Multiple Sequence Alignment (MSA) in the construction of phylogenetic trees, which are used to infer evolutionary relationships between homologous genes. Each phylogenetic analysis aims at exploring several different MSA methods to verify which execution produces trees with the best quality. This phylogenetic exploration may run during weeks, even when executed in High Performance Computing (HPC) environments. Although there are many approaches that model and parallelize phylogenetic analysis as scientific workflows, exploring all MSA methods becomes a complex and expensive task to be performed. If scientists determine a priorithe most adequate MSA method to use in the phylogenetic analysis, it would save time, and, in some cases, financial resources. Comparative genomics analyses play an important role in optimizing phylogenetic analysis workflows. In this paper, we extend the SciHmm scientific workflow, aimed at determining the most suitable MSA method, to use it in a phylogenetic analysis. SciHmm uses SciCumulus, a cloud workflow execution engine, for parallel execution. Experimental results show that using SciHmm considerably reduces the total execution time of the phylogenetic analysis (up to 80%). Experiments also show that trees built with the MSA program elected by using SciHmm presented more quality than the remaining, as expected. In addition, the parallel execution of SciHmm shows that this kind of bioinformatics workflow has an excellent cost/benefit when executed in cloud environments.     

Multiple sequence alignment with affine gap by using multi-objective genetic algorithm

Multiple sequence alignment is of central importance to bioinformatics and computational biology. Although a large number of algorithms for computing a multiple sequence alignment have been designed, the efficient computation of highly accurate and statistically significant multiple alignments is still a challenge. In this paper, we propose an efficient method by using multi-objective genetic algorithm (MSAGMOGA) to discover optimal alignments with affine gap in multiple sequence data. The main advantage of our approach is that a large number of tradeoff (i.e., non-dominated) alignments can be obtained by a single run with respect to conflicting objectives: affine gap penalty minimization and similarity and support maximization. To the best of our knowledge, this is the first effort with three objectives in this direction. The proposed method can be applied to any data set with a sequential character. Furthermore, it allows any choice of similarity measures for finding alignments. By analyzing the obtained optimal alignments, the decision maker can understand the tradeoff between the objectives. We compared our method with the three well-known multiple sequence alignment methods, MUSCLE, SAGA and MSA-GA. As the first of them is a progressive method, and the other two are based on evolutionary algorithms. Experiments on the BAliBASE 2.0 database were conducted and the results confirm that MSAGMOGA obtains the results with better accuracy statistical significance compared with the three well-known methods in aligning multiple sequence alignment with affine gap. The proposed method also finds solutions faster than the other evolutionary approaches mentioned above.     

Parallel Genomic Alignments on the Cell Broadband Engine

Genomic alignments, as a means to uncover evolutionary relationships among organisms, are a fundamental tool in computational biology. There is considerable recent interest in using the Cell Broadband Engine, a heterogeneous multicore chip that provides high performance, for biological applications. However, work in genomic alignments so far has been limited to computing optimal alignment scores using quadratic space for the basic global/local alignment problem. In this paper, we present a comprehensive study of developing alignment algorithms on the Cell, exploiting its thread and data level parallelism features. First, we develop a parallel implementation on the Cell that computes optimal alignments and adopts Hirschberg's linear space technique. The former is essential, as merely computing optimal alignment scores is not useful, while the latter is needed to permit alignments of longer sequences. We then present Cell implementations of two advanced alignment techniques-spliced alignments and syntenic alignments. Spliced alignments are useful in aligning mRNA sequences with corresponding genomic sequences to uncover the gene structure. Syntenic alignments are used to discover conserved exons and other sequences between long genomic sequences from different organisms. We present experimental results for these three types of alignments on 16 Synergistic Processing Elements of the IBM QS20 dual-Cell blade system.     

The balance between proximity and diversity in multiobjective evolutionary algorithms

Over the last decade, a variety of evolutionary algorithms (EAs) have been proposed for solving multiobjective optimization problems. Especially more recent multiobjective evolutionary algorithms (MOEAs) have been shown to be efficient and superior to earlier approaches. An important question however is whether we can expect such improvements to converge onto a specific efficient MOEA that behaves best on a large variety of problems. In this paper, we argue that the development of new MOEAs cannot converge onto a single new most efficient MOEA because the performance of MOEAs shows characteristics of multiobjective problems. While we point out the most important aspects for designing competent MOEAs in this paper, we also indicate the inherent multiobjective tradeoff in multiobjective optimization between proximity and diversity preservation. We discuss the impact of this tradeoff on the concepts and design of exploration and exploitation operators. We also present a general framework for competent MOEAs and show how current state-of-the-art MOEAs can be obtained by making choices within this framework. Furthermore, we show an example of how we can separate nondomination selection pressure from diversity preservation selection pressure and discuss the impact of changing the ratio between these components.     

一种求解MSA问题的自适应遗传算法

多序列比对(MSA)在生物信息学研究中占有重要地位，MSA问题是一个典型的NP问题，遗传算法是求解NP完全问题的一种有效方法。文章针对MSA问题，提出了一种新型自适应遗传算法，根据群体的多样性自适应调节变异概率，有效消除了算法中的欺骗性条件，使用突变算子来确保算法的搜索能力。整个算法模拟了自然界进化的周期性，较好的解决了群体的多样性和收敛深度的矛盾。算法的分析和测试表明，该算法是有效的。