Ant Colony Optimization

Our paper on the use of ant colony optimization (ACO) for the genetic analysis of epistasis has been accepted for presentation and publication as part of the 2009 Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics (EvoBIO'09) Conference in Germany. We use ACO as a simple estimation of distribution algorithm (EDA) wrapper around MDR. The EDA-ACO algorithm is included in our open-source MDR software available from here. The complete list of accepted papers at the conference can be found here.

Greene, C.S., Gilmore, J., Kiralis, J., Andrews, P.C., Moore, J.H. Optimal use of expert knowledge in ant colony optimization for the analysis of epistasis in human disease. Lecture Notes in Computer Science, in press (2009).

Now that the availability of chip-based technology has transformed human genetics and made routine the measurement of thousands of DNA sequence variations from across the human genome, an informatics challenge arises. This challenge is the identification of combinations
of interacting DNA sequence variations predictive of common diseases. We have previously developed Multifactor Dimensionality Reduction (MDR), a method capable of detecting these interactions, but an exhaustive MDR analysis is exponential in time complexity and thus
unsuitable for an interaction analysis of genome-wide datasets. Therefore we look to stochastic search approaches to find a suitable wrapper for the analysis of large amounts of genetic variation. We have previously shown that an ant colony optimization (ACO) framework can be successfully applied to human genetics when expert knowledge is included. We have integrated an ACO stochastic search wrapper into the open source MDR software package. In this wrapper we also introduce a scaling method based on an exponential distribution function with a single user-adjustable parameter. Here we obtain expert knowledge from Tuned ReliefF (TuRF), a method capable of detecting attribute interactions in the absence of main effects, and perform a power analysis on this implementation over different parameter settings. We show that the expert knowledge distribution parameter, the retention factor, and the weighting of expert knowledge significantly affect the power of the method.