Heuristic combinatorial optimization by simulated Darwinian evolution: a polynomial time algorithm for the Traveling Salesman Problem

A genetic algorithm simulating Darwinian evolution is proposed to yield near-optimal solutions to the Traveling Salesman Problem. Noting that Darwinian evolution is itself an optimization process, we propose a heuristic algorithm that incorporates the tenets of natural selection. The time complexity of this algorithm is equivalent to the fastest sorting scheme! Computer simulations indicate rapid convergence is maintained even with increasing problem complexity. This methodology can be adapted to tackle a host of other combinatorial problems.     

A Discrete Fruit Fly Optimization Algorithm for the Traveling Salesman Problem

The fruit fly optimization algorithm (FOA) is a newly developed bio-inspired algorithm. The continuous variant version of FOA has been proven to be a powerful evolutionary approach to determining the optima of a numerical function on a continuous definition domain. In this study, a discrete FOA (DFOA) is developed and applied to the traveling salesman problem (TSP), a common combinatorial problem. In the DFOA, the TSP tour is represented by an ordering of city indices, and the bio-inspired meta-heuristic search processes are executed with two elaborately designed main procedures: the smelling and tasting processes. In the smelling process, an effective crossover operator is used by the fruit fly group to search for the neighbors of the best-known swarm location. During the tasting process, an edge intersection elimination (EXE) operator is designed to improve the neighbors of the non-optimum food location in order to enhance the exploration performance of the DFOA. In addition, benchmark instances from the TSPLIB are classified in order to test the searching ability of the proposed algorithm. Furthermore, the effectiveness of the proposed DFOA is compared to that of other meta-heuristic algorithms. The results indicate that the proposed DFOA can be effectively used to solve TSPs, especially large-scale problems.     

Branch-and-terminate: a combinatorial optimization algorithm for protein design.

BACKGROUND: Several deterministic and stochastic combinatorial optimization algorithms have been applied to computational protein design and homology modeling. As structural targets increase in size, however, it has become necessary to find more powerful methods to address the increased combinatorial complexity. RESULTS: We present a new deterministic combinatorial search algorithm called 'Branch-and-Terminate' (B&T), which is derived from the Branch-and-Bound search method. The B&T approach is based on the construction of an efficient but very restrictive bounding expression, which is used for the search of a combinatorial tree representing the protein system. The bounding expression is used both to determine the optimal organization of the tree and to perform a highly effective pruning procedure named 'termination'. For some calculations, the B&T method rivals the current deterministic standard, dead-end elimination (DEE), sometimes finding the solution up to 21 times faster. A more significant feature of the B&T algorithm is that it can provide an efficient way to complete the optimization of problems that have been partially reduced by a DEE algorithm. CONCLUSIONS: The B&T algorithm is an effective optimization algorithm when used alone. Moreover, it can increase the problem size limit of amino acid sidechain placement calculations, such as protein design, by completing DEE optimizations that reach a point at which the DEE criteria become inefficient. Together the two algorithms make it possible to find solutions to problems that are intractable by either algorithm alone.     

Automatic Combination of Operators in a Genetic Algorithm to Solve the Traveling Salesman Problem

Genetic algorithms are powerful search methods inspired by Darwinian evolution. To date, they have been applied to the solution of many optimization problems because of the easy use of their properties and their robustness in finding good solutions to difficult problems. The good operation of genetic algorithms is due in part to its two main variation operators, namely, crossover and mutation operators. Typically, in the literature, we find the use of a single crossover and mutation operator. However, there are studies that have shown that using multi-operators produces synergy and that the operators are mutually complementary. Using multi-operators is not a simple task because which operators to use and how to combine them must be determined, which in itself is an optimization problem. In this paper, it is proposed that the task of exploring the different combinations of the crossover and mutation operators can be carried out by evolutionary computing. The crossover and mutation operators used are those typically used for solving the traveling salesman problem. The process of searching for good combinations was effective, yielding appropriate and synergic combinations of the crossover and mutation operators. The numerical results show that the use of the combination of operators obtained by evolutionary computing is better than the use of a single operator and the use of multi-operators combined in the standard way. The results were also better than those of the last operators reported in the literature.     

