A review of estimation of distribution algorithms in bioinformatics
---
paper_title: Linkage Information Processing In Distribution Estimation Algorithms

paper_content:

The last few years there has been an increasing amount of interest in the field of distribution estimation optimization algorithms. As more techniques are introduced, the variety in tested distribution structures increases. In this paper we analyze the implications of the form of such a structure. We show that learning the linkage relations alone and using them directly in a distribution estimation algorithm to generate new samples is not sufficient for building competent evolutionary algorithms. The information needs to be processed to identify and use the building blocks.
---
paper_title: Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation

paper_content:

List of Figures. List of Tables. Preface. Contributing Authors. Series Foreword. Part I: Foundations. 1. An Introduction to Evolutionary Algorithms J.A. Lozano. 2. An Introduction to Probabilistic Graphical Models P. Larranaga. 3. A Review on Estimation of Distribution Algorithms P. Larranaga. 4. Benefits of Data Clustering in Multimodal Function Optimization via EDAs J.M. Pena, et al. 5. Parallel Estimation of Distribution Algorithms J.A. Lozano, et al. 6. Mathematical Modeling of Discrete Estimation of Distribution Algorithms C. Gonzalez, et al. Part II: Optimization. 7. An Empiricial Comparison of Discrete Estimation of Distribution Algorithms R. Blanco., J.A. Lozano. 8. Results in Function Optimization with EDAs in Continuous Domain E. Bengoetxea, et al. 9. Solving the 0-1 Knapsack Problem with EDAs R. Sagarna, P. Larranaga. 10. Solving the Traveling Salesman Problem with EDAs V. Robles, et al. 11. EDAs Applied to the Job Shop Scheduling Problem J.A. Lozano, A. Mendiburu. 12. Solving Graph Matching with EDAs Using a Permutation-Based Representation E. Bengoetxea, et al. Part III: Machine Learning. 13. Feature Subset Selection by Estimation of Distribution Algorithms I. Inza, et al. 14. Feature Weighting for Nearest Neighbor by EDAs I. Inza, et al. 15. Rule Induction by Estimation of Distribution Algorithms B. Sierra, et al. 16. Partial Abductive Inference in Bayesian Networks: An Empirical Comparison Between GAs and EDAs L.M. de Campos, et al.17. Comparing K-Means, GAs and EDAs in Partitional Clustering J. Roure, et al. 18. Adjusting Weights in Artificial Neural Networks using Evolutionary Algorithms C. Cotta, et al. Index.
---
paper_title: MIMIC: Finding Optima by Estimating Probability Densities

paper_content:

In many optimization problems, the structure of solutions reflects complex relationships between the different input parameters. For example, experience may tell us that certain parameters are closely related and should not be explored independently. Similarly, experience may establish that a subset of parameters must take on particular values. Any search of the cost landscape should take advantage of these relationships. We present MIMIC, a framework in which we analyze the global structure of the optimization landscape. A novel and efficient algorithm for the estimation of this structure is derived. We use knowledge of this structure to guide a randomized search through the solution space and, in turn, to refine our estimate ofthe structure. Our technique obtains significant speed gains over other randomized optimization procedures.
---
paper_title: Evolutionary Synthesis of Bayesian Networks for Optimization

paper_content:

We shortly review our theoretical analysis of genetic algorithms and provide some new results. The theory has lead to the design of three different algorithms, all based on probability distributions instead of recombination of strings. In order to be numerically tractable, the probability distribution has to be factored into a small number of factors. Each factor should depend on a small number of variables only. For certain applications the factorization can be explicitly determined. In general it has to be determined from the search points used for the optimization. Computing the factorization from the data leads to learning Bayesian networks. The problem of finding a minimal structure which explains the data is discussed in detail. It is shown that the Bayesian Information Criterion is a good score for this problem. The algorithms are extended to probabilistic prototype trees used for synthesizing programs.
---
paper_title: Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images*

paper_content:

We make an analogy between images and statistical mechanics systems. Pixel gray levels and the presence and orientation of edges are viewed as states of atoms or molecules in a lattice-like physical system. The assignment of an energy function in the physical system determines its Gibbs distribution. Because of the Gibbs distribution, Markov random field (MRF) equivalence, this assignment also determines an MRF image model. The energy function is a more convenient and natural mechanism for embodying picture attributes than are the local characteristics of the MRF. For a range of degradation mechanisms, including blurring, non-linear deformations, and multiplicative or additive noise, the posterior distribution is an MRF with a structure akin to the image model. By the analogy, the posterior distribution defines another (imaginary) physical system. Gradual temperature reduction in the physical system isolates low-energy states (‘annealing’), or what is the same thing, the most probable states under the Gib...
---
paper_title: Population Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitve Learning

paper_content:

