Phylogenetic diversity and the greedy algorithm

Given a phylogenetic tree with leaves labeled by a collection of species, and with weighted edges, the "phylogenetic diversity" of any subset of the species is the sum of the edge weights of the minimal subtree connecting the species. This measure is relevant in biodiversity conservation where one may wish to compare different subsets of species according to how much evolutionary variation they encompass. In this note we show that phylogenetic diversity has an attractive mathematical property that ensures that we can solve the following problem easily by the greedy algorithm: find a subset of the species of any given size k of maximal phylogenetic diversity. We also describe an extension of this result that also allows weights to be assigned to species.     

Residue-rotamer-reduction algorithm for the protein side-chain conformation problem

MOTIVATION: The protein side-chain conformation problem is a central problem in proteomics with wide applications in protein structure prediction and design. Computational complexity results show that the problem is hard to solve. Yet, instances from realistic applications are large and demand fast and reliable algorithms. RESULTS: We propose a new global optimization algorithm, which for the first time integrates residue reduction and rotamer reduction techniques previously developed for the protein side-chain conformation problem. We show that the proposed approach simplifies dramatically the topology of the underlining residue graph. Computations show that our algorithm solves problems using only 1-10% of the time required by the mixed-integer linear programming approach available in the literature. In addition, on a set of hard side-chain conformation problems, our algorithm runs 2-78 times faster than SCWRL 3.0, which is widely used for solving these problems. AVAILABILITY: The implementation is available as an online server at http://eudoxus.scs.uiuc.edu/r3.html     

New learning automata based algorithms for adaptation of backpropagation algorithm parameters

One popular learning algorithm for feedforward neural networks is the backpropagation (BP) algorithm which includes parameters, learning rate (eta), momentum factor (alpha) and steepness parameter (lambda). The appropriate selections of these parameters have large effects on the convergence of the algorithm. Many techniques that adaptively adjust these parameters have been developed to increase speed of convergence. In this paper, we shall present several classes of learning automata based solutions to the problem of adaptation of BP algorithm parameters. By interconnection of learning automata to the feedforward neural networks, we use learning automata scheme for adjusting the parameters eta, alpha, and lambda based on the observation of random response of the neural networks. One of the important aspects of the proposed schemes is its ability to escape from local minima with high possibility during the training period. The feasibility of proposed methods is shown through simulations on several problems.     

Backpropagation algorithm adaptation parameters using learning automata

Despite of the many successful applications of backpropagation for training multi-layer neural networks, it has many drawbocks. For complex problems it may require a long time to train the networks, and it may not train at all. Long training time can be the result of the non-optimal parameters. It is not easy to choose appropriate value of the parameters for a particular problem. In this paper, by interconnection of fixed structure learning automata (FSLA) to the feedforward neural networks, we apply learning automata (LA) scheme for adjusting these parameters based on the observation of random response of neural networks. The main motivation in using learning automata as an adaptation algorithm is to use its capability of global optimization when dealing with multi-modal surface. The feasibility of proposed method is shown through simulations on three learning problems: exclusive-or, encoding problem, and digit recognition. The simulation results show that the adaptation of these parameters using this method not only increases the convergence rate of learning but it increases the likelihood of escaping from the local minima.     

Genetic algorithm with alphabet optimization

 In recent years the genetic algorithm (GA) was used successfully to solve many optimization problems. One of the most difficult questions of applying GA to a particular problem is that of coding. In this paper a scheme is derived to optimize one aspect of the coding in an automatic fashion. This is done by using a high cardinality alphabet and optimizing the meaning of the letters. The scheme is especially well suited in cases where a number of similar problems need to be solved. The use of the scheme is demonstrated with such a group of problems: the simplified problem of navigating a ‘robot’ in a ‘room.’ It is shown that for the sample problem family the proposed algorithm is superior to the canonical GA. Received: 26 August 1994/Accepted in revised form: 13 January 1995     

A local training and pruning approach for neural networks

The training of neural networks using the extended Kalman filter (EKF) algorithm is plagued by the drawback of high computational complexity and storage requirement that may become prohibitive even for networks of moderate size. In this paper, we present a local EKF training and pruning approach that can solve this problem. In particular, the by-products obtained along with the local EKF training can be utilized to measure the importance of the network weights. Comparing with the original global approach, the proposed local EKF training and pruning approach results in a much lower computational complexity and storage requirement. Hence, it is more practical in solving real world problems. The performance of the proposed algorithm is demonstrated on one medium- and one large-scale problems, namely, sunspot data prediction and handwritten digit recognition.     