Beyond directed evolution: Darwinian selection as a tool for synthetic biology

Synthetic biology is an engineering approach that seeks to design and construct new biological parts, devices and systems, as well as to re-design existing components. However, rationally designed synthetic circuits may not work as expected due to the context-dependence of biological parts. Darwinian selection, the main mechanism through which evolution works, is a major force in creating biodiversity and may be a powerful tool for synthetic biology. This article reviews selection-based techniques and proposes strict Darwinian selection as an alternative approach for the identification and characterization of parts. Additionally, a strategy for fine-tuning of relatively complex circuits by coupling them to a master standard circuit is discussed.     

Research program for a search of the origin of Darwinian evolution

The search for origin of ‘life’ is made even more complicated by differing definitions of the subject matter, although a general consensus is that an appropriate definition should center on Darwinian evolution (Cleland and Chyba 2002). Within a physical approach which has been defined as a level-4 evolution (Tessera and Hoelzer 2013), one mechanism could be described showing that only three conditions are required to allow natural selection to apply to populations of different system lineages. This approach leads to a vesicle- based model with the necessary properties. Of course such a model has to be tested. Thus, after a brief presentation of the model an experimental program is proposed that implements the different steps able to show whether this new direction of the research in the field is valid and workable.     

A polynomial time algorithm for calculating the probability of a ranked gene tree given a species tree

ABSTRACT: BACKGROUND: The ancestries of genes form gene trees which do not necessarily have the same topology as the species tree due to incomplete lineage sorting. Available algorithms determining the probability of a gene tree given a species tree require exponential computational runtime. RESULTS: In this paper, we provide a polynomial time algorithm to calculate the probability of a ranked gene tree topology for a given species tree, where a ranked tree topology is a tree topology with the internal vertices being ordered. The probability of a gene tree topology can thus be calculated in polynomial time if the number of orderings of the internal vertices is a polynomial number. However, the complexity of calculating the probability of a gene tree topology with an exponential number of rankings for a given species tree remains unknown. CONCLUSIONS: Polynomial algorithms for calculating ranked gene tree probabilities may become useful in developing methodology to infer species trees based on a collection of gene trees, leading to a more accurate reconstruction of ancestral species relationships.     

Thinking about evolution: combinatorial play as a strategy for exercising scientific creativity

An enduring focus in education on how scientists formulate experiments and ‘do science’ in the laboratory has excluded a vital element of scientific practice: the creative and imaginative thinking that generates models and testable hypotheses. In this case study, final‐year biomedical sciences university students were invited to create and justify a taxonomy of selected vertebrates on the basis of their brain organisation, as part of an exercise exploring the evolution of embryonic development. While raising a number of issues surrounding the context and methods of comparative zoology, this exercise also invoked a set of cognitive processes that can neither be adequately characterised as role‐play nor critical thinking. By contrast, the act of formulating and justifying taxonomy identifies a style of creative thought that is a prerequisite for hypothesis formation. A defining characteristic of this exercise is that it engages activities that are independent of disciplinary perspective. This flexibility in approach may provide a route through to defining what qualifies as a creative teaching exercise in science.     

An ant colony optimization algorithm for phylogenetic estimation under the minimum evolution principle

Background  

Distance matrix methods constitute a major family of phylogenetic estimation methods, and the minimum evolution (ME) principle (aiming at recovering the phylogeny with shortest length) is one of the most commonly used optimality criteria for estimating phylogenetic trees. The major difficulty for its application is that the number of possible phylogenies grows exponentially with the number of taxa analyzed and the minimum evolution principle is known to belong to the -hard class of problems.     

AbDesign: An algorithm for combinatorial backbone design guided by natural conformations and sequences

