FAACOSE: a fast adaptive ant colony optimization algorithm for detecting SNP epistasis. (English) Zbl 1373.93185

Summary: The epistasis is prevalent in the SNP interactions. Some of the existing methods are focused on constructing models for two SNPs. Other methods only find the SNPs in consideration of one-objective function. In this paper, we present a unified fast framework integrating adaptive ant colony optimization algorithm with multiobjective functions for detecting SNP epistasis in GWAS datasets. We compared our method with other existing methods using synthetic datasets and applied the proposed method to Late-Onset Alzheimer’s Disease dataset. Our experimental results show that the proposed method outperforms other methods in epistasis detection, and the result of real dataset contributes to the research of mechanism underlying the disease.


93C40 Adaptive control/observation systems
90C59 Approximation methods and heuristics in mathematical programming
92C50 Medical applications (general)
Full Text: DOI


[1] Hirschhorn, J. N.; Daly, M. J., Genome-wide association studies for common diseases and complex traits, Nature Reviews Genetics, 6, 2, 95-108, (2005)
[2] Howie, B. N.; Donnelly, P.; Marchini, J., A flexible and accurate genotype imputation method for the next generation of genome-wide association studies, PLoS Genetics, 5, 6, (2009)
[3] Manolio, T. A.; Collins, F. S.; Cox, N. J.; Goldstein, D. B.; Hindorff, L. A.; Hunter, D. J.; McCarthy, M. I.; Ramos, E. M.; Cardon, L. R.; Chakravarti, A.; Cho, J. H.; Guttmacher, A. E.; Kong, A.; Kruglyak, L.; Mardis, E.; Rotimi, C. N.; Slatkin, M.; Valle, D.; Whittemore, A. S.; Boehnke, M.; Clark, A. G.; Eichler, E. E.; Gibson, G.; Haines, J. L.; MacKay, T. F. C.; McCarroll, S. A.; Visscher, P. M., Finding the missing heritability of complex diseases, Nature, 461, 7265, 747-753, (2009)
[4] Shastry, B. S., SNP alleles in human disease and evolution, Journal of Human Genetics, 47, 11, 561-566, (2002)
[5] Stubbs, B.; Vancampfort, D.; De Hert, M.; Mitchell, A. J., The prevalence and predictors of type two diabetes mellitus in people with schizophrenia: a systematic review and comparative meta-analysis, Acta Psychiatrica Scandinavica, 132, 2, 144-157, (2015)
[6] Liao, K. P., Cardiovascular disease in patients with rheumatoid arthritis, Trends in Cardiovascular Medicine, 27, 2, 136-140, (2017)
[7] Mao, Y.; London, N. R.; Ma, L.; Dvorkin, D.; Da, Y., Detection of SNP epistasis effects of quantitative traits using an extended Kempthorne model, Physiological Genomics, 28, 1, 46-52, (2006)
[8] Zhang, W.; Zhu, J.; Schadt, E. E.; Liu, J. S., A Bayesian partition method for detecting pleiotropic and epistatic eQTL modules, PLoS Computational Biology, 6, 1, (2010)
[9] Kang, M.; Zhang, C.; Chun, H.-W.; Ding, C.; Liu, C.; Gao, J., EQTL epistasis: Detecting epistatic effects and inferring hierarchical relationships of genes in biological pathways, Bioinformatics, 31, 5, 656-664, (2015)
[10] Lin, H.; Chen, D.; Huang, P.; Liu, Y.; Ochoa, A.; Zabaleta, J.; Mercante, D. E.; Fang, Z.; Sellers, T. A.; Pow-Sang, J. M.; Cheng, C.; Eeles, R.; Easton, D.; Kote-Jarai, Z.; Amin Al Olama, A.; Benlloch, S.; Muir, K.; Giles, G. G.; Wiklund, F.; Gronberg, H.; Haiman, C. A.; Schleutker, J.; Nordestgaard, B. G.; Travis, R. C.; Hamdy, F.; Pashayan, N.; Khaw, K.; Stanford, J. L.; Blot, W. J.; Thibodeau, S. N.; Maier, C.; Kibel, A. S.; Cybulski, C.; Cannon-Albright, L.; Brenner, H.; Kaneva, R.; Batra, J.; Teixeira, M. R.; Pandha, H.; Lu, Y.; Park, J. Y., SNP interaction pattern identifier (SIPI): an intensive search for SNP–SNP interaction patterns, Bioinformatics, (2016)
[11] Prentice, R. L.; Qi, L., Aspects of the design and analysis of high-dimensional SNP studies for disease risk estimation, Biostatistics, 7, 3, 339-354, (2006) · Zbl 1170.62398
[12] Deng, S.-P.; Zhu, L.; Huang, D.-S., Mining the bladder cancer-associated genes by an integrated strategy for the construction and analysis of differential co-expression networks, BMC Genomics, 16, 3, article no. S4, (2015)
[13] Deng, S.-P.; Huang, D.-S., SFAPS: An R package for structure/function analysis of protein sequences based on informational spectrum method, Methods, 69, 3, 207-212, (2014)
[14] Moore, J. H.; Lamb, J. M.; Brown, N. J.; Vaughan, D. E., A comparison of combinatorial partitioning and linear regression for the detection of epistatic effects of the ACE I/D and PAI-1 4G/5G polymorphisms on plasma PAI-1 Levels, Clinical Genetics, 62, 1, 74-79, (2002)
[15] Michael, B. M.; Neapolitan, R. E.; Jiang, X.; Shyam, V., Learning genetic epistasis using Bayesian network scoring criteria, BMC Bioinformatics, 12, 1, (2011)
[16] Wang, Y.; Liu, X.; Robbins, K.; Rekaya, R., AntEpiSeeker: detecting epistatic interactions for case-control studies using a two-stage ant colony optimization algorithm, BMC Research Notes, 3, article 117, (2010)
[17] Zhang, Y.; Liu, J. S., Bayesian inference of epistatic interactions in case-control studies, Nature Genetics, 39, 9, 1167-1173, (2007)
[18] Dorigo, M.; Birattari, M.; Blum, C., Ant colony optimization and swarm intelligence, SpringerVerlag, 5217, 8, 767-771, (2004)
[19] Stützle, T.; López-Ibáñez, M.; Pellegrini, P.; Maur, M.; Montes De Oca, M.; Birattari, M.; Dorigo, M., Parameter adaptation in ant colony optimization, Autonomous Search, 9783642214349, 191-215, (2012)
[20] Blum, C.; Sampels, M., An ant colony optimization algorithm for shop scheduling problems, Journal of Mathematical Modelling and Algorithms, 3, 3, 285-308, (2004) · Zbl 1146.90405
[21] Musa, R.; Arnaout, J.-P.; Jung, H., Ant colony optimization algorithm to solve for the transportation problem of cross-docking network, Computers and Industrial Engineering, 59, 1, 85-92, (2010)
[22] Varela, G. N.; Sinclair, M. C., Ant colony optimisation for virtual-wavelength-path routing and wavelength allocation, Proceedings of the 1999 Congress on Evolutionary Computation (CEC ’99)
[23] Sim, K. M.; Sun, W. H., Ant colony optimization for routing and load-balancing: survey and new directions, Systems Man & Cybernetics Part A Systems Humans IEEE Transactions on, 33, 5, 560-572, (2003)
[24] Ngo, S.-H.; Jiang, X.; Horiguchi, S., Adaptive routing and wavelength assignment using ant-based algorithm, Proceedings of the 2004 12th IEEE International Conference on Networks, ICON 2004 - Unity in Diversity
[25] Vrieze, S. I., Model selection and psychological theory: a discussion of the differences between the Akaike information criterion (AIC) and the Bayesian information criterion (BIC), Psychological Methods, 17, 2, 228-243, (2012)
[26] Huang, D.-S.; Du, J.-X., A constructive hybrid structure optimization methodology for radial basis probabilistic neural networks, IEEE Transactions on Neural Networks, 19, 12, 2099-2115, (2008)
[27] North, B. V.; Curtis, D.; Sham, P. C., Application of logistic regression to case-control association studies involving two causative loci, Human Heredity, 59, 2, 79-87, (2005)
[28] Jing, P.-J.; Shen, H.-B., MACOED: A multi-objective ant colony optimization algorithm for SNP epistasis detection in genome-wide association studies, Bioinformatics, 31, 5, 634-641, (2015)
[29] Ryman, N., CHIFISH: A computer program testing for genetic heterogeneity at multiple loci using chi-square and Fisher’s exact test, Molecular Ecology Notes, 6, 1, 285-287, (2006)
[30] Mehta, C. R.; Patel, N. R., A network algorithm for performing Fisher’s exact test in r × c contingency tables, Journal of the American Statistical Association, 78, 382, 427-434, (1983) · Zbl 0545.62039
[31] Sobrino, B.; Brión, M.; Carracedo, A., SNPs in forensic genetics: A review on SNP typing methodologies, Forensic Science International, 154, 2-3, 181-194, (2005)
[32] Shoval, O.; Sheftel, H.; Shinar, G.; Hart, Y.; Ramote, O.; Mayo, A.; Dekel, E.; Kavanagh, K.; Alon, U., Evolutionary trade-offs, pareto optimality, and the geometry of phenotype space, Science, 336, 6085, 1157-1160, (2012)
[33] Huang, D.-S.; Jiang, W., A general CPL-AdS methodology for fixing dynamic parameters in dual environments, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 42, 5, 1489-1500, (2012)
[34] Zhu, L.; Guo, W.-L.; Deng, S.-P.; Huang, D.-S., ChIP-PIT: enhancing the analysis of chip-seq data using convex-relaxed pair-wise interaction tensor decomposition, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 13, 1, 55-63, (2016)
[35] Angione, C.; Carapezza, G.; Costanza, J.; Lio, P.; Nicosia, G., Pareto optimality in organelle energy metabolism analysis, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 10, 4, 1032-1044, (2013)
[36] Fisher, R. A., On the Interpretation of χ2 from Contingency Tables, and the Calculation of P, Journal of the Royal Statistical Society, 85, 1, 87, (1922)
[37] Agresti, A., A survey of exact inference for contingency tables, Statistical Science, 7, 1, 131-153, (1992) · Zbl 0955.62587
[38] Wenzheng, B.; Yuehui, C.; Dong, W., Prediction of protein structure classes with flexible neural tree, Bio-Medical Materials and Engineering, 24, 6, 3797-3806, (2014)
[39] Zhu, L.; You, Z.-H.; Huang, D.-S.; Wang, B., t-LSE: a novel robust geometric approach for modeling protein-protein interaction networks, PLoS ONE, 8, 4, (2013)
[40] Zheng, C.-H.; Zhang, L.; Ng, V. T.-Y.; Shiu, C. K.; Huang, D.-S., Molecular pattern discovery based on penalized matrix decomposition, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8, 6, 1592-1603, (2011)
[41] Huang, D.-S.; Yu, H.-J., Normalized feature vectors: a novel alignment-free sequence comparison method based on the numbers of adjacent amino acids, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 10, 2, 457-467, (2013)
[42] Marchini, J.; Donnelly, P.; Cardon, L. R., Genome-wide strategies for detecting multiple loci that influence complex diseases, Nature Genetics, 37, 4, 413-417, (2005)
[43] Jiang, R.; Tang, W.; Wu, X.; Fu, W., A random forest approach to the detection of epistatic interactions in case-control studies, BMC Bioinformatics, 10, 1, article S65, (2009)
[44] Kruppa, J.; Ziegler, A.; König, I. R., Risk estimation and risk prediction using machine-learning methods, Human Genetics, 131, 10, 1639-1654, (2012)
[45] Huang, D.-S.; Zheng, C.-H., Independent component analysis-based penalized discriminant method for tumor classification using gene expression data, Bioinformatics, 22, 15, 1855-1862, (2006)
[46] Mahley, R. W.; Weisgraber, K. H.; Huang, Y., Apolipoprotein E4: a causative factor and therapeutic target in neuropathology, including Alzheimer’s disease, Proceedings of the National Academy of Sciences of the United States of America, 103, 15, 5644-5651, (2006)
[47] Reiman, E. M.; Webster, J. A.; Myers, A. J.; Hardy, J.; Dunckley, T.; Zismann, V. L.; Joshipura, K. D.; Pearson, J. V.; Hu-Lince, D.; Huentelman, M.; Craig, D. W.; Coon, K. D.; Liang, W. S.; Herbert, R. H.; Beach, T.; Rohrer, K. C.; Zhao, A. S.; Leung, D.; Bryden, L.; Marlowe, L.; Kaleem, M.; Mastroeni, D.; Grover, A.; Heward, C. B.; Ravid, R.; Rogers, J.; Hutton, M. L.; Melquist, S.; Petersen, R. C.; Alexander, G. E.; Caselli, R.; Kukull, W.; Papassotiropoulos, A.; Stephan, D. A., GAB2 alleles modify Alzheimer’s Risk in APOE ε4 carriers, Neuron, 54, 5, 713-720, (2007)
[48] Zheng, C.-H.; Huang, D.-S.; Zhang, L.; Kong, X.-Z., Tumor clustering using nonnegative matrix factorization with gene selection, IEEE Transactions on Information Technology in Biomedicine, 13, 4, 599-607, (2009)
[49] Deng, S.-P.; Zhu, L.; Huang, D.-S., Predicting hub genes associated with cervical cancer through gene co-expression networks, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 13, 1, 27-35, (2016)
[50] Zhu, L.; Deng, S.-P.; Huang, D.-S., A two-stage geometric method for pruning unreliable links in protein-protein networks, IEEE Transactions on Nanobioscience, 14, 5, 528-534, (2015)
[51] Huang, D.-S.; Zhang, L.; Han, K.; Deng, S.; Yang, K.; Zhang, H., Prediction of protein-protein interactions based on protein-protein correlation using least squares regression, Current Protein and Peptide Science, 15, 6, 553-560, (2014)
[52] Huang, D.-S., Systematic Theory of Neural Networks for Pat-tern Recognition, (May 1996), Publishing House of Electronic Industry of China
[53] Huang, D.-S., Radial basis probabilistic neural networks: model and application, International Journal of Pattern Recognition and Artificial Intelligence, 13, 7, 1083-1101, (1999)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.