Fast Genome-Wide Epistasis Analysis Using Ant Colony Optimization for Multifactor Dimensionality Reduction Analysis on Graphics Processing Units

摘要

Epistasis, or non-linear gene-to-gene interaction, is now thought to be at the heart of many common human diseases. A popular algorithm to detect epistasis is Multifac-tor Dimensionality Reduction (MDR), which exhaustively searches to determine an optimal classification. This exhaustive search is combinatorial in complexity and does not scale efficiently to large datasets. Ant Colony Opimization (ACO) is a technique to reduce this complexity by exploiting expert knowledge to spend more time looking at most likely candidates for the optimal classification. Graphics Processing Units (GPUs) are highly-parallel integrated circuits able to execute arbitrary code. The authors implemented ACO MDR on GPUs and compared it to both a Java ACO implementation and an exhaustive C++ implementation. The performance advantage of GPUs, combined with the added computational efficiency of a heuristic evolutionary algorithm such as ACO, allow larger scale problems to be tackled, something that is becoming critical with the advances in high throughput genome sequencing.