Genetic algorithms (GAs) are biologically motivated adaptive systems which have been used, with varying degrees of success, for function optimization. In this study, an abstraction of the basic genetic algorithm, the Equilibrium Genetic Algorithm (EGA), and the GA in turn, are reconsidered within the framework of competitive learning. This new perspective reveals a number of different possibilities for performance improvements. This paper explores population-based incremental learning (PBIL), a method of combining the mechanisms of a generational genetic algorithm with simple competitive learning. The combination of these two methods reveals a tool which is far simpler than a GA, and which out-performs a GA on large set of optimization problems in terms of both speed and accuracy. This paper presents an empirical analysis of where the proposed technique will outperform genetic algorithms, and describes a class of problems in which a genetic algorithm may be able to perform better. Extensions to this algorithm are discussed and analyzed. PBIL and extensions are compared with a standard GA on twelve problems, including standard numerical optimization functions, traditional GA test suite problems, and NP-Complete problems.
---
paper_title: Using Optimal Dependency-Trees for Combinatorial Optimization: Learning the Structure of the Search Space

paper_content:

Many combinatorial optimization algorithms have no mechanism for capturing inter-parameter dependencies. However, modeling such dependencies may allow an algorithm to concentrate its sampling more effectively on regions of the search space which have appeared promising in the past. We present an algorithm which incrementally learns pairwise probability distributions from good solutions seen so far, uses these statistics to generate optimal (in terms of maximum likelihood) dependency trees to model these distributions, and then stochastically generates new candidate solutions from these trees. We test this algorithm on a variety of optimization problems. Our results indicate superior performance over other tested algorithms that either (1) do not explicitly use these dependencies, or (2) use these dependencies to generate a more restricted class of dependency graphs.
---
paper_title: The Bivariate Marginal Distribution Algorithm

paper_content:

The paper deals with the Bivariate Marginal Distribution Algorithm (BMDA). BMDA is an extension of the Univariate Marginal Distribution Algorithm (UMDA). It uses the pair gene dependencies in order to improve algorithms that use simple univariate marginal distributions. BMDA is a special case of the Factorization Distribution Algorithm, but without any problem specific knowledge in the initial stage. The dependencies are being discovered during the optimization process itself. In this paper BMDA is described in detail. BMDA is compared to different algorithms including the simple genetic algorithm with different crossover methods and UMDA. For some fitness functions the relation between problem size and the number of fitness evaluations until convergence is shown.
---
paper_title: BOA: The Bayesian Optimization Algorithm

paper_content:

In this paper, an algorithm based on the concepts of genetic algorithms that uses an estimation of a probability distribution of promising solutions in order to generate new candidate solutions is proposed. To estimate the distribution, techniques for modeling multivariate data by Bayesian networks are used. The proposed algorithm identifies, reproduces and mixes building blocks up to a specified order. It is independent of the ordering of the variables in the strings representing the solutions. Moreover, prior information about the problem can be incorporated into the algorithm. However, prior information is not essential. Preliminary experiments show that the BOA outperforms the simple genetic algorithm even on decomposable functions with tight building blocks as a problem size grows.
---
paper_title: Estimation of Distribution Algorithms with Kikuchi Approximations

paper_content:

The question of finding feasible ways for estimating probability distributions is one of the main challenges for Estimation of Distribution Algorithms (EDAs). To estimate the distribution of the selected solutions, EDAs use factorizations constructed according to graphical models. The class of factorizations that can be obtained from these probability models is highly constrained. Expanding the class of factorizations that could be employed for probability approximation is a necessary step for the conception of more robust EDAs. In this paper we introduce a method for learning a more general class of probability factorizations. The method combines a reformulation of a probability approximation procedure known in statistical physics as the Kikuchi approximation of energy, with a novel approach for finding graph decompositions. We present the Markov Network Estimation of Distribution Algorithm (MN-EDA), an EDA that uses Kikuchi approximations to estimate the distribution, and Gibbs Sampling (GS) to generate new points. A systematic empirical evaluation of MN-EDA is done in comparison with different Bayesian network based EDAs. From our experiments we conclude that the algorithm can outperform other EDAs that use traditional methods of probability approximation in the optimization of functions with strong interactions among their variables.
---
paper_title: A Factorized Distribution Algorithm Using Single Connected Bayesian Networks

paper_content:

Single connected Factorized Distribution Algorithms (FDA-SC) use factorizations of the joint distribution, which are trees, forests or polytrees. At each stage of the evolution they build a polytree from which new points are sampled. We study empirically the relation between the accuracy of the learned model and the quality of the new search points generated. We show that a change of the learned model before sampling might reduce the population size requirements of sampling.
---
paper_title: Schemata, Distributions and Graphical Models in Evolutionary Optimization

paper_content:

In this paper the optimization of additively decomposed discrete functions is investigated. For these functions genetic algorithms have exhibited a poor performance. First the schema theory of genetic algorithms is reformulated in probability theory terms. A schema defines the structure of a marginal distribution. Then the conceptual algorithm BEDA is introduced. BEDA uses a Boltzmann distribution to generate search points. From BEDA a new algorithm, FDA, is derived. FDA uses a factorization of the distribution. The factorization captures the structure of the given function. The factorization problem is closely connected to the theory of conditional independence graphs. For the test functions considered, the performance of FDA—in number of generations till convergence—is similar to that of a genetic algorithm for the OneMax function. This result is theoretically explained.
---
paper_title: The compact genetic algorithm

paper_content:

This paper introduces the "compact genetic algorithm" (cGA). The cGA represents the population as a probability distribution over the set of solutions, and is operationally equivalent to the order-one behavior of the simple GA with uniform crossover. It processes each gene independently and requires less memory than the simple GA.
---
paper_title: Optimization by Estimation of Distribution with DEUM Framework Based on Markov Random Fields

paper_content:

This paper presents a Markov random field (MRF) approach to estimating and sampling the probability distribution in populations of solutions. The approach is used to define a class of algorithms under the general heading distribution estimation using Markov random fields (DEUM). DEUM is a subclass of estimation of distribution algorithms (EDAs) where interaction between solution variables is represented as an undirected graph and the joint probability of a solution is factorized as a Gibbs distribution derived from the structure of the graph. The focus of this paper will be on describing the three main characteristics of DEUM framework, which distinguishes it from the traditional EDA. They are: 1) use of MRF models, 2) fitness modeling approach to estimating the parameter of the model and 3) Monte Carlo approach to sampling from the model.
---
paper_title: Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications (Studies in Computational Intelligence)

paper_content:

The Factorized Distribution Algorithm and the Minimum Relative Entropy Principle.- Linkage Learning via Probabilistic Modeling in the Extended Compact Genetic Algorithm (ECGA).- Hierarchical Bayesian Optimization Algorithm.- Numerical Optimization with Real-Valued Estimation-of-Distribution Algorithms.- A Survey of Probabilistic Model Building Genetic Programming.- Efficiency Enhancement of Estimation of Distribution Algorithms.- Design of Parallel Estimation of Distribution Algorithms.- Incorporating a priori Knowledge in Probabilistic-Model Based Optimization.- Multiobjective Estimation of Distribution Algorithms.- Effective and Reliable Online Classification Combining XCS with EDA Mechanisms.- Military Antenna Design Using a Simple Genetic Algorithm and hBOA.- Feature Subset Selection with Hybrids of Filters and Evolutionary Algorithms.- BOA for Nurse Scheduling.- Searching for Ground States of Ising Spin Glasses with Hierarchical BOA and Cluster Exact Approximation.
---
paper_title: Using Previous Models to Bias Structural Learning in the Hierarchical BOA

paper_content:

Estimation of distribution algorithms (EDAs) are stochastic optimization techniques that explore the space of potential solutions by building and sampling explicit probabilistic models of promising candidate solutions. While the primary goal of applying EDAs is to discover the global optimum or at least its accurate approximation, besides this, any EDA provides us with a sequence of probabilistic models, which in most cases hold a great deal of information about the problem. Although using problem-specific knowledge has been shown to significantly improve performance of EDAs and other evolutionary algorithms, this readily available source of problem-specific information has been practically ignored by the EDA community. This paper takes the first step toward the use of probabilistic models obtained by EDAs to speed up the solution of similar problems in the future. More specifically, we propose two approaches to biasing model building in the hierarchical Bayesian optimization algorithm (hBOA) based on knowledge automatically learned from previous hBOA runs on similar problems. We show that the proposed methods lead to substantial speedups and argue that the methods should work well in other applications that require solving a large number of problems with similar structure.
---
paper_title: Feature Subset Selection by Bayesian network-based optimization

paper_content:

