Using traveling salesman problem algorithms for evolutionary tree construction

MOTIVATION: The construction of evolutionary trees is one of the major problems in computational biology, mainly due to its complexity. RESULTS: We present a new tree construction method that constructs a tree with minimum score for a given set of sequences, where the score is the amount of evolution measured in PAM distances. To do this, the problem of tree construction is reduced to the Traveling Salesman Problem (TSP). The input for the TSP algorithm are the pairwise distances of the sequences and the output is a circular tour through the optimal, unknown tree plus the minimum score of the tree. The circular order and the score can be used to construct the topology of the optimal tree. Our method can be used for any scoring function that correlates to the amount of changes along the branches of an evolutionary tree, for instance it could also be used for parsimony scores, but it cannot be used for least squares fit of distances. A TSP solution reduces the space of all possible trees to 2n. Using this order, we can guarantee that we reconstruct a correct evolutionary tree if the absolute value of the error for each distance measurement is smaller than f2.gif" BORDER="0">, where f3.gif" BORDER="0">is the length of the shortest edge in the tree. For data sets with large errors, a dynamic programming approach is used to reconstruct the tree. Finally simulations and experiments with real data are shown.     

Learning to cooperate in solving the traveling salesman problem

A cooperative team of agents may perform many tasks better than single agents. The question is how cooperation among self-interested agents should be achieved. It is important that, while we encourage cooperation among agents in a team, we maintain autonomy of individual agents as much as possible, so as to maintain flexibility and generality. This paper presents an approach based on bidding utilizing reinforcement values acquired through reinforcement learning. We tested and analyzed this approach and demonstrated that a team indeed performed better than the best single agent as well as the average of single agents.     

An efficient approach to the travelling salesman problem using self-organizing maps

This paper presents an approach to the well-known Travelling Salesman Problem (TSP) using Self-Organizing Maps (SOM). The SOM algorithm has interesting topological information about its neurons configuration on cartesian space, which can be used to solve optimization problems. Aspects of initialization, parameters adaptation, and complexity analysis of the proposed SOM based algorithm are discussed. The results show an average deviation of 3.7% from the optimal tour length for a set of 12 TSP instances.     

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.     

A traveling salesman approach for predicting protein functions

Background  

Protein-protein interaction information can be used to predict unknown protein functions and to help study biological pathways.     

Theoretical analysis of two ACO approaches for the traveling salesman problem

Bioinspired algorithms, such as evolutionary algorithms and ant colony optimization, are widely used for different combinatorial optimization problems. These algorithms rely heavily on the use of randomness and are hard to understand from a theoretical point of view. This paper contributes to the theoretical analysis of ant colony optimization and studies this type of algorithm on one of the most prominent combinatorial optimization problems, namely the traveling salesperson problem (TSP). We present a new construction graph and show that it has a stronger local property than one commonly used for constructing solutions of the TSP. The rigorous runtime analysis for two ant colony optimization algorithms, based on these two construction procedures, shows that they lead to good approximation in expected polynomial time on random instances. Furthermore, we point out in which situations our algorithms get trapped in local optima and show where the use of the right amount of heuristic information is provably beneficial.     

Estimation-based ant colony optimization and local search for the probabilistic traveling salesman problem

The use of ant colony optimization for solving stochastic optimization problems has received a significant amount of attention in recent years. In this paper, we present a study of enhanced ant colony optimization algorithms for tackling a stochastic optimization problem, the probabilistic traveling salesman problem. In particular, we propose an empirical estimation approach to evaluate the cost of the solutions constructed by the ants. Moreover, we use a recent estimation-based iterative improvement algorithm as a local search. Experimental results on a large number of problem instances show that the proposed ant colony optimization algorithms outperform the current best algorithm tailored to solve the given problem, which also happened to be an ant colony optimization algorithm. As a consequence, we have obtained a new state-of-the-art ant colony optimization algorithm for the probabilistic traveling salesman problem.     

Optimal foraging and the traveling salesman

Optimal foraging models are examined that assume animals forage for discrete point resources on a plane and attempt to minimize their travel distance between resources. This problem is similar to the well-known traveling salesman problem: A salesman must choose the shortest path from his home office to all cities on his itinerary and back to his home office again. The traveling salesman problem is in a class of enigmatic problems, called NP-complete, which can be so difficult to solve that animals might be incapable of finding the best solution. Two major results of this analysis are: (1) The simple foraging strategy of always moving to the closest resource site does surprisingly well. More sophisticated strategies of “looking ahead” a small number of steps, choosing the shortest path, then taking a step, do worse if all the resource sites are visited, but do slightly better (less than 10%) if not all the resource sites are visited. (2) Short cyclical foraging routes resulted when resources were allowed to renew. This is suggested as an alternative explanation for “trap-lining” in animals that forage for discrete, widely separated resources.     

