BACKGROUND: Identifying the locations of gene breakpoints between species of different taxonomic groups can provide useful insights into the underlying evolutionary processes. Given the exact locations of their genes, the breakpoints can be computed without much effort. However, often, existing gene annotations are erroneous, or only nucleotide sequences are available. Especially in mitochondrial genomes, high variations in gene orders are usually accompanied by a high degree of sequence inconsistencies. This makes accurately locating breakpoints in mitogenomic nucleotide sequences a challenging task. RESULTS: This contribution presents a novel method for detecting gene breakpoints in the nucleotide sequences of complete mitochondrial genomes, taking into account possible high substitution rates. The method is implemented in the software package DeBBI. DeBBI allows to analyze transposition- and inversion-based breakpoints independently and uses a parallel program design, allowing to make use of modern multi-processor systems. Extensive tests on synthetic data sets, covering a broad range of sequence dissimilarities and different numbers of introduced breakpoints, demonstrate DeBBI 's ability to produce accurate results. Case studies using species of various taxonomic groups further show DeBBI 's applicability to real-life data. While (some) multiple sequence alignment tools can also be used for the task at hand, we demonstrate that especially gene breaks between short, poorly conserved tRNA genes can be detected more frequently with the proposed approach. CONCLUSION: The proposed method constructs a position-annotated de-Bruijn graph of the input sequences. Using a heuristic algorithm, this graph is searched for particular structures, called bulges, which may be associated with the breakpoint locations. Despite the large size of these structures, the algorithm only requires a small number of graph traversal steps.

Dynamic multiobjective optimization problems are challenging due to their fast convergence and diversity maintenance requirements. Prediction-based evolutionary algorithms currently gain much attention for meeting these requirements. However, it is not always the case that an elaborate predictor is suitable for different problems and the quality of historical solutions is sufficient to support prediction, which limits the availability of prediction-based methods over various problems. Faced with these issues, this article proposes a knowledge learning strategy for change response in the dynamic multiobjective optimization. Unlike prediction approaches that estimate the future optima from previously obtained solutions, in the proposed strategy, we react to changes via learning from the historical search process. We introduce a method to extract the knowledge within the previous search experience. The extracted knowledge can accelerate convergence as well as introduce diversity for the optimization of the future environment. We conduct a comprehensive experiment on comparing the proposed strategy with the state-of-the-art algorithms. Results demonstrate the better performance of the proposed strategy in terms of solution quality and computational efficiency.

The two-machine permutation flow shop scheduling problem with buffer is studied for the special case that all processing times on one of the two machines are equal to a constant c. This case is interesting because it occurs in various applications, for example, when one machine is a packing machine or when materials have to be transported. Different types of buffers and buffer usage are considered. It is shown that all considered buffer flow shop problems remain NP-hard for the makespan criterion even with the restriction to equal processing times on one machine. However, the special case where the constant c is larger or smaller than all processing times on the other machine is shown to be polynomially solvable by presenting an algorithm (2BF-OPT) that calculates optimal schedules in O(nlogn) steps. Two heuristics for solving the NP-hard flow shop problems are proposed: (i) a modification of the commonly used NEH heuristic (mNEH) and (ii) an Iterated Local Search heuristic (2BF-ILS) that uses the mNEH heuristic for computing its initial solution. It is shown experimentally that the proposed 2BF-ILS heuristic obtains better results than two state-of-the-art algorithms for buffered flow shop problems from the literature and an Ant Colony Optimization algorithm. In addition, it is shown experimentally that 2BF-ILS obtains the same solution quality as the standard NEH heuristic, however, with a smaller number of function evaluations.

Gene order evolution of unichromosomal genomes, for example mitochondrial genomes, has been modelled mostly by four major types of genome rearrangements: inversions, transpositions, inverse transpositions, and tandem duplication random losses. Generalizing models that include all those rearrangements while admitting computational tractability are rare. In this paper, we study such a rearrangement model, namely the inverse tandem duplication random loss (iTDRL) model, where an iTDRL duplicates and inverts a continuous segment of a gene order followed by the random loss of one of the redundant copies of each gene. The iTDRL rearrangement has currently been proposed by several authors suggesting it to be a possible mechanisms of mitochondrial gene order evolution. We initiate the algorithmic study of this new model of genome rearrangement by proving that a shortest rearrangement scenario that transforms one given gene order into another given gene order can be obtained in quasilinear time. Furthermore, we show that the length of such a scenario, i.e., the minimum number of iTDRLs in the transformation, can be computed in linear time.

