Cuckoo search epistasis: a new method for exploring significant genetic interactions

Abstract

The advent of high-throughput sequencing technology has resulted in the ability to measure millions of single-nucleotide polymorphisms (SNPs) from thousands of individuals. Although these high-dimensional data have paved the way for better understanding of the genetic architecture of common diseases, they have also given rise to challenges in developing computational methods for learning epistatic relationships among genetic markers. We propose a new method, named cuckoo search epistasis (CSE) for identifying significant epistatic interactions in population-based association studies with a case-control design. This method combines a computationally efficient Bayesian scoring function with an evolutionary-based heuristic search algorithm, and can be efficiently applied to high-dimensional genome-wide SNP data. The experimental results from synthetic data sets show that CSE outperforms existing methods including multifactorial dimensionality reduction and Bayesian epistasis association mapping. In addition, on a real genome-wide data set related to Alzheimer's disease, CSE identified SNPs that are consistent with previously reported results, and show the utility of CSE for application to genome-wide data.

Figure 1

An example of genotype–phenotype table with two SNPs and a binary phenotype. This figure summarizes the genotype and phenotype data for a two-way interaction model with two SNPs. BCM assumes a binomial distribution for any combination of the SNP1 and SNP2 values, that is, each column of this table follows a binomial distribution. Thus, P(Data|M, θ_c) is obtained by multiplying nine independent binomial distributions.

Figure 2

Pseudocode for modified CS.

Figure 3

Flowchart showing the main steps in CSE.

Figure 4

Pseudocode for CSE method.

Figure 5

Powers obtained by three epistasis detection methods (CSE, MDR and BEAM) on synthetic data containing two interacting SNPs. The figure gives the power of the methods for three sample sizes of 1600, 800 and 400 with equal numbers of cases and controls. For each sample size, 20 penetrance functions with two MAFs and two heritability levels are examined. For each penetrance model, 100 data sets with 1000 SNPs are examined. The highest scoring interactions were evaluated using CSE, MDR and BEAM for each data set. Finally, the power was estimated as the number of correctly detected interacting SNPs divided by the number of SNPs in the data set.