Solving the SAT problem using a DNA computing algorithm based on ligase chain reaction

A new DNA computing algorithm based on a ligase chain reaction is demonstrated to solve an SAT problem. The proposed DNA algorithm can solve an n-variable m-clause SAT problem in m steps and the computation time required is O (3m+n). Instead of generating the full-solution DNA library, we start with an empty test tube and then generate solutions that partially satisfy the SAT formula. These partial solutions are then extended step by step by the ligation of new variables using Taq DNA ligase. Correct strands are amplified and false strands are pruned by a ligase chain reaction (LCR) as soon as they fail to satisfy the conditions. If we score and sort the clauses, we can use this algorithm to markedly reduce the number of DNA strands required throughout the computing process. In a computer simulation, the maximum number of DNA strands required was 2(0.48n) when n=50, and the exponent ratio varied inversely with the number of variables n and the clause/variable ratio m/n. This algorithm is highly space-efficient and error-tolerant compared to conventional brute-force searching, and thus can be scaled-up to solve large and hard SAT problems.     

Predatory search algorithm with restriction of solution distance

A variety of methods and algorithms have been developed to solve NP-Hard problems in recent decades. In this paper, we are concerned with a relatively new algorithm based on animal behavioral adaptability and evolutionary computation, namely predatory search. When first introduced, the algorithm was implemented with restrictions based on solution cost as a simplification of distance adopted by search-intensive predators. Our research concentrates on exploring the possibility of using distance to restrict search area. Based on the research of Boese et al. (1994), we propose a type of predatory search algorithm restricted by solution distance (particularly bond distance), and compare it with the original algorithm based on three benchmark traveling salesman problems. The results indicate that both algorithms are suitable for solving the traveling salesman problems, while our proposed algorithm either outperforms or at least matches its predecessor with respect to both the running time and the quality of solutions. In addition, further experiments suggest that there exists a certain relationship between the two algorithms.     

Evaluation of a particle swarm algorithm for biomechanical optimization

Optimization is frequently employed in biomechanics research to solve system identification problems, predict human movement, or estimate muscle or other internal forces that cannot be measured directly. Unfortunately, biomechanical optimization problems often possess multiple local minima, making it difficult to find the best solution. Furthermore, convergence in gradient-based algorithms can be affected by scaling to account for design variables with different length scales or units. In this study we evaluate a recently-developed version of the particle swarm optimization (PSO) algorithm to address these problems. The algorithm's global search capabilities were investigated using a suite of difficult analytical test problems, while its scale-independent nature was proven mathematically and verified using a biomechanical test problem. For comparison, all test problems were also solved with three off-the-shelf optimization algorithms--a global genetic algorithm (GA) and multistart gradient-based sequential quadratic programming (SQP) and quasi-Newton (BFGS) algorithms. For the analytical test problems, only the PSO algorithm was successful on the majority of the problems. When compared to previously published results for the same problems, PSO was more robust than a global simulated annealing algorithm but less robust than a different, more complex genetic algorithm. For the biomechanical test problem, only the PSO algorithm was insensitive to design variable scaling, with the GA algorithm being mildly sensitive and the SQP and BFGS algorithms being highly sensitive. The proposed PSO algorithm provides a new off-the-shelf global optimization option for difficult biomechanical problems, especially those utilizing design variables with different length scales or units.     

A CLIQUE algorithm using DNA computing techniques based on closed-circle DNA sequences

DNA computing has been applied in broad fields such as graph theory, finite state problems, and combinatorial problem. DNA computing approaches are more suitable used to solve many combinatorial problems because of the vast parallelism and high-density storage. The CLIQUE algorithm is one of the gird-based clustering techniques for spatial data. It is the combinatorial problem of the density cells. Therefore we utilize DNA computing using the closed-circle DNA sequences to execute the CLIQUE algorithm for the two-dimensional data. In our study, the process of clustering becomes a parallel bio-chemical reaction and the DNA sequences representing the marked cells can be combined to form a closed-circle DNA sequences. This strategy is a new application of DNA computing. Although the strategy is only for the two-dimensional data, it provides a new idea to consider the grids to be vertexes in a graph and transform the search problem into a combinatorial problem.     