Genetic algorithms for the traveling salesman problem based on a heuristic crossover operation

We apply strategies inspired by natural evolution to a classical example of discrete optimization problems, the traveling salesman problem. Our algorithms are based on a new knowledge-augmented crossover operation. Even if we use only this operation in the reproduction process, we get quite good results. The most obvious faults of the solutions can be eliminated and the results can further be improved by allowing for a simple form of mutation. If each crossover is followed by an affordable local optimization, we get the optimum solution for a 318-town problem, probably the optimum solutions for several different 100-town problems, and very nearly optimum solutions for 350-town and 1000-town problems. A new strategy for the choice of parents considerably speeds up the convergence of the latter method.     

A developmental approach to the problem of variation in evolutionary rates

Certain general features are widely recognized in evolution, one of which is the variability in the rate at which morphological characters evolve and taxa are replaced by others. Although some rate-variability in evolution no doubt arises because of different rates of ecological change, it is proposed that some of the variability also arises from developmental, rather than ecological, sources. A theory is outlined whereby early-acting genes influencing the course of development evolve more slowly, but have individually larger effects, than genes affecting development at a later stage in the life-cycle. The erratic course of morphological evolution that results is illustrated by computer simulation. It is suggested that the applicability of the theory is restricted to long-term evolution and that variability in the rate of evolution over shorter periods may be of an entirely different nature.     

An efficient harris hawk optimization algorithm for solving the travelling salesman problem

Cluster Computing - Travelling Salesman Problem (TSP) is an Np-Hard problem, for which various solutions have been offered so far. Using the Harris Hawk Optimization (HHO) algorithm, this paper...     

Solving traveling salesman problems with DNA molecules encoding numerical values

We introduce a DNA encoding method to represent numerical values and a biased molecular algorithm based on the thermodynamic properties of DNA. DNA strands are designed to encode real values by variation of their melting temperatures. The thermodynamic properties of DNA are used for effective local search of optimal solutions using biochemical techniques, such as denaturation temperature gradient polymerase chain reaction and temperature gradient gel electrophoresis. The proposed method was successfully applied to the traveling salesman problem, an instance of optimization problems on weighted graphs. This work extends the capability of DNA computing to solving numerical optimization problems, which is contrasted with other DNA computing methods focusing on logical problem solving.     

Amoeba-based computing for traveling salesman problem: Long-term correlations between spatially separated individual cells of Physarum polycephalum

A single-celled, multi-nucleated amoeboid organism, a plasmodium of the true slime mold Physarum polycephalum, can perform sophisticated computing by exhibiting complex spatiotemporal oscillatory dynamics while deforming its amorphous body. We previously devised an “amoeba-based computer (ABC)” to quantitatively evaluate the optimization capability of the amoeboid organism in searching for a solution to the traveling salesman problem (TSP) under optical feedback control. In ABC, the organism changes its shape to find a high quality solution (a relatively shorter TSP route) by alternately expanding and contracting its pseudopod-like branches that exhibit local photoavoidance behavior. The quality of the solution serves as a measure of the optimality of which the organism maximizes its global body area (nutrient absorption) while minimizing the risk of being illuminated (exposure to aversive stimuli). ABC found a high quality solution for the 8-city TSP with a high probability. However, it remains unclear whether intracellular communication among the branches of the organism is essential for computing. In this study, we conducted a series of control experiments using two individual cells (two single-celled organisms) to perform parallel searches in the absence of intercellular communication. We found that ABC drastically lost its ability to find a solution when it used two independent individuals. However, interestingly, when two individuals were prepared by dividing one individual, they found a solution for a few tens of minutes. That is, the two divided individuals remained correlated even though they were spatially separated. These results suggest the presence of a long-term memory in the intrinsic dynamics of this organism and its significance in performing sophisticated computing.     

An evolutionary approach to enzyme kinetics: Optimization of ordered mechanisms

A theoretical investigation is presented which allows the calculation of rate constants and phenomenological parameters in states of maximal reaction rates for unbranched enzymic reactions. The analysis is based on the assumption that an increase in reaction rates was an important characteristic of the evolution of the kinetic properties of enzymes. The corresponding nonlinear optimization problem is solved taking into account the constraint that the rate constants of the elementary processes do not exceed certain upper limits. One-substrate-one-product reactions with two, three and four steps are treated in detail. Generalizations concern ordered uni-uni-reactions involving an arbitrary number of elementary steps. It could be shown that depending on the substrate and product concentrations different types of solutions can be found which are classified according to the number of rate constants assuming in the optimal state submaximal values. A general rule is derived concerning the number of possible solutions of the given optimization problem. For high values of the equilibrium constant one solution always applies to a very large range of the concentrations of the reactants. This solution is characterized by maximal values of the rate constants of all forward reactions and by non-maximal values of the rate constants of all backward reactions. Optimal kinetic parameters of ordered enzymic mechanisms with two substrates and one product (bi-uni-mechanisms) are calculated for the first time. Depending on the substrate and product concentrations a complete set of solutions is found. In all cases studied the model predicts a matching of the concentrations of the reactants and the corresponding Michaelis constants, which is in good accordance with the experimental data. It is discussed how the model can be applied to the calculation of the optimal kinetic design of real enzymes.     

