Estimation of Distribution Algorithms (EDA)

Our paper on the use of simple Estimation of Distribution Algorithms (EDA) for the genome-wide genetic analysis of epistasis has been accepted for publication in Lecture Notes in Computer Science as part of the Sixth Annual Conference on Ant Colony Optimization and Swarm Intelligence (ANTS) to be held in September in Belgium. Our EDA was implemented as Ant Colony Optimization (ACO) that is inspired by the successful strategies (e.g. pheromones) that ants use to forage for food. In practice, ACO is a simple matrix of probabilities for choosing different SNPs for analysis that is updated as different solutons are evaluated. ACO was appealing for this problem because it inherently uses heuristic information or expert knowledge to update probabilities. We are in the process of adding this simple univariate EDA to the open-source MDR software package that is freely available from here. This new version (v. 2.0) will be available later this summer.

Greene CS, White BC, Moore JH. Ant colony optimization for genome-wide genetic analysis. Lecture Notes in Computer Science, in press (2008).

Abstract.

In human genetics it is now feasible to measure large numbers of DNA sequence variations across the human genome. Given current knowledge about biological networks and disease processes it seems likely that disease risk can best be modeled by interactions between biological components, which can be examined as interacting DNA sequence variations. The machine learning challenge is to effectively explore interactions in these datasets to identify combinations of variations which are predictive of common human diseases. Ant colony optimization (ACO) is a promising approach to this problem. The goal of this study is to examine the usefulness of ACO for problems in this domain and to develop a prototype of an expert knowledge guided probabilistic search wrapper. We show that an ACO approach is not successful in the absence of expert knowledge but is successful when expert knowledge is supplied through the pheromone updating rule.