A real time learning algorithm for recurrent analog neural networks

A new learning algorithm is described for a general class of recurrent analog neural networks which ultimately settle down to a steady state. Recently, Pineda (Pineda 1987; Almeida 1987; Ikeda et al. 1988) has introduced a learning rule for the recurrent net in which the connection weights are adjusted so that the distance between the stable outputs of the current system and the desired outputs will be maximally decreased. In this method, many cycles are needed in order to get a target system. In each cycle, the recurrent net is run until it reaches a stable state. After that, the weight change is calculated by using a linearized recurrent net which receives the current error of the system as a bias input. In the new algorithm the weights are changed so that the total error of neuron outputs over the entire trajectory is minimized. The weights are adjusted in real time when the network is running. In this method, the trajectory to the target system can be controlled, whereas Pineda's algorithm only controls the position of the fixed point. The relation to the back propagation method (Hinton et al. 1986) is also discussed.     

Optimal HP configurations of proteins by combining local search with elastic net algorithm

The prediction of protein conformation from its amino-acid sequence is one of the most prominent problems in computational biology. But it is NP-hard. Here, we focus on an abstraction widely studied of this problem, the two-dimensional hydrophobic-polar protein folding problem (2D HP PFP). Mathematical optimal model of free energy of protein is established. Native conformations are often sought using stochastic sampling methods, but which are slow. The elastic net (EN) algorithm is one of fast deterministic methods as travelling salesman problem (TSP) strategies. However, it cannot be applied directly to protein folding problem, because of fundamental differences in the two types of problems. In this paper, how the 2D HP protein folding problem can be framed in terms of TSP is shown. Combination of the modified elastic net algorithm and novel local search method is adopted to solve this problem. To our knowledge, this is the first application of EN algorithm to 2D HP model. The results indicate that our approach can find more optimal conformations and is simple to implement, computationally efficient and fast.     

Optimal HP configurations of proteins by combining local search with elastic net algorithm

The prediction of protein conformation from its amino-acid sequence is one of the most prominent problems in computational biology. But it is NP-hard. Here, we focus on an abstraction widely studied of this problem, the two-dimensional hydrophobic-polar protein folding problem (2D HP PFP). Mathematical optimal model of free energy of protein is established. Native conformations are often sought using stochastic sampling methods, but which are slow. The elastic net (EN) algorithm is one of fast deterministic methods as travelling salesman problem (TSP) strategies. However, it cannot be applied directly to protein folding problem, because of fundamental differences in the two types of problems. In this paper, how the 2D HP protein folding problem can be framed in terms of TSP is shown. Combination of the modified elastic net algorithm and novel local search method is adopted to solve this problem. To our knowledge, this is the first application of EN algorithm to 2D HP model. The results indicate that our approach can find more optimal conformations and is simple to implement, computationally efficient and fast.     

A new algorithm for RNA secondary structure design

The function of many RNAs depends crucially on their structure. Therefore, the design of RNA molecules with specific structural properties has many potential applications, e.g. in the context of investigating the function of biological RNAs, of creating new ribozymes, or of designing artificial RNA nanostructures. Here, we present a new algorithm for solving the following RNA secondary structure design problem: given a secondary structure, find an RNA sequence (if any) that is predicted to fold to that structure. Unlike the (pseudoknot-free) secondary structure prediction problem, this problem appears to be hard computationally. Our new algorithm, "RNA Secondary Structure Designer (RNA-SSD)", is based on stochastic local search, a prominent general approach for solving hard combinatorial problems. A thorough empirical evaluation on computationally predicted structures of biological sequences and artificially generated RNA structures as well as on empirically modelled structures from the biological literature shows that RNA-SSD substantially out-performs the best known algorithm for this problem, RNAinverse from the Vienna RNA Package. In particular, the new algorithm is able to solve structures, consistently, for which RNAinverse is unable to find solutions. The RNA-SSD software is publically available under the name of RNA Designer at the RNASoft website (www.rnasoft.ca).     

The superior fault tolerance of artificial neural network training with a fault/noise injectionbased genetic algorithm