In this paper a new population update rule for population based ant colony optimization (PACO) is proposed. PACO is a well known alternative to the standard ant colony optimization algorithm. The new update rule allows to weight different parts of the solutions. PACO with the new update rule is evaluated for the example of the single machine total weighted tardiness problem (SMTWTP). This is an `NP-hard optimization problem where the aim is to schedule jobs on a single machine such that their total weighted tardiness is minimized. PACO with the new population update rule is evaluated with several benchmark instances from the OR-Library. Moreover, the impact of the weights of the jobs on the solutions in the population and on the convergence of the algorithm are analyzed experimentally. The results show that PACO with the new update rule has on average better solution quality than PACO with the standard update rule.

The preserving Genome Sorting Problem (pGSP) asks for a shortest sequence of rearrangement operations that transforms a given gene order into another given gene order by using rearrangement operations that preserve common intervals, i.e., groups of genes that form an interval in both given gene orders. The wpGSP is the weighted version of the problem were each type of rearrangement operation has a weight and a minimum weight sequence of rearrangement operations is sought. An exact algorithm - called CREx2 - is presented, which solves the wpGSP for arbitrary gene orders and the following types of rearrangement operations: inversions, transpositions, inverse transpositions, and tandem duplication random loss operations. CREx2 has a (worst case) exponential runtime, but a linear runtime for problem instances where the common intervals are organized in a linear structure. The efficiency of CREx2 and its usefulness for phylogenetic analysis is shown empirically for gene orders of fungal mitochondrial genomes.

BACKGROUND: To study the differences between two unichromosomal circular genomes, e.g., mitochondrial genomes, under the tandem duplication random loss (TDRL) rearrangement it is important to consider the whole set of potential TDRL rearrangement events that could have taken place. The reason is that for two given circular gene orders there can exist different TDRL rearrangements that transform one of the gene orders into the other. Hence, a TDRL event cannot always be reconstructed only from the knowledge of the circular gene order before a TDRL event and the circular gene order after it. RESULTS: We present the program EqualTDRL that computes and illustrates the complete set of TDRLs for pairs of circular gene orders that differ by only one TDRL. EqualTDRL considers the circularity of the given genomes and certain restrictions on the TDRL rearrangements. Examples for the latter are sequences of genes that have to be conserved during a TDRL or pairs of genes that frame intergenic regions which might represent remnants of duplicated genes. Additionally, EqualTDRL allows to determine the set of TDRLs that are minimum with respect to the number of duplicated genes. CONCLUSION: EqualTDRL supports scientists to study the complete set of TDRLs that possibly could have taken place in the evolution of mitochondrial genomes. EqualTDRL is implemented in C++ using the ggplot2 package of the open source programming language R and is freely available from http://pacosy.informatik.uni-leipzig.de/equaltdrl .

The tandem duplication random loss operation (TDRL) is an important genome rearrangement operation in metazoan mitochondrial genomes. A TDRL consists of a duplication of a contiguous set of genes in tandem followed by a random loss of one copy of each duplicated gene. This paper presents an analysis of the combinatorics of TDRLs on circular genomes, e.g., the mitochondrial genome. In particular, results on TDRLs for circular genomes and their linear representatives are established. Moreover, the distance between gene orders with respect to linear TDRLs and circular TDRLs is studied. An analysis of the available animal mitochondrial gene orders shows the practical relevance of the theoretical results.

The weighted Genome Sorting Problem (wGSP) is to find a minimum-weight sequence of rearrangement operations that transforms a given gene order into another given gene order using rearrangement operations that are associated with a predefined weight. This paper presents a polynomial sized Integer Linear Program -called GeRe-ILP- for solving the wGSP for the following three types of rearrangement operations: inversion , transposition, and inverse transposition. GeRe-ILP uses variables and constraints for gene orders of length . It is studied experimentally on simulated data how different weighting schemes influence the reconstructed scenarios. The influences of the length of the gene orders and of the size of the reconstructed scenarios on the runtime of GeRe-ILP are studied as well.

A generic scheme is proposed for designing and classifying simple probabilistic population-based optimization (SPPBO) algorithms that use principles from population-based ant colony optimization (PACO) and simplified swarm optimization (SSO) for solving combinatorial optimization problems. The scheme, called SPPBO, identifies different types of populations (or archives) and their influence on the construction of new solutions. The scheme is used to show how SSO can be adapted for solving combinatorial optimization problems and how it is related to PACO. Moreover, several new variants and combinations of these two metaheuristics are generated with the proposed scheme. An experimental study is done to evaluate and compare the influence of different population types on the optimization behavior of SPPBO algorithms, when applied to the traveling salesperson problem and the quadratic assignment problem.

In this paper we study the use of different evolutionary inheritance mechanisms for the adaptation of parameters in a multi-agent system where the agents have to solve tasks that are distributed within a dynamic environment. In the studied system the agents have to form teams to execute the tasks. Deciding which task to execute next is a multi-criteria decision problem for which the agents use different ranking schemes. Agents that have successfully executed several tasks can reproduce and pass the type of ranking scheme they have used and some corresponding parameter values to their successors. Three types of evolutionary mechanisms are compared: haploid, diploid, and haplo-diploid. The latter one is new for multi-agent systems. The focus of our simulation experiments is to study the influence of the different evolutionary mechanisms on the diversity of the agents and on the resulting efficiency of the multi-agent system for different dynamic environments.

Combinatorial optimization problems and corresponding (meta-)heuristics have received much attention in the literature. Especially, the structural or topological analysis of search landscapes is important for evaluating the applicability and the performance of search operators for a given problem. However, this analysis is often tedious and usually the focus is on one specific problem and only a few operators. We present a visual analysis method that can be applied to a wide variety of problems and search operators. The method is based on steepest descent walks and shortest distances in the search landscape. The visualization shows the search landscape as seen by the search algorithm. It supports the topological analysis as well as the comparison of search landscapes. We showcase the method by applying it to two different search operators on the TSP, the QAP, and the SMTTP. Our results show how differences between search operators manifest in the search landscapes and how conclusions about the suitability of the search operator for different optimizations can be drawn.

In this paper, we present an integer linear programming (ILP) approach, called CoRe-ILP, for finding an optimal time consistent cophylogenetic host-parasite reconciliation under the cophylogenetic event model with the events cospeciation, duplication, sorting, host switch, and failure to diverge. Instead of assuming event costs, a simplified model is used, maximizing primarily for cospeciations and secondarily minimizing host switching events. Duplications, sortings, and failure to diverge events are not explicitly scored. Different from existing event based reconciliation methods, CoRe-ILP can use (approximate) phylogenetic branch lengths for filtering possible ancestral host-parasite interactions. Experimentally, it is shown that CoRe-ILP can successfully use branch length information and performs well for biological and simulated data sets. The results of CoRe-ILP are compared with the results of the reconciliation tools Jane 4, Treemap 3b, NOTUNG 2.8 Beta, and Ranger-DTL. Algorithm CoRe-ILP is implemented using IBM ILOG CPLEX Optimizer 12.6 and is freely available from http://pacosy.informatik.uni-leipzig.de/core-ilp.

MOTIVATION: Computer-assisted studies of structure, function and evolution of viruses remains a neglected area of research. The attention of bioinformaticians to this interesting and challenging field is far from commensurate with its medical and biotechnological importance. It is telling that out of >200 talks held at ISMB 2013, the largest international bioinformatics conference, only one presentation explicitly dealt with viruses. In contrast to many broad, established and well-organized bioinformatics communities (e.g. structural genomics, ontologies, next-generation sequencing, expression analysis), research groups focusing on viruses can probably be counted on the fingers of two hands. RESULTS: The purpose of this review is to increase awareness among bioinformatics researchers about the pressing needs and unsolved problems of computational virology. We focus primarily on RNA viruses that pose problems to many standard bioinformatics analyses owing to their compact genome organization, fast mutation rate and low evolutionary conservation. We provide an overview of tools and algorithms for handling viral sequencing data, detecting functionally important RNA structures, classifying viral proteins into families and investigating the origin and evolution of viruses.

Two new ranking methods for solutions of multi objective optimization problems are proposed in this paper. Theoretical results show that both new ranking methods form a total preorder and are refinements of the pareto dominance relation. These properties make the ranking methods suitable for the selection of a subset of good solutions from a set of non-dominated solutions as needed by meta-heuristics. In particular, this is shown experimentally for a Population-based ACO that uses the ranking methods to solve a multi objective flow shop problem.

Ant Colony Optimization (ACO) has been successfully applied to many combinatorial optimization problems. In this work we propose a new solution construction scheme for ACO. This scheme uses the common intervals of the current iteration's best solutions to guide the ants during solution construction. Firstly, we compared the performance of ACO and the proposed algorithm Common Interval ACO (CIACO). Secondly, we conducted an in-depth study for the CIACO algorithm to investigate the influence of the common interval guidance. For both experiments a large parameter space was used. The results show, that common intervals can be used to improve the solution quality in comparison to the standard ACO algorithm.

A new scheme is proposed for the design of probabilistic population based optimization algorithms for solving combinatorial optimization problems. The new scheme, Simple Probabilistic Population Based Optimization scheme (SPPBO), is used also to classify existing metaheuristics, e.g., the Population-based Ant Colony Optimization algorithm (PACO) and the Simplified Swarm Optimization algorithm (SSO). The classification shows the close relationship between PACO and SSO. This fact has not been recognized in the literature so far. SPPBO is also used to identify new metaheuristics that come up naturally as variants and combinations of PACO and SSO. An experimental study is done to evaluate and compare the different algorithms when applied to the Traveling Salesperson Problem. The results show which parts of the algorithms are helpful for obtaining a good optimization behaviour. In addition to the original PACO and SSO algorithms also some of the new combinations perform very well.

We analyze the behavior and efficiency of a task-force of heterogeneous agents, which have different skills to solve a resource collection task. The agents can move within an arena and are able to cooperate in order to accessing the skills of other agents. Cooperation between agents is only possible, when they form a group by moving to the same location. Yet the number of agents on the same location is restricted. Thus the agents can only cooperate with a limited number of other agents at a time. Different strategies for the agents to decide whether to cooperate or not and how to detect the most favorable partner for cooperation within their surrounding are are investigated. In the studied scenarios the amounts of the different resources that are available varies between different locations. The agents are forced to decide whether to follow the drive of their own efficiency, or rather to build a cooperation with close-by agents that might be located in a different direction.

Abstract Particle swarm optimization (PSO) is a metaheuristic that has been applied successfully to many continuous and combinatorial optimization problems, e.g., in the fields of economics, engineering, and natural sciences. In PSO, a swarm of particles moves within a search space in order to find an optimal solution. Unfortunately, it is hard to understand in detail why and how changes in the design of PSO algorithms affect the optimization behavior. Visualizing the particle states could provide substantially better insight into PSO algorithms. Though in case of combinatorial optimization problems, it often raises the problem of illustrating the states within the discrete search space that cannot be embedded spatially. We propose a visualization approach to depict the optimization problem topologically using a landscape metaphor. This visualization is augmented by an illustration of the time‐dependent states of the particles. Thus, the user of dPSO‐Vis is able to analyze the swarm's behavior within the search space. In principle, our method can be used for any optimization algorithm where a swarm of individuals searches within a discrete search space. Our approach is verified with a case study for the PSO algorithm HelixPSO that predicts the secondary structure of RNA molecules.

Given a set of nucleotide sequences and corresponding gene annotations which might contain a moderate number of errors we consider the problem to identify common substrings occurring in homologous genes and to identify putative errors in the given annotations. The problem is solved by identifying nodes in a suffix tree that contains all substrings occurring in the data set. Due to the large size of the targeted data set our approach employs a truncated version of suffix trees. The approach is successfully applied to the mitochondrial nucleotide sequences and the corresponding annotations available in RefSeq for more than 2000 metazoan species. We demonstrate that the approach finds appropriate subsequences despite of errors in the given annotations. Moreover, it identifies several hundred errors within the RefSeq annotations.

The identification of protein binding sites and the prediction of protein-ligand complexes play a key role in the pharmaceutical drug design process and many domains of life sciences. Computational approaches for protein-ligand docking (or molecular docking) have received increased attention over the last years as they allow inexpensive and fast prediction of protein-ligand complexes. Here we introduce the principle of Bee Nest-Site Selection Optimisation (BNSO), which solves optimisation problems using a novel scheme inspired by the nest-site selection behaviour found in honeybees. Moreover, the first BNSO algorithm -- Bee-Nest -- is proposed and applied to molecular docking. The performance of Bee-Nest is tested on 173 docking instances from the PDBbind core set and compared to the performance of three reference algorithms. The results show that Bee-Nest could find ligand poses with very small energy levels. Interestingly, the reference Particle Swarm Optimization (PSO) produces results that are qualitatively closer to wet-lab experimentally derived complexes but have higher energy levels than the results found by Bee-Nest. Our results highlight the superior performance of Bee-Nest in semi-local optimization for the molecular docking problem and suggests Bee-Nest's usefulness in a hybrid strategy.

BACKGROUND: Changes in the order of mitochondrial genes are a good source of information for phylogenetic investigations. Phylogenetic hypotheses are often supported by parsimonious mitochondrial gene order rearrangement scenarios. CREx is a heuristic for computing short pairwise rearrangement scenarios for metazoan mitochondrial gene orders. Different from other methods, CREx considers four types of rearrangement operations: inversions, transpositions, inverse transpositions, and tandem duplication random loss operations. RESULTS: An extensive analysis of the CREx reconstructions for artificial data has been presented and it is shown how the quality of the reconstructed rearrangement scenarios depends on the type of rearrangement model and additional parameter values. Moreover, a fast method is proposed to apply CREx to a large number of gene orders to find likely rearrangement scenarios and store them in a graph structure called RI-Graph. This method is applied to analyse all known metazoan mitochondrial gene orders. It is shown that the obtained RI-Graph contains many rearrangement scenarios that are described in the literature. CONCLUSIONS: The prospects and limitations of CREx have been analysed empirically and a comparison with the literature on gene order evolution highlights its benefits. The newly developed method to apply CREx to a large number of gene orders is successful in computing an RI-graph that contains many rearrangement scenarios for metazoan gene orders that have also been described in the literature. This shows that the new method is very helpful for a fast analysis of a large number of gene orders which is relevant due to the strongly increasing number of known gene orders.

BACKGROUND: Coevolutionary systems like hosts and their parasites are commonly used model systems for evolutionary studies. Inferring the coevolutionary history based on given phylogenies of both groups is often done by employing a set of possible types of events that happened during coevolution. Costs are assigned to the different types of events and a reconstruction of the common history with a minimal sum of event costs is sought. RESULTS: This paper introduces a new algorithm and a corresponding tool called CoRe-PA, that can be used to infer the common history of coevolutionary systems. The proposed method utilizes an event-based concept for reconciliation analyses where the possible events are cospeciations, sortings, duplications, and (host) switches. All known event-based approaches so far assign costs to each type of cophylogenetic events in order to find a cost-minimal reconstruction. CoRe-PA uses a new parameter-adaptive approach, i.e., no costs have to be assigned to the coevolutionary events in advance. Several biological coevolutionary systems that have already been studied intensely in literature are used to show the performance of CoRe-PA. CONCLUSION: From a biological point of view reasonable cost values for event-based reconciliations can often be estimated only very roughly. CoRe-PA is very useful when it is difficult or impossible to assign exact cost values to different types of coevolutionary events in advance.

When asked if ants rest or if they work untiringly all day long, most people would probably respond that they had no idea. In fact, when watching the bustling life of an ant hill it is hard to imagine that ants take a rest from now and then. However, biologists discovered that ants rest quite a large fraction of their time. Surprisingly, not only single ants show alternate phases of resting and being active, but whole ant colonies exhibit synchronized activity phases that result from self-organization. Inspired by this self-synchronization behaviour of ant colonies, we develop a mechanism for self-synchronized duty-cycling in mobile sensor networks. In addition, we equip sensor nodes with energy harvesting capabilities such as, for example, solar cells. We show that the self-synchronization mechanism can be made adaptive depending on the available energy.

This special issue contains seven papers describing recent research developments in the swarm intelligence (SI) field.

Dynamically reconfigurable hardware offers promising possibilities for flexible, computation intensive applications. With the technological advance of reconfigurable hardware came a rapid growth in the number of resources per chip requiring large amounts of data transfer per reconfiguration. Especially run-time reconfigurable applications, which make frequent use of reconfiguration, suffer from the growing overhead induced thereby. In this project, we investigate novel concepts for reconfigurable architectures that can dynamically reconfigure the actual reconfiguration potential to reduce the total amount of reconfiguration data that is necessary for a computation.

Genomic rearrangement operations can be very useful to infer the phylogenetic relationship of gene orders representing species. We study the problem of finding potential ancestral gene orders for the gene orders of given taxa, such that the corresponding rearrangement scenario has a minimal number of reversals, and where each of the reversals has to preserve the common intervals of the given input gene orders. Common intervals identify sets of genes that occur consecutively in all input gene orders. The problem of finding such an ancestral gene order is called the preserving reversal median problem (pRMP). A tree-based data structure for the representation of the common intervals of all input gene orders is used in our exact algorithm TCIP for solving the pRMP. It is known that the minimum number of reversals to transform one gene order into another can be computed in polynomial time, whereas the corresponding problem with the restriction that common intervals should not be destroyed is already NP-hard. It is shown theoretically that TCIP can solve a large class of pRMP instances in polynomial time. Empirically we show the good performance of TCIP on biological and artificial data.

We propose an algorithm that is based on the Ant Colony Optimization (ACO) metaheuristic for producing harmonized melodies. The algorithm works in two stages. In the first stage it creates a melody. This melody is then harmonized according to the rules of Baroque harmony in the second stage. This is the first ACO algorithm to create music that uses domain knowledge and the first employed for harmonization of a melody.

This paper introduces the HelixPSO particle swarm optimization (PSO) algorithm for finding minimum energy RNA secondary structures. It is shown experimentally that HelixPSO profits when it is combined with a genetic algorithm that finds a good starting population for HelixPSO. On all test instances this hybrid variant of HelixPSO performs significantly better than a state-of-the-art genetic algorithm. Also compared with another PSO algorithm that has been proposed very recently for the prediction of RNA secondary structures, HelixPSO is more efficient both in terms of free energy and correctly predicted base pairs

The moving behaviour of the particles in particle swarm optimization (PSO) algorithms is studied in this paper. It is shown that particles in standard PSO have a clear bias in their movement direction that depends on the direction of the coordinate axes. This has the effect that the optimization behaviour of standard PSO is not invariant to rotations of the optimization function. A second problem of standard PSO is that non-oscillatory trajectories can quickly cause a particle to stagnate. A sidestep mechanism is proposed to improve the movement of the particles. A particle performs a sidestep with respect to a certain dimension when stagnation of movement along this dimension is observed. It is shown for simple test functions that the movement behaviour of sidestep PSO can prevent the unwanted bias and makes PSO less dependent on rotations of the optimization function. It is also shown for standard benchmark functions that sidestep PSO outperforms standard PSO

A new approach to prevent negative emergent behaviors of adaptive or organic computing systems is presented. One characteristic of such computing systems is the use self-organisation principles from nature and components that make decentralized decisions. To control such systems is a difficult task. In this paper we propose to control by introducing a swarm of so called anti-components to the system that can prevent the negative emergence. As an example serves a model that is inspired by the emergent behavior of ants to cluster different items. This model system has been used for several applications in computer science already. Different types of anti-components (or anti-agents) that can prevent a clustering behavior are designed for this system. Several cluster validity measures are used to investigate the clustering behavior of a system that contains standard clustering agents together with anti-clustering agents. It is shown that such systems can show a complex behavior over time where a phase of item distributions with increasing order is followed by distributions with increasing degree of clustering. It is also shown that a medium number of certain anti-clustering agents (which in a larger number completely prevent any clustering) may even help the system to perform a good clustering faster

MOTIVATION: Algorithms for phylogenetic tree reconstruction based on gene order data typically repeatedly solve instances of the reversal median problem (RMP) which is to find for three given gene orders a fourth gene order (called median) with a minimal sum of reversal distances. All existing algorithms of this type consider only one median for each RMP instance even when a large number of medians exist. A careful selection of one of the medians might lead to better phylogenetic trees. RESULTS: We propose a heuristic algorithm amGRP for solving the multiple genome rearrangement problem (MGRP) by repeatedly solving instances of the RMP taking all medians into account. Algorithm amGRP uses a branch-and-bound method that branches over medians from a selected subset of all medians for each RMP instance. Different heuristics for selecting the subsets have been investigated. To show that the medians for RMP vary strongly with respect to different properties that are likely to be relevant for phylogenetic tree reconstruction, the set of all medians has been investigated for artificial datasets and mitochondrial DNA (mtDNA) gene orders. Phylogenetic trees have been computed for a large set of randomly generated gene orders and two sets of mtDNA gene order data for different animal taxa with amGRP and with two standard approaches for solving the MGRP (GRAPPA-DCM and MGR). The results show that amGRP outperforms both other methods with respect to solution quality and computation time on the test data. AVAILABILITY: The source code of amGRP, additional results and the test instances used in this paper are freely available from the authors.

SUMMARY: We present the web-based program CREx for heuristically determining pairwise rearrangement events in unichromosomal genomes. CREx considers transpositions, reverse transpositions, reversals and tandem-duplication-random-loss (TDRL) events. It supports the user in finding parsimonious rearrangement scenarios given a phylogenetic hypothesis. CREx is based on common intervals, which reflect genes that appear consecutively in several of the input gene orders. AVAILABILITY: CREx is freely available at http://pacosy.informatik.uni-leipzig.de/crex

Dynamically reconfigurable hardware has already been deployed for accelerating computationally demanding applications. Some of these hardware architectures allow run time reconfiguration but this leads usually to a large reconfiguration overhead. The advantage of run time reconfiguration is that it allows new algorithmic solutions for many applications. To study the potential of frequent run time reconfiguration it is interesting to investigate its costs and benefits from an abstract point of view and to develop new architectural concepts. Multilevel reconfigurable architectures are one such concept that introduce several levels of reconfiguration. This paper deals with new types of multi-level reconfigurable architectures. The corresponding problem of finding the best granularity for different reconfiguration levels is formulated and investigated. Although this problem is shown to be NP-complete, an interesting restricted subcase is solved optimally in polynomial time. For the general case, a good heuristic is proposed that is based on solutions for the restricted case. Results on three example applications show that the reconfiguration cost can be reduced with the new architectures. Based on a proposed measure of relative efficiency it is also shown that the new architectures are more efficient so that they obtain a larger reconfiguration cost reduction with less additional hardware

In this paper, we study multi-level dynamically reconfigurable architectures. These are extensions of standard reconfigurable architectures where ordinary reconfiguration operations correspond to the lowest reconfiguration level. On each higher reconfiguration level the reconfiguration capabilities of the reconfigurable resources that are available on the level directly below can be reconfigured. We show that the problem to find optimal reconfigurations with an arbitrary number of reconfiguration levels can be found in polynomial time for the switch cost model. The problem of finding the optimal number of reconfiguration levels is shown to be solvable in polynomial time on homogeneous multi-level architectures but it becomes NP-hard for heterogeneous multi-level architectures. Moreover, we present experimental results for some example problems on a simple test architecture.

A self-organized allocation scheme for service tasks in computing systems is proposed in this paper. Usually components of a computing system need some service from time to time in order perform their work efficiently. In adaptive computing systems the components and the necessary tasks adapt to the needs of users or the environment. Since in such cases the type of service tasks will often change it is attractive to use reconfigurable hardware to perform the service tasks. The studied system consists of normal worker components and helper components which have reconfigurable hardware and can perform different service tasks. The speed with which a service tasks is executed by a helper depends on its actual configuration. Different strategies for the helpers to decide about service task acceptance and reconfiguration are proposed. These strategies are inspired by stimulus-threshold models that are used to explain task allocation in social insects

The order of genes in the genomes of species can change during evolution and can provide information about their phylogenetic relationship. An interesting method to infer the phylogenetic relationship from the gene orders is to use different types of rearrangement operations and to find possible rearrangement scenarios using these operations. One of the most common rearrangement operations is reversals, which reverse the order of a subset of neighbored genes. In this paper, we study the problem to find the ancestral gene order for three species represented by their gene orders. The rearrangement scenario should use a minimal number of reversals and no other rearrangement operations. This problem is called the Median problem and is known to be NP-complete. In this paper, we describe a heuristic algorithm for finding solutions to the Median problem that searches for rearrangement scenarios with the additional property that gene groups should not be destroyed by reversal operations. The concept of conserved intervals for signed permutations is used to describe such gene groups. We show experimentally, for different types of test problems, that the proposed algorithm produces very good results compared to other algorithms for the Median problem. We also integrate our reversal selection procedure into the well-known MGR and GRAPPA algorithms and show that they achieve a significant speedup while obtaining solutions of the same quality as the original algorithms on the test problems.

A hierarchical version of the particle swarm optimization (PSO) metaheuristic is introduced in this paper. In the new method called H-PSO, the particles are arranged in a dynamic hierarchy that is used to define a neighborhood structure. Depending on the quality of their so-far best-found solution, the particles move up or down the hierarchy. This gives good particles that move up in the hierarchy a larger influence on the swarm. We introduce a variant of H-PSO, in which the shape of the hierarchy is dynamically adapted during the execution of the algorithm. Another variant is to assign different behavior to the individual particles with respect to their level in the hierarchy. H-PSO and its variants are tested on a commonly used set of optimization functions and are compared to PSO using different standard neighborhood schemes.

Dynamically reconfigurable architectures or systems are able to reconfigure their function and/or structure to suit changing needs of a computation during run time. The increasing flexibility of modern dynamically reconfigurable systems improves their adaptability but also makes fast reconfiguration difficult because of the large amount of necessary reconfiguration information. However, even when a computation uses this flexibility it is not use it all the time. Therefore, we propose to make the potential for reconfiguration itself reconfigurable. This allows for speeding up reconfiguration operations during phases where only parts of the total flexibility are required. Such architectures are called hyperreconfigurable and uses two types of reconfiguration operations: hyperreconfigurations for changing the reconfiguration potential and ordinary reconfigurations for actually configuring a new context for a computation.

Summary form only given. Hyperreconfigurable architectures can adapt their reconfiguration abilities during run time and have been proposed to increase the speed of dynamic reconfiguration. They use two types of dynamic reconfiguration steps. In hyperreconfiguration steps they change their ability for reconfiguration and in ordinary reconfiguration steps they reconfigure the actual contexts for a computation within the limits that have been set by the last hyperreconfiguration step. We study the concept of partial hyperreconfiguration for multi tasks environments. We propose several models for partially hyperreconfigurable architectures and study corresponding reconfiguration problems to find optimal (hyper)reconfigurations. While under a general cost model the problem to find optimal (hyper)reconfigurations is known to be NP-complete even for a single task. We identify an interesting special case that can be solved by a polynomial time algorithm even for multiple tasks. We illustrate the introduced concepts with a partially hyperreconfigurable example architecture and describe the results of simulated runs with a small test application.

Summary form only given. A new type of a decentralized clustering problem for networks is studied in this paper. The so called decentralized packet clustering (DPC) problem is to find for a set of packets that are send around in a network a clustering where the clustering has to be done by the routers without using neither much computational power nor a large amount of memory. Further, no direct information transfer between the routers is allowed. We investigate the behavior of a type of decentralized k-means algorithm $called DPClust - for the DPC problem. DPClust has also some similarities with ant based clustering algorithms. We investigate the clustering behavior DPClust for different cluster problems and for networks that consist of several subnetworks so that there is only a limited amount of packet exchange between the subnetworks. A dynamic situation where the packet exchange rates varies over time is also considered. The proposed DPC problem leads to further interesting research problems for network clustering.

A hierarchical version of the particle swarm optimization method called H-PSO is introduced. In H-PSO the particles are arranged in a dynamic hierarchy that is used to define a neighborhood structure. Depending on the quality of their so far best found solution the particles move up or down the hierarchy so that good particles have a higher influence on the swarm. Moreover, the hierarchy is used to define different search properties for the particles. Several variants of H-PSO are compared experimentally with variants of the standard PSO.

We propose to modify a type of ant algorithm called Population based Ant Colony Optimization (P-ACO) to allow implementation on an FPGA architecture. Ant algorithms are adapted from the natural behavior of ants and used to find good solutions to combinatorial optimization problems. General layout on the FPGA and algorithmic description are covered The most notable achievements featured in this paper are a runtime reduction and including the approximation of the heuristic function by a small set of favored decisions which changes over time.

The dynamics of Ant Colony Optimization (ACO) algorithms is studied using a deterministic model that assumes an average expected behavior of the algorithms. The ACO optimization metaheuristic is an iterative approach, where in every iteration, artificial ants construct solutions randomly but guided by pheromone information stemming from former ants that found good solutions. The behavior of ACO algorithms and the ACO model are analyzed for certain types of permutation problems. It is shown analytically that the decisions of an ant are influenced in an intriguing way by the use of the pheromone information and the properties of the pheromone matrix. This explains why ACO algorithms can show a complex dynamic behavior even when there is only one ant per iteration and no competition occurs. The ACO model is used to describe the algorithm behavior as a combination of situations with different degrees of competition between the ants. This helps to better understand the dynamics of the algorithm when there are several ants per iteration as is always the case when using ACO algorithms for optimization. Simulations are done to compare the behavior of the ACO model with the ACO algorithm. Results show that the deterministic model describes essential features of the dynamics of ACO algorithms quite accurately, while other aspects of the algorithms behavior cannot be found in the model.

SCOPUS: ed.j

An ant colony optimization (ACO) approach for the resource-constrained project scheduling problem (RCPSP) is presented. Several new features that are interesting for ACO in general are proposed and evaluated. In particular, the use of a combination of two pheromone evaluation methods by the ants to find new solutions, a change of the influence of the heuristic on the decisions of the ants during the run of the algorithm, and the option that an elitist ant forgets the best-found solution are studied. We tested the ACO algorithm on a set of large benchmark problems from the Project Scheduling Library. Compared to several other heuristics for the RCPSP, including genetic algorithms, simulated annealing, tabu search, and different sampling methods, our algorithm performed best on average. For nearly one-third of all benchmark problems, which were not known to be solved optimally before, the algorithm was able to find new best solutions.

Merkle D, Middendorf M. Fast ant colony optimization on reconfigurable processor arrays. In: Proceedings 15th International Parallel and Distributed Processing Symposium. IPDPS 2001. IEEE; 2001: 1465-1472.