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. Heredity (2014) 112, 666-674; doi:10.1038/hdy.2014 published online 19 February 2014 Keywords: single-nucleotide polymorphism; epistatic interactions; dimensionality reduction; cuckoo search INTRODUCTION One source of complexity in biological systems is due to rich interactions among the components (Weng et al., 1999; Hlavacek and Faeder, 2009 ). The advent of high-throughput genotyping and sequencing technologies has enabled the measurement of millions of single-nucleotide polymorphisms (SNPs)-the commonest type of genetic variants-in an individual. This has paved the way for understanding the genetic architecture of common diseases, but has also given rise to challenges in developing efficient methods for identifying of interactions (epistasis) among genetic variants. Several methods have been developed for analyzing genetic data that focus on epistatic interactions and include frequentist and Bayesian statistical methods and computational methods (Ritchie et al., 2001; Zhang and Xu, 2005; Zhao and Xiong, 2006; Ferreira et al., 2007; Zhang and Liu 2007; Gayan et al., 2008; Li et al., 2008b; Park and Hastie, 2008; Jung et al., 2009; Miller et al., 2009; Wang, 2009; Wu et al., 2009) . A key challenge is the large number of statistical tests that have to be performed in epistasis testing especially in genome-wide association (GWA) studies that measure a large number of SNPs (Bellman and Kalaba, 1959; Steen, 2011) . Moreover, high-dimensionality arising from multi-locus combinations, the relatively small sample size and the resulting data sparsity lead to lack of power in data mining methods (Cordell, 2009; Steen, 2011) . To address the challenge of high-dimensionality, several feature selection methods have been applied to GWA data as a first step in identifying informative SNPs (Dube et al., 2007 , Saeys et al., 2007 . Feature selection methods can be broadly grouped into two categories that include filter and wrapper methods (Freitas, 2002) . In addition, feature selection methods that leverage biological knowledge relevant to SNPs, such as INTERSNP and Biofilter, have been developed as alternatives to filter and wrapper methods that do not sue such knowledge (Bush et al., 2009; Herold et al., 2009) . INTERSNP is a time-efficient approach to select combinations of SNPs for a further interaction analysis based on a priori information obtained from either statistical evidence of single-marker association or biologic/genetic relevance information sources (Herold et al., 2009) . Similarly, Biofilter is a systematic knowledge-based approach to produce SNP models by integrating multiple genetic databases. This approach can be implemented with a variety of techniques such as logistic regression, classification and regression trees (Bush et al., 2009) . The filter methods, typically, assess the quality of each attribute (such as a SNP) using a selection criterion. These types of feature selection methods have the advantage of being fast, but are often criticized for their inability to select relevant attributes involved in a significant interaction effect on the susceptibility of a disease or trait but that would not show sufficient individual effects for selection. Wrapper approaches, on the other hand, attempt to evaluate subsets of attributes based on sample classification accuracy. In contrast to filter methods, wrapper methods allow for all attributes to be retained and use a selection probability (Moore et al., 2010). As a result, no attribute is eliminated from the analysis. There are different types of wrapper methods and among them evolutionary computing algorithms such as the genetic algorithm (GA) and the evolution strategy methods have attracted much attention for stochastic search of epistatic interactions (Li et al., 2001; Ooi and Tan, 2003; Moore et al., 2004; Shah and Kusiak, 2004; Jirapech-Umpai and Aitken, 2005) . Recently, a GA-based hybrid algorithm called genetic ensemble (GE) was proposed by ; this method relies on a combination of an ensemble of classifiers and a multi-objective GA (Zhang and Yang 2008; . The GE algorithm was shown to outperform other GA-based methods (Zhang and Yang, 2008) . However, ensemble methods such as GE require diverse and accurate classifiers to achieve better accuracy, and identifying an efficient set of classifiers can be difficult (Dietterich, 2000) . Selecting appropriate classifiers for different data sets with different number of attributes and samples, and configuring parameters properly for each classifier is challenging. Moreover, ensemble methods are likely to be more computationally expensive than methods that use a single classifier. Finally, despite the superior performance of GAs in comparison with gradient-based optimization methods, they are sensitive to parameter settings, exhibiting varying performance for different configurations of parameters such as population size, crossover frequency and mutation rate (Kumar and Chakarverty, 2011) . Motivated by evolutionary algorithms, we develop and evaluate a fast stochastic search method named cuckoo search epistasis (CSE) for identifying significant epistatic interactions in GWA studies. CSE differs from wrapper feature selection methods in that CSE does not search for a subset of informative attributes that are further analyzed for epistasis, but performs stochastic search of epistasis with no classification or training/prediction scheme. CSE used a new and relatively fast evolutionary algorithm called cuckoo search (CS), which performs better than other evolutionary algorithms. In addition, CSE uses a computationally efficient Bayesian score to evaluate combinations of SNPs for association with the phenotype. We compare CSE's ability to identify epistatic interactions to that of multifactorial dimensionality reduction (MDR) and Bayesian epistasis association mapping (BEAM) using synthetic data sets. We also apply CSE to an Alzheimer's disease GWA data set that contains over 300 000 SNPs. This section provides background information on Bayesian combinatorial method (BCM), which uses a Bayesian statistic for measuring genetic interactions. The CSE method uses the Bayesian statistic of BCM to evaluate combinations of SNPs. In addition, brief descriptions on MDR and BEAM are also provided.
The method reported in REF combines Bayesian scoring with an evolutionary-based heuristic approach; it allowed to process around 1,400 subjets and 300,000 SNPs.
Cuckoo search epistasis: a new method for exploring significant genetic interactions
Heredity
Heredity
Biology Medicine