Computational design of protein function has made substantial progress, generating new enzymes, binders, inhibitors, and nanomaterials not previously seen in nature. However, the ability to design new protein backbones for function—essential to exert control over all polypeptide degrees of freedom—remains a critical challenge. Most previous attempts to design new backbones computed the mainchain from scratch. Here, instead, we describe a combinatorial backbone and sequence optimization algorithm called AbDesign, which leverages the large number of sequences and experimentally determined molecular structures of antibodies to construct new antibody models, dock them against target surfaces and optimize their sequence and backbone conformation for high stability and binding affinity. We used the algorithm to produce antibody designs that target the same molecular surfaces as nine natural, high‐affinity antibodies; in five cases interface sequence identity is above 30%, and in four of those the backbone conformation at the core of the antibody binding surface is within 1 Å root‐mean square deviation from the natural antibodies. Designs recapitulate polar interaction networks observed in natural complexes, and amino acid sidechain rigidity at the designed binding surface, which is likely important for affinity and specificity, is high compared to previous design studies. In designed anti‐lysozyme antibodies, complementarity‐determining regions (CDRs) at the periphery of the interface, such as L1 and H2, show greater backbone conformation diversity than the CDRs at the core of the interface, and increase the binding surface area compared to the natural antibody, potentially enhancing affinity and specificity. Proteins 2015; 83:1385–1406. © 2015 Wiley Periodicals, Inc.     

Optimizing the search algorithm for protein engineering by directed evolution

An in silico protein model based on the Kauffman NK-landscape, where N is the number of variable positions in a protein and K is the degree of coupling between variable positions, was used to compare alternative search strategies for directed evolution. A simple genetic algorithm (GA) was used to model the performance of a standard DNA shuffling protocol. The search effectiveness of the GA was compared to that of a statistical approach called the protein sequence activity relationship (ProSAR) algorithm, which consists of two steps: model building and library design. A number of parameters were investigated and found to be important for the comparison, including the value of K, the screening size, the system noise and the number of replicates. The statistical model was found to accurately predict the measured activities for small values of the coupling between amino acids, K 相似文献   

Molecular evolution: dynamic combinatorial libraries, autocatalytic networks and the quest for molecular function

The principles of Darwinian evolution have been explored in molecular systems such as autocatalytic networks and dynamic combinatorial libraries. Molecular evolution in such systems manifests itself as ligand or receptor amplification by selection. Research efforts exploring these concepts may provide a mechanism for the identification of novel catalysts, molecular receptors and bioactive molecules.     

The "sensational" power of movement in plants: A Darwinian system for studying the evolution of behavior

Darwin's research on botany and plant physiology was a landmark attempt to integrate plant movements into a biological perspective of behavior. Since antiquity, people have sought to explain plant movements via mechanical or physiological forces, and yet they also constructed analogies between plant and animal behavior. During the Renaissance and Enlightenment, thinkers began to see that physiochemical explanations of plant movements could equally apply to animal behavior and even human thought. Darwin saw his research on plant movements as a strategic front against those who argued that his theory of evolution could not account for the acquisition of new behavioral traits. He believed that his research explained how the different forms of plant movement evolved as modified habits of circumnutation, and he presented evidence that plants might have a brain-like organ, which could have acquired various types of plant sensitivity during evolution. Upon publication of The Power of Movement in Plants, his ideas were overwhelmingly rejected by plant physiologists. Subsequently, plant biologists came to view the work as an important contribution to plant physiology and biology, but its intended contribution to the field of evolution and behavior has been largely overlooked.     

Exploring the thermostable properties of halohydrin dehalogenase from Agrobacterium radiobacter AD1 by a combinatorial directed evolution strategy

As a crucial factor for biocatalysts, protein thermostability often arises from a combination of factors that are often difficult to rationalize. In this work, the thermostable nature of halohydrin dehalogenase from Agrobacterium radiobacter AD1 (HheC) was systematically explored using a combinatorial directed evolution approach. For this, a mutagenesis library of HheC mutants was first constructed using error-prone PCR with low mutagenesis frequency. After screening approximately 2000 colonies, six mutants with eight mutation sites were obtained. Those mutation sites were subsequently combined by adopting several rounds of iterative saturation mutagenesis (ISM) approach. After four rounds of saturation mutagenesis, one best mutant ISM-4 with a 3400-fold improvement in half-life (t _1/2) inactivation at 65 °C, 18 °C increase in apparent T _m value, and 20 °C increase in optimum temperature was obtained, compared to wild-type HheC. To the best of our knowledge, the mutant represents the most thermostable HheC variant reported up to now. Moreover, the mutant was as active as wild-type enzyme for the substrate 1,3-dichloro-2-propanol, and they remained most enantioselectivity of wild-type enzyme in the kinetic resolution of rac-2-chloro-1-phenolethanol, exhibiting a great potential for industrial applications. Our structural investigation highlights that surface loop regions are hot spots for modulating the thermostability of HheC, the residues located at these regions contribute to the thermostability of HheC in a cooperative way, and protein rigidity and oligomeric interface connections contribute to the thermostability of HheC. All of these essential factors could be used for further design of an even more thermostable HheC, which, in turn, could greatly facilitate the application of the enzyme as a biocatalyst.

     

