A Distributed Evolutionary Framework for Large-scale SNP-SNP Interaction Detection

Capturing the complex interactions of single nucleotide polymorphisms (SNPs) is considered essential for etiological analysis in genome-wide association analysis (GWAS). Evolutionary algorithms (EAs) have been extensively adopted for SNP-SNP interaction detection. Most existing EA-based methods focus on enhancing the search ability of EA itself. However, as the scale of SNP data further increases, the exponentially growing search space gradually becomes the dominant factor leading to the performance degradation of EA-based methods. To this end, a distributed evolutionary framework based on space partitioning (SP-EF) is proposed to detect SNP-SNP interactions on large-scale datasets. Distinct from the traditional population-distributed approaches, SP-EF first partitions the entire search space into several subspaces from the perspective of data. The space partitioning strategy is non-destructive since it guarantees that each feasible solution is assigned to a specific subspace. Thereafter, each subspace is explored by an EA optimizer independently and all the subspaces are optimized in parallel. Lastly, the final output is selected from the local optima in the historical search of each subspace. SP-EF can not only cope with the heavy computational burden of SNP combination evaluation but also enhance the diversity of the population to avoid local optima. Notably, SP-EF is load-balanced and scalable since it can flexibly partition the space according to the number of available computational nodes and the problem size. To show the practicability of SP-EF, we further design a discrete fireworks algorithm (DFWA) with three problem-guided operators as an EA optimizer. Experiments on artificial and real-world datasets demonstrate that our method significantly improves search speed and search accuracy.