Transitions and transversions in evolutionary descent: An approach to understanding

Summary In this paper I lay a quantitative theoretical groundwork for understanding the proportions of the possible types of base substitutions observed between 12 genes sharing a common ancestor and isolated from extant species. The experimentally observed types of base substitution between two sequenced genes do not give a direct measure of the types of base substitutions that occur during evolutionary descent. However, by use of a statistical assemblage of these observations, we can recover, without the assumption of parsimony, the conditional base substitution probabilities that determine this descent. Three methods—direct count, regression, and informational entropy maximization—are described by which these probabilities can be estimated from experimental data. The methods are complementary in that each is most useful for somewhat different types of experimental data. These methods are used to study the ratio of transversions to transitions during gene divergence. Though this ratio is not constant during divergence, it does approach a stable limiting value that in principle can vary from zero, corresponding to 100% transition differences, to infinity, corresponding to 0% transition differences. In practice the limiting ratio tends to hover around a value of two, which is expected on a random basis. However, base substitution pathways that are very nonrandom also may lead to a limiting ratio of exactly two, so that such a value is not diagnostic for random pathways. The limiting ratio can be directly calculated from a knowledge of the twelve conditional probabilities for each type of base substitution, or from a knowledge of the equilibrium base composition of the DNAs compared. An expression is given for this calculation. Fifteen years ago Jean Derancourt, Andrew Lebor and Emile Zuckerkandl (1967), analyzing the amino acid sequence of globin chains coded by nuclear genes, made the original observation that the proportion of transition differences decreases with increasing evolutionary time. Recently Brown et al. (1982) and Brown and Simpson (1982) have reported a decrease in the observed proportion of transition differences in mitochondrial DNA with increasing evolutionary divergence. The conditions that must be satisfied for this type of behavior to occur at stable base composition and with stable base substitution probabilities are defined. Multiple substitutionsper se do not lead to a decrease in transition differences with increasing evolutionary divergence.     

State-space search strategies gleaned from animal behavior: a traveling salesman experiment

A widespread search strategy employed by predators in both vertebrate and invertebrate phyla is the well-known area-restricted search strategy. The generality, simplicity, and effectiveness of this strategy have made it emerge many times during the course of natural selection. In this work, an artificial intelligence state-space search procedure is developed using search guidelines gleaned from the foraging behavior of predators. This procedure, which we call predatory search, has been implemented on a NP-Hard combinatorial problem: the traveling salesman problem. Numerical results are presented for a limited set of benchmark problems, and area-restricted search seems to be effective: We have been able to find the optimal solution to, among others, a 400-city Manhattan problem. Received: 9 July 1997 / Accepted in revised form: 24 November 1997     

A population-based evolutionary search approach to the multiple minima problem in de novo protein structure prediction

Background

Elucidating the native structure of a protein molecule from its sequence of amino acids, a problem known as de novo structure prediction, is a long standing challenge in computational structural biology. Difficulties in silico arise due to the high dimensionality of the protein conformational space and the ruggedness of the associated energy surface. The issue of multiple minima is a particularly troublesome hallmark of energy surfaces probed with current energy functions. In contrast to the true energy surface, these surfaces are weakly-funneled and rich in comparably deep minima populated by non-native structures. For this reason, many algorithms seek to be inclusive and obtain a broad view of the low-energy regions through an ensemble of low-energy (decoy) conformations. Conformational diversity in this ensemble is key to increasing the likelihood that the native structure has been captured.

Methods

We propose an evolutionary search approach to address the multiple-minima problem in decoy sampling for de novo structure prediction. Two population-based evolutionary search algorithms are presented that follow the basic approach of treating conformations as individuals in an evolving population. Coarse graining and molecular fragment replacement are used to efficiently obtain protein-like child conformations from parents. Potential energy is used both to bias parent selection and determine which subset of parents and children will be retained in the evolving population. The effect on the decoy ensemble of sampling minima directly is measured by additionally mapping a conformation to its nearest local minimum before considering it for retainment. The resulting memetic algorithm thus evolves not just a population of conformations but a population of local minima.

Results and conclusions

Results show that both algorithms are effective in terms of sampling conformations in proximity of the known native structure. The additional minimization is shown to be key to enhancing sampling capability and obtaining a diverse ensemble of decoy conformations, circumventing premature convergence to sub-optimal regions in the conformational space, and approaching the native structure with proximity that is comparable to state-of-the-art decoy sampling methods. The results are shown to be robust and valid when using two representative state-of-the-art coarse-grained energy functions.