GATC: a genetic algorithm for gene tree construction under the Duplication-Transfer-Loss model of evolution

Background

Several methods have been developed for the accurate reconstruction of gene trees. Some of them use reconciliation with a species tree to correct, a posteriori, errors in gene trees inferred from multiple sequence alignments. Unfortunately the best fit to sequence information can be lost during this process.

Results

We describe GATC, a new algorithm for reconstructing a binary gene tree with branch length. GATC returns optimal solutions according to a measure combining both tree likelihood (according to sequence evolution) and a reconciliation score under the Duplication-Transfer-Loss (DTL) model. It can either be used to construct a gene tree from scratch or to correct trees infered by existing reconstruction method, making it highly flexible to various input data types. The method is based on a genetic algorithm acting on a population of trees at each step. It substantially increases the efficiency of the phylogeny space exploration, reducing the risk of falling into local minima, at a reasonable computational time. We have applied GATC to a dataset of simulated cyanobacterial phylogenies, as well as to an empirical dataset of three reference gene families, and showed that it is able to improve gene tree reconstructions compared with current state-of-the-art algorithms.

Conclusion

The proposed algorithm is able to accurately reconstruct gene trees and is highly suitable for the construction of reference trees. Our results also highlight the efficiency of multi-objective optimization algorithms for the gene tree reconstruction problem. GATC is available on Github at: https://github.com/UdeM-LBIT/GATC.

     

Cyndi: a multi-objective evolution algorithm based method for bioactive molecular conformational generation

Background  

Conformation generation is a ubiquitous problem in molecule modelling. Many applications require sampling the broad molecular conformational space or perceiving the bioactive conformers to ensure success. Numerous in silico methods have been proposed in an attempt to resolve the problem, ranging from deterministic to non-deterministic and systemic to stochastic ones. In this work, we described an efficient conformation sampling method named Cyndi, which is based on multi-objective evolution algorithm.     

ASTRO-FOLD: a combinatorial and global optimization framework for Ab initio prediction of three-dimensional structures of proteins from the amino acid sequence

The field of computational biology has been revolutionized by recent advances in genomics. The completion of a number of genome projects, including that of the human genome, has paved the way toward a variety of challenges and opportunities in bioinformatics and biological systems engineering. One of the first challenges has been the determination of the structures of proteins encoded by the individual genes. This problem, which represents the progression from sequence to structure (genomics to structural genomics), has been widely known as the structure-prediction-in-protein-folding problem. We present the development and application of ASTRO-FOLD, a novel and complete approach for the ab initio prediction of protein structures given only the amino acid sequences of the proteins. The approach exhibits many novel components and the merits of its application are examined for a suite of protein systems, including a number of targets from several critical-assessment-of-structure-prediction experiments.     

Solving a combinatorial problem via self-organizing process: An application of the Kohonen algorithm to the traveling salesman problem

We present an application of the Kohonen algorithm to the traveling salesman problem: Using only this algorithm, without energy function nor any parameter choosen ad hoc, we found good suboptimal tours. We give a neural model version of this algorithm, closer to classical neural networks. This is illustrated with various numerical examples.     

Medium optimization for the production of the aroma compound 2-phenylethanol using a genetic algorithm

Using a genetic algorithm, 13 medium constituents and the temperature were varied to improve the bioconversion of -phenylalanine ( -phe) to 2-phenylethanol (2-PE) with Kluyveromyces marxianus CBS 600. Within four generations plus an additional temperature screening, corresponding to 98 parallel experiments altogether, a maximum 2-PE concentration of 5.6 g/l, equivalent to an increase of 87% compared to the non-optimized medium was obtained. The vitamin content of the medium had to be raised significantly.