Genome-Wide Association Studies (GWASs), analyses that try to find a link between a given phenotype (such as a disease) and genetic markers, have been growing in popularity in the recent years. Relations between phenotypes and genotypes are not easy to identify, as most of the phenotypes are a product of the interaction between multiple genes, a phenomenon known as epistasis. Many authors have resorted to different approaches and hardware architectures in order to mitigate the exponential time complexity of the problem. However, these studies make some compromises in order to keep a reasonable execution time, such as limiting the number of genetic markers involved in the interaction, or discarding some of these markers in an initial filtering stage. This work presents MPI3SNP, a tool that implements a three-way exhaustive search for cluster architectures with the aim of mitigating the exponential growth of the run-time. Modern cluster solutions usually incorporate GPUs. Thus, MPI3SNP includes implementations for both multi-CPU and multi-GPU clusters. To contextualize the performance achieved, MPI3SNP is able to analyze an input of 6300 genetic markers and 3200 samples in less than 6 min using 768 CPU cores or 4 min using 8 NVIDIA K80 GPUs. The source code is available at https://github.com/chponte/mpi3snp.
CattaertTCalleMLDudekSM, et al. (2011) A detailed view on model-based multifactor dimensionality reduction for detecting gene-gene interactions in case-control data in the absence and presence of noise. Annals of Human Genetics75(1): 78–89.
2.
CordellHJ (2009) Detecting gene-gene interactions that underlie human diseases. Nature Reviews Genetics10(6): 392–404.
3.
CulverhouseR (2007) The use of the restricted partition method with case-control data. Human Heredity63(2): 93–100.
4.
FangGHaznadarMWangW, et al. (2012) High-order SNP combinations associated with complex diseases: efficient discovery, statistical power and functional interactions. PLoS ONE7(4): 1–15.
5.
González-DomínguezJSchmidtB (2015) GPU-accelerated exhaustive search for third-order epistatic interactions in case-control studies. The Journal of Computational Science8: 93–100.
6.
González-DomínguezJSchmidtBKässensJC, et al. (2014) Hybrid CPU/GPU acceleration of detection of 2-SNP epistatic interactions in GWAS. In: Euro-Par 2014: European conference on parallel processing (eds SilvaFDutraISantos CostaV), Vol. 8632, Porto, Portugal, 25–29 August 2014, pp. 680–691. Cham: Springer.
7.
GoudeyBAbediniMHopperJL, et al. (2015) High performance computing enabling exhaustive analysis of higher order single nucleotide polymorphism interaction in Genome Wide Association Studies. Health Information Science and Systems3(S1): S3.
8.
GoudeyBRawlinsonDWangQ, et al. (2013) GWIS—model-free, fast and exhaustive search for epistatic interactions in case-control GWAS. BMC Genomics14(3): S10.
9.
GuiJAndrewASAndrewsP, et al. (2011) A robust multifactor dimensionality reduction method for detecting gene-gene interactions with application to the genetic analysis of bladder cancer susceptibility. Annals of Human Genetics75(1): 20–28.
10.
HemaniGTheocharidisAWeiW, et al. (2011) EpiGPU: exhaustive pairwise epistasis scans parallelized on consumer level graphics cards. Bioinformatics27(11): 1462–1465.
11.
HuXLiuQZhangZ, et al. (2010) SHEsisEpi, a GPU-enhanced genome-wide SNP-SNP interaction scanning algorithm, efficiently reveals the risk genetic epistasis in bipolar disorder. Cell Research20(7): 854–857.
12.
KässensJCGonzález-DomínguezJWienbrandtL, et al. (2014) UPC++ for bioinformatics: a case study using genome-wide association studies. In: 2014 IEEE international conference on cluster computing (CLUSTER), Madrid, Spain, 22–26 September 2014, pp. 248–256. IEEE.
13.
KässensJCWienbrandtLGonzález-DomínguezJ, et al. (2015) High-speed exhaustive 3-locus interaction epistasis analysis on FPGAs. Journal of Computational Science9: 131–136.
14.
LeemSJeongHLeeJ, et al. (2014) Fast detection of high-order epistatic interactions in genome-wide association studies using information theoretic measure. Computational Biology and Chemistry50: 19–28.
15.
LiX (2017) A fast and exhaustive method for heterogeneity and epistasis analysis based on multi-objective optimization. Bioinformatics33(18): 2829–2836.
16.
MaLRuneshaHBDvorkinD, et al. (2008) Parallel and serial computing tools for testing single-locus and epistatic SNP effects of quantitative traits in genome-wide association studies. BMC Bioinformatics9(1): 315.
17.
MaherB (2008) Personal genomes: the case of the missing heritability. Nature456(7218): 18–21.
18.
MooreJHAsselbergsFWWilliamsSM (2010) Bioinformatics challenges for genome-wide association studies. Bioinformatics26(4): 445–455.
19.
MooreJHWilliamsSM (2009) Epistasis and its implications for personal genetics. The American Journal of Human Genetics85(3): 309–320.
20.
NelsonMRKardiaSLSingCF (2001) A combinatorial partitioning method to identify multilocus genotypic partitions that predict quantitative trait variation. Genome Research11(3): 458–470.
21.
PiriyapongsaJNgamphiwCIntarapanichA, et al. (2012) iLOCi: a SNP interaction prioritization technique for detecting epistasis in genome-wide association studies. BMC Genomics13(7): S2.
22.
RitchieMDHahnLWRoodiN, et al. (2001) Multifactor-dimensionality reduction reveals high-order interactions among estrogen-metabolism genes in sporadic breast cancer. The American Journal of Human Genetics69(1): 138–147.
23.
SchüpbachTXenariosIBergmannS, et al. (2010) FastEpistasis: a high performance computing solution for quantitative trait epistasis. Bioinformatics26(11): 1468–1469.
24.
TangWWuXJiangR, et al. (2009) Epistatic module detection for case-control studies: a Bayesian model with a Gibbs sampling strategy. PLoS Genetics5(5): 1–18.
25.
TylerALAsselbergsFWWilliamsSM, et al. (2009) Shadows of complexity: what biological networks reveal about epistasis and pleiotropy. Bioessays31(2): 220–227.
26.
UptonATrellesOCornejo-GarcíaJA, et al. (2015) High-performance computing to detect epistasis in genome scale data sets. Briefings in Bioinformatics17(3): 368–379.
27.
WanXYangCYangQ, et al. (2009) MegaSNPHunter: a learning approach to detect disease predisposition SNPs and high level interactions in genome wide association study. BMC Bioinformatics10(1): 13.
28.
WanXYangCYangQ, et al. (2010) Predictive rule inference for epistatic interaction detection in genome-wide association studies. Bioinformatics26(1): 30–37.
29.
WienbrandtLKässensJCGonzález-DomínguezJ, et al. (2014) FPGA-based acceleration of detecting statistical epistasis in GWAS. Procedia Computer Science29: 220–230.
30.
XieMLiJJiangT (2012) Detecting genome-wide epistases based on the clustering of relatively frequent items. Bioinformatics28(1): 5–12.
31.
YoshizoeKTeradaATsudaK (2018) MP-LAMP: parallel detection of statistically significant multi-loci markers on cloud platforms. Bioinformatics1: 3.
32.
YungLSYangCWanX, et al. (2011) GPU-accelerated exhaustive search for third-order epistatic interactions in case-control studies. Bioinformatics27(9): 1309–1310.
33.
ZhangYLiuJS (2007) Bayesian inference of epistatic interactions in case-control studies. Nature Genetics39(9): 1167–1173.
34.
ZhouZLiuGSuL (2016) A new approach to detect epistasis utilizing parallel implementation of ant colony optimization by MapReduce framework. International Journal of Computer Mathematics93(3): 511–523.
35.
ZubenkoGSHughesHBIIIStifflerJS (2001) D10S1423 identifies a susceptibility locus for Alzheimer’s disease in a prospective, longitudinal, double-blind study of asymptomatic individuals. Molecular Psychiatry6(4): 413–419.
