A review of estimation of distribution algorithms in bioinformatics

Rubén Armañanzas, Iñaki Inza, Roberto Santana, Yvan Saeys, Jose Luis Flores, José Antonio Lozano, Yves Van de Peer, Rosa Blanco, Víctor Robles, Concha Bielza, Pedro LarrañagaBioData Min 2008 · OpenReview

TL;DR

This paper reviews Estimation of Distribution Algorithms (EDAs) as a powerful alternative to traditional Genetic Algorithms (GAs) for solving complex, high-dimensional optimization problems in bioinformatics. EDAs leverage probabilistic models to guide their search, offering advantages in scalability and interpretability, and have shown promise in areas like gene structure analysis, gene expression analysis, and protein structure prediction.

What Problem Does This Paper Address?

Bioinformatics is awash with high-dimensional optimization problems, stemming from the explosion of data generated by modern high-throughput technologies. Traditional optimization techniques often struggle with these vast search spaces, getting stuck in local optima or requiring prohibitive computational resources. Genetic Algorithms (GAs) emerged as a popular heuristic solution, but they can be parameter-sensitive and sometimes lack transparency. This paper addresses the need for more efficient, scalable, and interpretable optimization methods in bioinformatics by reviewing Estimation of Distribution Algorithms (EDAs), a class of evolutionary algorithms that use probabilistic models to guide their search.

Methods

The core of EDAs lies in their probabilistic modeling approach. Instead of relying on crossover and mutation operators like GAs, EDAs build a probabilistic model from the promising solutions found so far. This model then generates new candidate solutions, effectively learning the structure of the search space. The paper categorizes EDAs based on the complexity of their probabilistic models:

  • Univariate EDAs: Assume variables are independent, factorizing the joint probability as a product of univariate marginal probabilities. These are the simplest and fastest.
  • Bivariate EDAs: Can represent low-order dependencies between variables, often using fast learning algorithms.
  • Multivariate EDAs: Factorize the joint probability distribution using statistics of order greater than two, allowing for the representation of more complex interactions but requiring more sophisticated learning processes.

The paper also discusses two main learning approaches: "structure+parameter learning" (where both the model structure and its parameters are learned) and "parameter learning" (where a fixed model structure is used).

Datasets

The paper is a review and does not introduce new datasets. Instead, it discusses applications of EDAs to various bioinformatics problems, referencing existing datasets used in those studies. Examples include:

  • Gene structure analysis: Applications often use benchmark datasets for gene prediction and splice site recognition.
  • Gene expression analysis: Datasets from DNA microarray experiments are frequently used for classification, clustering, and biclustering tasks.
  • Protein structure prediction and design: Problems often involve simplified protein models or real protein sequences, with energy functions serving as the evaluation metric.

Key Insights and Ideas

  • Probabilistic modeling as a paradigm shift: EDAs move beyond simple recombination and mutation by learning the underlying distribution of good solutions, offering a more principled way to guide the search.
  • Scalability and interpretability: EDAs are often more scalable to high-dimensional problems than GAs and their probabilistic models can offer insights into the problem structure and feature interactions.
  • Flexibility in model choice: The taxonomy of EDAs highlights that the choice of probabilistic model (univariate, bivariate, multivariate) can be tailored to the complexity of the problem's dependencies.
  • Potential for prior knowledge integration: EDAs can be designed to incorporate prior biological knowledge into their probabilistic models, potentially reducing search cost and improving accuracy.
  • Reusability of learned models: Information gathered by EDA models from one problem instance might be reusable for other similar problems, paving the way for more efficient bioinformatics applications.

Key Results

The paper reviews numerous studies demonstrating the effectiveness of EDAs across various bioinformatics domains:

  • Gene structure analysis: EDA-based feature subset selection (FSS) has been shown to improve the performance of gene prediction models, particularly for splice site recognition, and provides insights into feature relevance.
  • Gene expression analysis: EDAs have achieved competitive results in gene selection for cancer classification and have been successfully applied to gene clustering and biclustering tasks, often outperforming traditional methods.
  • Protein structure prediction and design: EDAs have demonstrated superior performance in solving simplified protein folding problems and side chain placement tasks, sometimes outperforming other evolutionary algorithms and even achieving optimal solutions where others fail. They have also been used to generate potential peptide ligands and address protein design problems by minimizing contact potentials.

Limitations and Future Work

  • Model complexity vs. computational cost: A key trade-off exists between the complexity of the probabilistic model (which can capture more intricate dependencies) and the computational cost of learning and sampling from it.
  • Choice of EDA: Selecting the "best" EDA for a given problem is not always straightforward and depends on factors like problem dimensionality, representation type, and the nature of variable interactions.
  • Future Research: The authors highlight the need for adapting and applying multivariate EDA models to efficiently handle the huge dimensionality of current bioinformatic problems. They also suggest that explicitly inspecting probabilistic relationships among variables could lead to improved accuracy and the generation of novel biological hypotheses. The reusability of learned EDA models across problem instances is another promising avenue for future research.

Summary updated

Abstract

Evolutionary search algorithms have become an essential asset in the algorithmic toolbox for solving high-dimensional optimization problems in across a broad range of bioinformatics problems. Genetic algorithms, the most well-known and representative evolutionary search technique, have been the subject of the major part of such applications. Estimation of distribution algorithms (EDAs) offer a novel evolutionary paradigm that constitutes a natural and attractive alternative to genetic algorithms. They make use of a probabilistic model, learnt from the promising solutions, to guide the search process. In this paper, we set out a basic taxonomy of EDA techniques, underlining the nature and complexity of the probabilistic model of each EDA variant. We review a set of innovative works that make use of EDA techniques to solve challenging bioinformatics problems, emphasizing the EDA paradigm's potential for further research in this domain.
BibTeX
@inproceedings{armananzas2008review,
  author = {Rubén Armañanzas and Iñaki Inza and Roberto Santana and Yvan Saeys and Jose Luis Flores and José Antonio Lozano and Yves Van de Peer and Rosa Blanco and Víctor Robles and Concha Bielza and Pedro Larrañaga},
  title = {{A review of estimation of distribution algorithms in bioinformatics}},
  booktitle = {BioData Min},
  year = {2008},
  url = {https://openreview.net/forum?id=mRMLJe4k4De},
}
Figure