MOTIVATION: We describe an approach to normalize spotted microarray data, based on a physically motivated calibration model. This model consists of two major components, describing the hybridization of target transcripts to their corresponding probes on the one hand, and the measurement of fluorescence from the hybridized, labeled target on the other hand. The model parameters and error distributions are estimated from external control spikes. RESULTS: Using a publicly available dataset, we show that our procedure is capable of adequately removing the typical non-linearities of the data, without making any assumptions on the distribution of differences in gene expression from one biological sample to the next. Since our model links target concentration to measured intensity, we show how absolute expression values of target transcripts in the hybridization solution can be estimated up to a certain degree.

BACKGROUND: The development of algorithms to infer the structure of gene regulatory networks based on expression data is an important subject in bioinformatics research. Validation of these algorithms requires benchmark data sets for which the underlying network is known. Since experimental data sets of the appropriate size and design are usually not available, there is a clear need to generate well-characterized synthetic data sets that allow thorough testing of learning algorithms in a fast and reproducible manner. RESULTS: In this paper we describe a network generator that creates synthetic transcriptional regulatory networks and produces simulated gene expression data that approximates experimental data. Network topologies are generated by selecting subnetworks from previously described regulatory networks. Interaction kinetics are modeled by equations based on Michaelis-Menten and Hill kinetics. Our results show that the statistical properties of these topologies more closely approximate those of genuine biological networks than do those of different types of random graph models. Several user-definable parameters adjust the complexity of the resulting data set with respect to the structure learning algorithms. CONCLUSION: This network generation technique offers a valid alternative to existing methods. The topological characteristics of the generated networks more closely resemble the characteristics of real transcriptional networks. Simulation of the network scales well to large networks. The generator models different types of biological interactions and produces biologically plausible synthetic gene expression data.

In this note, we indicate how the basic machinery of Walsh transforms can be generalized from the binary case ([3, 4]) to multary alphabets. Our main results show how Walsh coefficients are related to partition coefficients and how they may be used to calculate schema averages.

Many experiments have proved that crossover is an essential search operator in evolutionary algorithms, at least for certain functions. However, the rigorous analysis of such algorithms on crossover-friendly functions is still in its infancy. Here, a recombinative hill-climber is analyzed on the crossover-friendly function hierarchical-if-and-only-if (H-IFF) introduced by Watson et al. (1998). The dynamics of this algorithm are investigated and it is proved that the expected optimization time equals /spl Theta/(n log n).

We introduce a discrete particle swarm (PS) algorithm for solving binary constraint satisfaction problems (CSPs). It uses information about the conflicts between the variables to compute the velocity of the individual particles. We tune the parameters of the PS algorithm to a quasi-optimal setting and study the behavior of the algorithm under changes to this setting. The PS algorithm is then empirically compared with ant colonies (which also belong to the swarm intelligence class) and genetic algorithms on a whole range of randomly generated binary CSP instances.

In the context of optimization by evolutionary algorithms (EAs), epistasis, deception, and scaling are well-known examples of problem difficulty characteristics. The presence of one such characteristic in the representation of a search problem indicates a certain type of difficulty the EA is to encounter during its search for globally optimal configurations. In this paper, we claim that the occurrence of symmetry in the representation is another problem difficulty characteristic and discuss one particular form, spin-flip symmetry, characterized by fitness invariant permutations on the alphabet. Its usual effect on unspecialized EAs, premature convergence due to synchronization problems, is discussed in detail. We discuss five different ways to specialize EAs to cope with the symmetry: adapting the genetic operators, changing the fitness function, using a niching technique, using a distributed EA, and attaching a highly redundant genotype-phenotype mapping.

The presence or symmetry in the representation of an optimization problem can have a positive or a negative influence on the dynamics of a search algorithm. Symmetry can cause a genetic algorithm or simulated annealing to get stuck in a local optimum, but it can also help an algorithm to find the optima more quickly, as the dual genetic algorithm does in some cases. The first part of the paper describes three common types of symmetry and their effects on evolutionary algorithms. Next to obvious permutations on the string representation leaving the objective value invariant, the interaction structure of the problem can be a source of symmetry. Typical examples can be found in the class of aggregated problems, studied in the second part of the paper. An abstract model for aggregated problems is introduced together with a strategy to overcome their symmetry.

Proposes an object model for a generic optimization framework centred around two concepts: search spaces and transformations of search spaces. We define and discuss the model's basic entities and demonstrate how commonly used optimization techniques within the world of evolutionary algorithms (EAs) can be represented in the model. We briefly discuss an implementation of the model, called bIOS (Belgian Intelligent Optimization System), which serves as an efficient tool for both theoretical research in EAs and industry-oriented optimization tasks.

We define an ant algorithm for solving random binary constraint satisfaction problems (CSPs). We empirically investigate the behavior of the algorithm on this type of problems and establish the parameter settings under which the ant algorithm performs best for a specific class of CSPs. The ant algorithm is compared to six other state-of-the-art stochastic algorithms from the field of evolutionary computing. It turns out that the ant algorithm outperforms all other algorithms and that bivariate distribution algorithms perform worse than the univariate ones, the latter largely due to the fact that they cannot model the randomly generated instances.

This paper studies a number of predictive measures of problem difficulty, among which epistasis variance and fitness distance correlation are the most widely known. Our approach is based on comparing the reference class of a measure to a number of known easy function classes. First, we generalize the reference classes of fitness distance correlation and epistasis variance, and construct a new predictive measure that is insensitive to nonlinear fitness scaling. We then investigate the relations between the reference classes of the measures and a number of intuitively easy classes. We also point out the need to further identify which functions are easy for a given class of evolutionary algorithms in order to design more efficient hardness indicators for them. We finally restrict attention to the genetic algorithm (GA), and consider both GA-easy and GA-hard fitness functions, and give experimental evidence that the values of the measures, based on random samples, can be completely unreliable and entirely uncorrelated to the convergence quality and convergence speed of GA instances using either proportional or ranking selection.

Recent work stresses the limitations of fitness distance correlation (FDC) as an indicator of landscape difficulty for genetic algorithms (GAs). Realizing that the fitness distance correlation (FDC) value cannot be reliably related to landscape difficulty, we investigate whether an interpretation of the whole correlation plot can yield reliable information about the behavior of the GA. Our approach is as follows. We present a generic method for constructing fitness functions which share the same fitness versus distance-to-optimum relation (FD relation). Special attention is given to FD relations which show no local optimum in the correlation plot, as is the case for the relation induced by Horn's longpath (J. Horn and D.E. Goldberg, 1995). We give an inventory of different types of GA behavior found within a class of fitness functions with a common correlation plot. We finally show that GA behavior can be very sensitive to small modifications of the fitness-distance relation.

In this paper we investigate the behavior of mutation-based evolutionary algorithms on highly symmetric binary constraint satisfaction problems. With empirical methods we study why and when these algorithms perform better under the stepwise adaptive weighting of penalties (SAWing) than under the standard penalty function. We observe that SAWing has little effect when the local optima of the symmetric problems are not very strong. However, while the use of the standard penalty function can lead to strong local optima, the SAWing mechanism can avoid this situation. The symmetric problems we consider are the standard one-dimensional Ising model and a more complex construction with the Ising model as the core component.