Abstract A new method for Feature Subset Selection in machine learning, FSS-EBNA (Feature Subset Selection by Estimation of Bayesian Network Algorithm), is presented. FSS-EBNA is an evolutionary, population-based, randomized search algorithm, and it can be executed when domain knowledge is not available. A wrapper approach, over Naive-Bayes and ID3 learning algorithms, is used to evaluate the goodness of each visited solution. FSS-EBNA, based on the EDA (Estimation of Distribution Algorithm) paradigm, avoids the use of crossover and mutation operators to evolve the populations, in contrast to Genetic Algorithms. In absence of these operators, the evolution is guaranteed by the factorization of the probability distribution of the best solutions found in a generation of the search. This factorization is carried out by means of Bayesian networks. Promising results are achieved in a variety of tasks where domain knowledge is not available. The paper explains the main ideas of Feature Subset Selection, Estimation of Distribution Algorithm and Bayesian networks, presenting related work about each concept. A study about the `overfitting' problem in the Feature Subset Selection process is carried out, obtaining a basis to define the stopping criteria of the new algorithm.
---
paper_title: Feature selection for splice site prediction: A new method using EDA-based feature ranking

paper_content:

BackgroundThe identification of relevant biological features in large and complex datasets is an important step towards gaining insight in the processes underlying the data. Other advantages of feature selection include the ability of the classification system to attain good or even better solutions using a restricted subset of features, and a faster classification. Thus, robust methods for fast feature selection are of key importance in extracting knowledge from complex biological data.ResultsIn this paper we present a novel method for feature subset selection applied to splice site prediction, based on estimation of distribution algorithms, a more general framework of genetic algorithms. From the estimated distribution of the algorithm, a feature ranking is derived. Afterwards this ranking is used to iteratively discard features. We apply this technique to the problem of splice site prediction, and show how it can be used to gain insight into the underlying biological process of splicing.ConclusionWe show that this technique proves to be more robust than the traditional use of estimation of distribution algorithms for feature selection: instead of returning a single best subset of features (as they normally do) this method provides a dynamical view of the feature selection process, like the traditional sequential wrapper methods. However, the method is faster than the traditional techniques, and scales better to datasets described by a large number of features.
---
paper_title: Fast feature selection using a simple estimation of distribution algorithm: a case study on splice site prediction

paper_content:

Motivation: Feature subset selection is an important preprocessing step for classification. In biology, where structures or processes are described by a large number of features, the elimination of irrelevant and redundant information in a reasonable amount of time has a number of advantages. It enables the classification system to achieve good or even better solutions with a restricted subset of features, allows for a faster classification, and it helps the human expert focus on a relevant subset of features, hence providing useful biological knowledge. Results: We present a heuristic method based on Estimation of Distribution Algorithms to select relevant subsets of features for splice site prediction in Arabidopsis thaliana. We show that this method performs a fast detection of relevant feature subsets using the technique of constrained feature subsets. Compared to the traditional greedy methods the gain in speed can be up to one order of magnitude, with results being comparable or even better than the greedy methods. This makes it a very practical solution for classification tasks that can be solved using a relatively small amount of discriminative features (or feature dependencies), but where the initial set of potential discriminative features is rather large.
---
paper_title: Toward integrating feature selection algorithms for classification and clustering

paper_content:

This paper introduces concepts and algorithms of feature selection, surveys existing feature selection algorithms for classification and clustering, groups and compares different algorithms with a categorizing framework based on search strategies, evaluation criteria, and data mining tasks, reveals unattempted combinations, and provides guidelines in selecting feature selection algorithms. With the categorizing framework, we continue our efforts toward-building an integrated system for intelligent feature selection. A unifying platform is proposed as an intermediate step. An illustrative example is presented to show how existing feature selection algorithms can be integrated into a meta algorithm that can take advantage of individual algorithms. An added advantage of doing so is to help a user employ a suitable algorithm without knowing details of each algorithm. Some real-world applications are included to demonstrate the use of feature selection in data mining. We conclude this work by identifying trends and challenges of feature selection research and development.
---
paper_title: Feature subset selection by genetic algorithms and estimation of distribution algorithms. A case study in the survival of cirrhotic patients treated with TIPS

paper_content:

The transjugular intrahepatic portosystemic shunt (TIPS) is an interventional treatment for cirrhotic patients with portal hypertension. In the light of our medical staff's experience, the consequences of TIPS are not homogeneous for all the patients and a subgroup dies in the first 6 months after TIPS placement. Actually, there is no risk indicator to identify this subgroup of patients before treatment. An investigation for predicting the survival of cirrhotic patients treated with TIPS is carried out using a clinical database with 107 cases and 77 attributes. Four supervised machine learning classifiers are applied to discriminate between both subgroups of patients. The application of several feature subset selection (FSS) techniques has significantly improved the predictive accuracy of these classifiers and considerably reduced the amount of attributes in the classification models. Among FSS techniques, FSS-TREE, a new randomized algorithm inspired on the new EDA (estimation of distribution algorithm) paradigm has obtained the best average accuracy results for each classifier.
---
paper_title: Molecular classification of cancer: class discovery and class prediction by gene expression monitoring

paper_content:

Although cancer classification has improved over the past 30 years, there has been no general approach for identifying new cancer classes (class discovery) or for assigning tumors to known classes (class prediction). Here, a generic approach to cancer classification based on gene expression monitoring by DNA microarrays is described and applied to human acute leukemias as a test case. A class discovery procedure automatically discovered the distinction between acute myeloid leukemia (AML) and acute lymphoblastic leukemia (ALL) without previous knowledge of these classes. An automatically derived class predictor was able to determine the class of new leukemia cases. The results demonstrate the feasibility of cancer classification based solely on gene expression monitoring and suggest a general strategy for discovering and predicting cancer classes for other types of cancer, independent of previous biological knowledge.
---
paper_title: Gene selection for cancer classification using wrapper approaches

paper_content:

Despite the fact that cancer classification has considerably improved, nowadays a general method that classifies known types of cancer has not yet been developed. In this work, we propose the use of supervised classification techniques, coupled with feature subset selection algorithms, to automatically perform this classification in gene expression datasets. Due to the large number of features of gene expression datasets, the search of a highly accurate combination of features is done by means of the new Estimation of Distribution Algorithms paradigm. In order to assess the accuracy level of the proposed approach, the naive-Bayes classification algorithm is employed in a wrapper form. Promising results are achieved, in addition to a considerable reduction in the number of genes. Stating the optimal selection of genes as a search task, an automatic and robust choice in the genes finally selected is performed, in contrast to previous works that research the same types of problems.
---
paper_title: Gene selection for classification of cancers using probabilistic model building genetic algorithm

paper_content:

Abstract Recently, DNA microarray-based gene expression profiles have been used to correlate the clinical behavior of cancers with the differential gene expression levels in cancerous and normal tissues. To this end, after selection of some predictive genes based on signal-to-noise (S2N) ratio, unsupervised learning like clustering and supervised learning like k -nearest neighbor ( k NN) classifier are widely used. Instead of S2N ratio, adaptive searches like Probabilistic Model Building Genetic Algorithm (PMBGA) can be applied for selection of a smaller size gene subset that would classify patient samples more accurately. In this paper, we propose a new PMBGA-based method for identification of informative genes from microarray data. By applying our proposed method to classification of three microarray data sets of binary and multi-type tumors, we demonstrate that the gene subsets selected with our technique yield better classification accuracy.
---
paper_title: Identification of Informative Genes for Molecular Classification Using Probabilistic Model Building Genetic Algorithm

paper_content:

DNA microarray allows the monitoring and measurement of the expression levels of thousands of genes simultaneously in an organism. A systematic and computational analysis of this vast amount of data provides understanding and insight into many aspects of biological processes. Recently, there has been a growing interest in classification of patient samples based on these gene expressions. The main challenge here is the overwhelming number of genes relative to the number of available training samples in the data set, and many of these genes are irrelevant for classification and have negative effect on the accuracy of the classifier. The choice of genes affects several aspects of classification: accuracy, required learning time, cost, and number of training samples needed. In this paper, we propose a new Probabilistic Model Building Genetic Algorithm (PMBGA) for the identification of informative genes for molecular classification and present our unbiased experimental results on three bench-mark data sets.
---
paper_title: Estimation of Distribution Algorithms as Logistic Regression Regularizers of Microarray Classifiers

paper_content:

Objectives: The “large k (genes), small N (samples)” phenomenon complicates the problem of microarray classification with logistic regression. The indeterminacy of the maximum likelihood solutions, multicollinearity of predictor variables and data over-fitting cause unstable parameter estimates. Moreover, computational problems arise due to the large number of predictor (genes) variables. Regularized logistic regression excels as a solution. However, the difficulties found here involve an objective function hard to be optimized from a mathematical viewpoint and a careful required tuning of the regularization parameters. Methods: Those difficulties are tackled by introducing a new way of regularizing the logistic regression. Estimation of distribution algorithms (EDAs), a kind of evolutionary algorithms, emerge as natural regularizers. Obtaining the regularized estimates of the logistic classifier amounts to maximizing the likelihood function via our EDA, without having to be penalized. Likelihood penalties add a number of difficulties to the resulting optimization problems, which vanish in our case. Simulation of new estimates during the evolutionary process of EDAs is performed in such a way that guarantees their shrinkage while maintaining their probabilistic dependence relationships learnt. The EDA process is embedded in an adapted recursive feature elimination procedure, thereby providing the genes that are best markers for the classification. Results: The consistency with the literature and excellent classification performance achieved with our algorithm are illustrated on four microarray data sets: Breast , Colon , Leukemia and Prostate . Details on the last two data sets are available as supplementary material. Conclusions: We have introduced a novel EDA-based logistic regression regularizer. It implicitly shrinks the coefficients during EDA evolution process while optimizing the usual likelihood function. The approach is combined with a gene subset selection procedure and automatically tunes the required parameters. Empirical results on microarray data sets provide sparse models with confirmed genes and performing better in classification than other competing regularized methods.
---
paper_title: Obtaining biclusters in microarrays with population-based heuristics

paper_content:

In this article, we shall analyze the behavior of population-based heuristics for obtaining biclusters from DNA microarray data. More specifically, we shall propose an evolutionary algorithm, an estimation of distribution algorithm, and several memetic algorithms that differ in the local search used. ::: ::: In order to analyze the effectiveness of the proposed algorithms, the freely available yeast microarray dataset has been used. The results obtained have been compared with the algorithm proposed by Cheng and Church. ::: ::: Both in terms of the computation time and the quality of the solutions, the comparison reveals that a standard evolutionary algorithm and the estimation of distribution algorithm offer an efficient alternative for obtaining biclusters.
---
paper_title: Biclustering of Expression Data

paper_content:

An efficient node-deletion algorithm is introduced to find submatrices in expression data that have low mean squared residue scores and it is shown to perform well in finding co-regulation patterns in yeast and human. This introduces "biclustering’, or simultaneous clustering of both genes and conditions, to knowledge discovery from expression data. This approach overcomes some problems associated with traditional clustering methods, by allowing automatic discovery of similarity based on a subset of attributes, simultaneous clustering of genes and conditions, and overlapped grouping that provides a better representation for genes with multiple functions or regulated by many factors.
---
paper_title: Inducing Pairwise Gene Interactions from Time-Series Data by EDA Based Bayesian Network

paper_content:

Recently a variety of high throughput experimental techniques, such as DNA microarray, are opening system-level perspectives of living organisms on molecular level. Inferring gene-gene interactions from time series data generated from these technologies is an important computational method to help us to understand the system behavior of living organisms. The Bayesian network (BN), which is a graph-based representation of a joint probability distribution that captures properties of conditional independence between variables, is a desirable tool. However, how to construct appropriate BNs that best fit the data profile is very difficult since the number of BNs on n variables is the super-exponential of n. To avert the combinational explosion, in this paper, we use estimation of distribution algorithms (EDAs) to search the space. Also, in order to generate meaningful individuals, we also propose depth-first search method to cut circles in the graphs. We have tested our method on cell-cycle gene expression data and found that it can not only discover some existing relationships in other literatures and gene ontology, but also reveal some previously unknown interactions
---
paper_title: Detecting reliable gene interactions by a hierarchy of Bayesian network classifiers

paper_content:

The main purpose of a gene interaction network is to map the relationships of the genes that are out of sight when a genomic study is tackled. DNA microarrays allow the measure of gene expression of thousands of genes at the same time. These data constitute the numeric seed for the induction of the gene networks. In this paper, we propose a new approach to build gene networks by means of Bayesian classifiers, variable selection and bootstrap resampling. The interactions induced by the Bayesian classifiers are based both on the expression levels and on the phenotype information of the supervised variable. Feature selection and bootstrap resampling add reliability and robustness to the overall process removing the false positive findings. The consensus among all the induced models produces a hierarchy of dependences and, thus, of variables. Biologists can define the depth level of the model hierarchy so the set of interactions and genes involved can vary from a sparse to a dense set. Experimental results show how these networks perform well on classification tasks. The biological validation matches previous biological findings and opens new hypothesis for future studies
---
paper_title: Theory for the folding and stability of globular proteins

paper_content:

Using lattice statistical mechanics, we develop theory to account for the folding of a heteropolymer molecule such as a protein to the globular and soluble state. Folding is assumed to be driven by the association of solvophobic monomers to avoid solvent and opposed by the chain configurational entropy. Theory predicts a phase transition as a function of temperature or solvent character. Molecules that are too short or too long or that have too few solvophobic residues are predicted not to fold. Globular molecules should have a largely solvophobic core, but there is an entropic tendency for some residues to be "out of place", particularly in small molecules. For long chains, molecules comprised of globular domains are predicted to be ther- modynamically more stable than spherical molecules. The number of accessible conformations in the globular state is calculated to be an exceedingly small fraction of the number available to the random coil. Previous estimates of this number, which have motivated kinetic theories of folding, err by many tens of orders of magnitude.
---
paper_title: The evolutionary landscape of functional model proteins

paper_content:

To study the distinct influences of structure and function on evolution, we propose a minimalist model for proteins with binding pockets, called functional model proteins, based on a shifted-HP model on a two-dimensional square lattice. These model proteins are not maximally compact and contain an empty lattice site surrounded by at least three nearest neighbors, thus providing a binding pocket. Functional model proteins possess a unique native state, cooperative folding and tolerance to mutation. Due to the explicit functionality in these models (by design), we have been able to explore their fitness or evolutionary landscapes, as characterized by the size and distribution of homologous families and by the complexity of the inter-relatedness of the functional model proteins. Mindful that these minimalist models are highly idealized and two-dimensional, functional model proteins should nevertheless provide a useful means for exploring the constraints of maintaining structure and function on the evolution of proteins.
---
paper_title: Automated alphabet reduction method with evolutionary algorithms for protein structure prediction

paper_content:

This paper focuses on automated procedures to reduce the dimensionality ofprotein structure prediction datasets by simplifying the way in which the primary sequence of a protein is represented. The potential benefits ofthis procedure are faster and easier learning process as well as the generationof more compact and human-readable classifiers.The dimensionality reduction procedure we propose consists on the reductionof the 20-letter amino acid (AA) alphabet, which is normally used to specify a protein sequence, into a lower cardinality alphabet. This reduction comes about by a clustering of AA types accordingly to their physical and chemical similarity. Our automated reduction procedure is guided by a fitness function based on the Mutual Information between the AA-based input attributes of the dataset and the protein structure featurethat being predicted. To search for the optimal reduction, the Extended Compact Genetic Algorithm (ECGA) was used, and afterwards the results of this process were fed into (and validated by) BioHEL, a genetics-based machine learningtechnique. BioHEL used the reduced alphabet to induce rules forprotein structure prediction features. BioHEL results are compared to two standard machine learning systems. Our results show that it is possible to reduce the size of the alphabet used for prediction fromtwenty to just three letters resulting in more compact, i.e. interpretable,rules. Also, a protein-wise accuracy performance measure suggests that the loss of accuracy acrued by this substantial alphabet reduction is not statistically significant when compared to the full alphabet.
---
paper_title: Protein Folding in Simplified Models With Estimation of Distribution Algorithms

paper_content:

Simplified lattice models have played an important role in protein structure prediction and protein folding problems. These models can be useful for an initial approximation of the protein structure, and for the investigation of the dynamics that govern the protein folding process. Estimation of distribution algorithms (EDAs) are efficient evolutionary algorithms that can learn and exploit the search space regularities in the form of probabilistic dependencies. This paper introduces the application of different variants of EDAs to the solution of the protein structure prediction problem in simplified models, and proposes their use as a simulation tool for the analysis of the protein folding process. We develop new ideas for the application of EDAs to the bidimensional and tridimensional (2-d and 3-d) simplified protein folding problems. This paper analyzes the rationale behind the application of EDAs to these problems, and elucidates the relationship between our proposal and other population-based approaches proposed for the protein folding problem. We argue that EDAs are an efficient alternative for many instances of the protein structure prediction problem and are indeed appropriate for a theoretical analysis of search procedures in lattice models. All the algorithms introduced are tested on a set of difficult 2-d and 3-d instances from lattice models. Some of the results obtained with EDAs are superior to the ones obtained with other well-known population-based optimization algorithms.
---
paper_title: ENPDA: an evolutionary structure-based de novo peptide design algorithm

paper_content:

One of the goals of computational chemists is to automate the de novo design of bioactive molecules. Despite significant advances in computational approaches to ligand design and binding energy evaluation, novel procedures for ligand design are required. Evolutionary computation provides a new approach to this design endeavor. We propose an evolutionary tool for de novo peptide design, based on the evaluation of energies for peptide binding to a user-defined protein surface patch. Special emphasis has been placed on the evaluation of the proposed peptides, leading to two different evaluation heuristics. The software developed was successfully tested on the design of ligands for the proteins prolyl oligopeptidase, p53, and DNA gyrase.
---
paper_title: Population Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitve Learning

paper_content:

Genetic algorithms (GAs) are biologically motivated adaptive systems which have been used, with varying degrees of success, for function optimization. In this study, an abstraction of the basic genetic algorithm, the Equilibrium Genetic Algorithm (EGA), and the GA in turn, are reconsidered within the framework of competitive learning. This new perspective reveals a number of different possibilities for performance improvements. This paper explores population-based incremental learning (PBIL), a method of combining the mechanisms of a generational genetic algorithm with simple competitive learning. The combination of these two methods reveals a tool which is far simpler than a GA, and which out-performs a GA on large set of optimization problems in terms of both speed and accuracy. This paper presents an empirical analysis of where the proposed technique will outperform genetic algorithms, and describes a class of problems in which a genetic algorithm may be able to perform better. Extensions to this algorithm are discussed and analyzed. PBIL and extensions are compared with a standard GA on twelve problems, including standard numerical optimization functions, traditional GA test suite problems, and NP-Complete problems.
---
paper_title: Protein Folding in 2-Dimensional Lattices with Estimation of Distribution Algorithms

paper_content:

This paper introduces a new type of evolutionary computation algorithm based on probability distributions for the solution of two simplified protein folding models. The relationship of the introduced algorithm with previous evolutionary methods used for protein folding is discussed. A number of experiments for difficult instances of the models under analysis is presented. For the instances considered, the algorithm is shown to outperform previous evolutionary optimization methods.
---
paper_title: Side chain placement using estimation of distribution algorithms

paper_content:

Objective: This paper presents an algorithm for the solution of the side chain placement problem. Methods and materials: The algorithm combines the application of the Goldstein elimination criterion with the univariate marginal distribution algorithm (UMDA), which stochastically searches the space of possible solutions. The suitability of the algorithm to address the problem is investigated using a set of 425 proteins. Results: For a number of difficult instances where inference algorithms do not converge, it has been shown that UMDA is able to find better structures. Conclusions: The results obtained show that the algorithm can achieve better structures than those obtained with other state-of-the-art methods like inference-based techniques. Additionally, a theoretical and empirical analysis of the computational cost of the algorithm introduced has been presented.
---
paper_title: Combining variable neighborhood search and estimation of distribution algorithms in the protein side chain placement problem

paper_content:

The aim of this work is to introduce several proposals for combining two metaheuristics: variable neighborhood search (VNS) and estimation of distribution algorithms (EDAs). Although each of these metaheuristics has been previously hybridized in several ways, this paper constitutes the first attempt to combine both optimization methods. ::: ::: The different ways of combining VNS and EDAs will be classified into three groups. In the first group, we will consider combinations where the philosophy underlying VNS is embedded in EDAs. Considering different neighborhood spaces (points, populations or probability distributions), we will obtain instantiations for the approaches in this group. The second group of algorithms is obtained when probabilistic models (or any other machine learning paradigm) are used in order to exploit the good and bad shakes of the randomly generated solutions in a reduced variable neighborhood search. The last group of algorithms contains the results of alternating VNS and EDAs. ::: ::: An application of the first approach is presented in the protein side chain placement problem. The results obtained show the superiority of the hybrid algorithm in comparison with EDAs and VNS.
---
paper_title: BOA: The Bayesian Optimization Algorithm

paper_content:

In this paper, an algorithm based on the concepts of genetic algorithms that uses an estimation of a probability distribution of promising solutions in order to generate new candidate solutions is proposed. To estimate the distribution, techniques for modeling multivariate data by Bayesian networks are used. The proposed algorithm identifies, reproduces and mixes building blocks up to a specified order. It is independent of the ordering of the variables in the strings representing the solutions. Moreover, prior information about the problem can be incorporated into the algorithm. However, prior information is not essential. Preliminary experiments show that the BOA outperforms the simple genetic algorithm even on decomposable functions with tight building blocks as a problem size grows.
---
paper_title: The role of a priori information in the minimization of contact potentials by means of estimation of distribution algorithms

paper_content:

Directed search methods and probabilistic approaches have been used as two alternative ways for computational protein design. This paper presents a hybrid methodology that combines features from both approaches. Three estimation of distribution algorithms are applied to the solution of a protein design problem by minimization of contact potentials. The combination of probabilistic models able to represent probabilistic dependencies with the use of information about residues interactions in the protein contact graph is shown to improve the efficiency of search for the problems evaluated.
---
paper_title: The mixture of trees Factorized Distribution Algorithm

paper_content:

This paper introduces a Factorized Distribution Algorithm based on a mixture of trees distribution. The probabilistic model and the learning algorithm used differs to previous uses of probabilistic modeling in the context of Evolutionary Computation. Preliminary results show the algorithm is competitive, and some times superior to other Factorized Distribution Algorithms. We also illustrate how particular features of the search space can be employed during the search by conveniently selecting the mixture of trees parameters.
---

Title: A Review of Estimation of Distribution Algorithms in Bioinformatics

Section 1: Introduction
Description 1: Introduce evolutionary optimization techniques and the emergence of estimation of distribution algorithms (EDAs) in bioinformatics.

Section 2: Estimation of Distribution Algorithms
Description 2: Explain what EDAs are, including their process and pseudocode.

Section 3: Characteristics of EDAs
Description 3: Describe the key characteristics of EDAs and how they differ from other evolutionary algorithms.

Section 4: A Taxonomy of EDAs
Description 4: Present a detailed taxonomy of different types of EDAs based on the complexity of probabilistic models and other factors.

Section 5: Potential of EDAs in Bioinformatics
Description 5: Discuss the potential applications and benefits of EDAs in solving bioinformatics problems.

Section 6: EDAs in Genomics
Description 6: Review the application of EDAs to various genomic problems, including gene structure analysis and gene expression analysis.

Section 7: Gene Structure Analysis
Description 7: Explain the use of EDAs for predicting gene structures and selecting relevant features for classification tasks.

Section 8: Gene Expression Analysis
Description 8: Describe how EDAs are applied to gene expression data, including classification and clustering tasks.

Section 9: Classification of DNA Microarray Data
Description 9: Discuss the role of EDAs in identifying relevant gene subsets for microarray data classification.

Section 10: Clustering of DNA Microarray Data
Description 10: Explain how EDAs are used for clustering gene expression data and biclustering.

Section 11: Inference of Genetic Networks
Description 11: Review the application of EDAs for inferring gene-gene interactions and genetic networks.

Section 12: EDA Approaches
Description 12: Categorize EDAs based on the complexity of the protein models they use and the types of protein-related problems they address.

Section 13: Conclusion
Description 13: Summarize the findings of the review, emphasizing the efficiency and accuracy of EDAs and suggesting future research directions.