DESeeker: Detecting Epistatic Interactions Using a Two-Stage Differential Evolution Algorithm

Boxin Guan, Yuhai Zhao, Yuan LiIEEE Access 2019 · OpenReview

Abstract

Epistatic interactions are generally defined as the interactions between different single-nucleotide polymorphisms (SNPs). Identifying epistatic interactions is important for determining the individual susceptibility of complex diseases. In large-scale association studies, finding epistatic interactions in the large volume of SNP data is a challenging issue. Since the current search approaches are confronted with the serious problem of computational burden, developing an efficient algorithm for dealing with the intensive computing problem would be significant. In this paper, a novel differential evolution-based algorithm DESeeker is proposed to detect epistatic interactions. DESeeker, combined with a local search and a self-adapting parameter tuning strategy, employs a two-stage design of DE to enhance its search capability. DESeeker is compared with the other recent algorithms on a set of simulated datasets and a real biological dataset. The experimental results on the simulated datasets show that the proposed algorithm is superior to the other compared algorithms in terms of detection power. The discovery of the real biological dataset demonstrates that the proposed algorithm is promising for practical disease prognosis.

Introduction

Genome-Wide Association Studies (GWAS) typically focus on identifying single-locus SNPs (Single Nucleotide Polymorphisms) that correlate with specific diseases. However, complex conditions such as diabetes, breast cancer, and rheumatoid arthritis are often driven by epistasis—a phenomenon where the effect of one genetic mutation is contingent upon the presence of others.

The primary challenge in detecting these interactions is the sheer scale of the search space. For a dataset containing 100,000 SNPs, there are approximately 5 billion possible pairwise combinations. Exhaustive search methods are computationally prohibitive, while existing heuristic approaches often lack the necessary detection power to identify subtle interactions amidst high-dimensional noise.

Methodology

The proposed algorithm, DESeeker, utilizes the Differential Evolution (DE) metaheuristic, a population-based optimization technique that evolves solutions through mutation, crossover, and selection. DESeeker introduces three primary innovations to the standard DE framework:

  1. Two-Stage Search Strategy: Rather than searching for SNP pairs directly, the first stage identifies larger SNP clusters (e.g., groups of 6). This approach captures SNPs with strong marginal effects that might be overlooked in pairwise searches. The second stage then performs an exhaustive search within these high-performing clusters to pinpoint specific epistatic pairs.
  2. Hill Climbing Local Search (HCLS): To prevent the algorithm from converging on local optima, DESeeker incorporates a local search mechanism that explores the immediate neighborhood of the best-performing vectors in each generation.
  3. Self-Adapting Parameters: DESeeker automatically tunes critical parameters, such as the scaling factor ($F$) and crossover rate ($CR$), by evolving them alongside the genetic data. This allows the algorithm to adapt to the specific characteristics of the dataset without manual intervention.

The "fitness" of each candidate solution is evaluated using a $\chi^2$ (chi-square) test, measuring the statistical association between SNP combinations and the disease state.

Datasets

The algorithm was validated using both synthetic and real-world data:

  • Simulated Datasets: Generated via GAMETES 2.0, these included Multiplicative, Threshold, and Concrete epistasis models with varying allele frequencies.
  • Biological Data: A Rheumatoid Arthritis (RA) dataset comprising 3,503 individuals and 332,831 SNPs.

Results and Discussion

DESeeker demonstrated superior performance across multiple benchmarks. In simulated environments, it consistently outperformed five major algorithms: SNPRuler, BOOST, AntEpiSeeker, IEACO, and standard DE. In several test scenarios, DESeeker achieved 100% detection power, significantly surpassing the 60-80% range of competing methods.

Comparison of detection power across different Minor Allele Frequencies (MAF) for various algorithms.

The effectiveness of the "searching big to find small" strategy was confirmed, as SNPs involved in epistasis often exhibit marginal effects that are more detectable when markers are grouped. Furthermore, the integration of global DE search with local Hill Climbing refinement provided a robust balance between exploration and exploitation. On the real-world RA dataset, DESeeker successfully identified interactions involving the TNFAIP3, OLIG3, and CD40 genes, all of which have established biological links to the disease.

Conclusion

DESeeker offers a powerful and computationally efficient solution for detecting epistatic interactions in large-scale genomic studies. By combining a two-stage search strategy with self-adapting parameters and local search refinement, it achieves high detection power and precision. Future research will focus on incorporating prior biological knowledge, such as protein-protein interaction networks, and extending the algorithm to detect higher-order interactions (e.g., 3-way or 4-way epistasis).

Summary updated

Abstract

Epistatic interactions are generally defined as the interactions between different single-nucleotide polymorphisms (SNPs). Identifying epistatic interactions is important for determining the individual susceptibility of complex diseases. In large-scale association studies, finding epistatic interactions in the large volume of SNP data is a challenging issue. Since the current search approaches are confronted with the serious problem of computational burden, developing an efficient algorithm for dealing with the intensive computing problem would be significant. In this paper, a novel differential evolution-based algorithm DEseeker is proposed to detect epistatic interactions. DEseeker, combined with a local search and a self-adapting parameter tuning strategy, employs a two-stage design of DE to enhance its search capability. DEseeker is compared with the other recent algorithms on a set of simulated datasets and a real biological dataset. The experimental results on the simulated datasets show that the proposed algorithm is superior to the other compared algorithms in terms of detection power. The discovery of the real biological dataset demonstrates that the proposed algorithm is promising for practical disease prognosis.
BibTeX
@inproceedings{guan2019deseeker,
  author = {Boxin Guan and Yuhai Zhao and Yuan Li},
  title = {{DESeeker: Detecting Epistatic Interactions Using a Two-Stage Differential Evolution Algorithm}},
  booktitle = {IEEE Access},
  year = {2019},
  url = {https://openreview.net/forum?id=cFKOCzfZpz1},
}
Figure