Artificial neural networks (ANNs) are powerful computational tools that are designed to replicate the human brain and adopted to solve a variety of problems in many different fields. Fault tolerance (FT), an important property of ANNs, ensures their reliability when significant portions of a network are lost. In this paper, a fault/noise injection-based (FIB) genetic algorithm (GA) is proposed to construct fault-tolerant ANNs. The FT performance of an FIB-GA was compared with that of a common genetic algorithm, the back-propagation algorithm, and the modification of weights algorithm. The FIB-GA showed a slower fitting speed when solving the exclusive OR (XOR) problem and the overlapping classification problem, but it significantly reduced the errors in cases of single or multiple faults in ANN weights or nodes. Further analysis revealed that the fit weights showed no correlation with the fitting errors in the ANNs constructed with the FIB-GA, suggesting a relatively even distribution of the various fitting parameters. In contrast, the output weights in the training of ANNs implemented with the use the other three algorithms demonstrated a positive correlation with the errors. Our findings therefore indicate that a combination of the fault/noise injection-based method and a GA is capable of introducing FT to ANNs and imply that the distributed ANNs demonstrate superior FT performance.     

A linear-time algorithm for the perfect phylogeny haplotyping (PPH) problem.

Since the introduction of the Perfect Phylogeny Haplotyping (PPH) Problem in RECOMB 2002 (Gusfield, 2002), the problem of finding a linear-time (deterministic, worst-case) solution for it has remained open, despite broad interest in the PPH problem and a series of papers on various aspects of it. In this paper, we solve the open problem, giving a practical, deterministic linear-time algorithm based on a simple data structure and simple operations on it. The method is straightforward to program and has been fully implemented. Simulations show that it is much faster in practice than prior nonlinear methods. The value of a linear-time solution to the PPH problem is partly conceptual and partly for use in the inner loop of algorithms for more complex problems, where the PPH problem must be solved repeatedly.     

Hierarchical genetic algorithm for near optimal feedforward neural network design

In this paper, we propose a genetic algorithm based design procedure for a multi layer feed forward neural network. A hierarchical genetic algorithm is used to evolve both the neural networks topology and weighting parameters. Compared with traditional genetic algorithm based designs for neural networks, the hierarchical approach addresses several deficiencies, including a feasibility check highlighted in literature. A multi objective cost function is used herein to optimize the performance and topology of the evolved neural network simultaneously. In the prediction of Mackey Glass chaotic time series, the networks designed by the proposed approach prove to be competitive, or even superior, to traditional learning algorithms for the multi layer Perceptron networks and radial basis function networks. Based upon the chosen cost function, a linear weight combination decision making approach has been applied to derive an approximated Pareto optimal solution set. Therefore, designing a set of neural networks can be considered as solving a two objective optimization problem.     

Density estimation using a new dimension adaptive particle swarm optimization algorithm

Current Particle Swarm Optimization (PSO) algorithms do not address problems with unknown dimensions, which arise in many applications that would benefit from the use of PSO. In this paper, we propose a new algorithm, called Dimension Adaptive Particle Swarm Optimization (DA-PSO) that can address problems with any number of dimensions. We also propose and compare three other PSO-based methods with DA-PSO. We apply our algorithms to solve the Weibull mixture model density estimation problem as an illustration. DA-PSO achieves better objective function values than other PSO-based algorithms on four simulated datasets and a real dataset. We also compare DA-PSO with the recursive Expectation-Maximization (EM) estimator, which is a non-PSO-based method, obtaining again very good results.     

Ant colony optimization for multicasting in static wireless ad-hoc networks

Nodes of wireless ad-hoc networks are generally equipped with batteries. This makes energy a scarce resource. Therefore, power consumption of network operations is critical and subject to optimization. One of the fundamental problems in ad-hoc networks is multicasting. In this work, we consider the so-called minimum energy multicast (MEM) problem in static ad-hoc networks. This problem can be stated as a combinatorial optimization problem. We develop an ant colony optimization algorithm for networks with omni-directional as well as directional antennas. The results show that our algorithm consistently outperforms existing techniques. This work was supported by grant TIN2007-66523 (FORMALISM) of the Spanish Government, and by the EU project FRONTS (FP7-ICT-2007-1) funded by the European Commission under the FET Proactive Initiative Pervasive Adaptation. In addition, Christian Blum acknowledges support from the Ramón y Cajal program of the Spanish Ministry of Science and Innovation, and Hugo Hernández acknowledges support from the Catalan Government through an FI grant.