Ant colony optimisation of decision tree and contingency table models for the discovery of gene–gene interactions

Emmanuel Sapin; Ed Keedwell; Tim Frayling

Ant colony optimisation of decision tree and contingency table models for the discovery of gene–gene interactions

View Fulltext

Author(s): Emmanuel Sapin ¹¹ ; Ed Keedwell ¹¹ ; Tim Frayling ²²
- Affiliations: 1: College of Engineering, Mathematics and Physical Sciences, University of Exeter, UK ;
  2: Exeter Medical School, University of Exeter, UK
Source: Volume 9, Issue 6, December 2015, p. 218 – 225
DOI: 10.1049/iet-syb.2015.0017 , Print ISSN 1751-8849, Online ISSN 1751-8857

Received 16/02/2015, Accepted 31/05/2015, Revised 15/05/2015, Published 01/12/2015

In this study, ant colony optimisation (ACO) algorithm is used to derive near-optimal interactions between a number of single nucleotide polymorphisms (SNPs). This approach is used to discover small numbers of SNPs that are combined into a decision tree or contingency table model. The ACO algorithm is shown to be very robust as it is proven to be able to find results that are discriminatory from a statistical perspective with logical interactions, decision tree and contingency table models for various numbers of SNPs considered in the interaction. A large number of the SNPs discovered here have been already identified in large genome-wide association studies to be related to type II diabetes in the literature, lending additional confidence to the results.

References

1. 1)
  - 22. Moore, J.H., White, W.C.: ‘Exploiting knowledge in genetic programming for genome-wide genetic analysis’. Parallel Problem Solving from Nature - PPSN IX, 2010 (LNCS, 4193), pp. 969–977.
2. 2)
  - 28. Sapin, E., Keedwell, E., Frayling, T.: ‘Subset-based ant colony optimisation for the discovery of gene–gene interactions in genome wide association studies’. Proc. 15th Annual Conf. on Genetic and Evolutionary Computation, 2013, pp. 295–302.
3. 3)
  - 41. Leguizamon, G., Michalewicz, Z.: ‘A new version of ant system for subset problems’. Proc. of the 1999 Congress on Evolutionary Computation (CEC 99), 1999, vol. 2, pp. 1458–1464.
4. 4)
  - 18. Gunther, F., Wawro, N., Bammann, K.: ‘Neural networks for modeling gene–gene interactions in association studies’, BMC Genet.., 2009, 10 (doi: 10.1186/1471-2156-10-87).
5. 5)
  - 36. Otero, F., Freitas, A., Johnson, C.: ‘Inducing decision trees with an ant colony optimization algorithm’, Appl. Soft Comput., 2012, 12, (11), pp. 3615–3626 (doi: 10.1016/j.asoc.2012.05.028).
6. 6)
  - 3. Wright, S.: ‘Genic and organismic selection’, Evolution, 1980, 34, pp. 825–843 (doi: 10.2307/2407990).
7. 7)
  - 20. Yang, C., He, Z., Wan, X., Yang, Q., Xue, H., Yu, W.: ‘SNPharvester: a filtering-based approach for detecting epistatic interactions in genome-wide association studies’, Bioinformatics, 2009, 25, pp. 504–511 (doi: 10.1093/bioinformatics/btn652).
8. 8)
  - 43. Jin, T., Liu, L.: ‘The wnt signaling pathway effector TCF7l2 and type 2 diabetes mellitus’, Mol. Endocrinol., 2008, 22, pp. 2383–2392 (doi: 10.1210/me.2008-0135).
9. 9)
  - 45. He, X., Fuller, C., Song, Y., et al: ‘Sherlock: detecting gene-disease associations by matching patterns of expression QTL and GWAA’, AJHG, 2013, 92, pp. 667–680 (doi: 10.1016/j.ajhg.2013.03.022).
10. 10)
  - 16. Park, M., Hastie, T.: ‘Penalized logistic regression for detecting gene interactions’, Biostatistics, 1980, 9, pp. 30–50 (doi: 10.1093/biostatistics/kxm010).
11. 11)
  - 39. Sapin, E., Keedwell, E.: ‘T-ACO – tournament ant colony optimisation for high-dimensional problems’. Proc. of the Int. Joint Conf. on Computational Intelligence, 2012, pp. 81–86.
12. 12)
  - 44. Bell, J., Timpson, N.J., Rayner, N.W., et al: ‘Genome-wide association scan allowing for epistasis in type 2 diabetes’, Ann. Hum. Genet., 2011, 75, pp. 10–19 (doi: 10.1111/j.1469-1809.2010.00629.x).
13. 13)
  - 29. Sapin, E., Keedwell, E., Frayling, T.: ‘Ant colony optimisation for exploring logical gene–gene associations in genome wide association studies’. IWBBIO'13, 2013, pp. 449–456.
14. 14)
  - 25. Zhou, Z., Liu, G., Su, L.: ‘A new approach to detect epistasis utilizing parallel implementation of ant colony optimization by MapReduce framework’, Int. J. Comput. Math., 2015, pp. 1–13 (doi: 10.1080/00207160.2014.1000882).
15. 15)
  - 42. Saxena, R., Voight, B.F., Lyssenko, V., et al: ‘Genome-wide association analysis identifies loci for type 2 diabetes and triglyceride levels’, Science, 2007, 316, pp. 1331–1336 (doi: 10.1126/science.1142358).
16. 16)
  - 1. Klein, R., Zeiss, C., Chew, E., et al: ‘Complement factor h polymorphism in age-related macular degeneration’, Sci. 15 April 2005, 2005, 308, pp. 385–389.
17. 17)
  - 30. Sapin, E., Keedweel, E., Frayling, T.: ‘Subset-based ant colony optimisation of decision trees for the detection of gene-gene interactions’ . 2014 IEEE International Conference on Bioinformatics and Biomeicine (BIBM), Nov. 2014, pp 57–61.
18. 18)
  - 38. Dorigo, M., Maniezzo, V., Colorni, A.: ‘Positive feedback as a search strategy’. Technical Report, no. 91–016, Politecnico di Milano, Italy, 1991.
19. 19)
  - 27. Christmas, J., Keedwell, E., Frayling, T.M., Perry, J.R.B.: ‘Ant colony optimisation to identify genetic variant association with type 2 diabetes’, Inf. Sci., 2011, 181, pp. 1609–1622 (doi: 10.1016/j.ins.2010.12.005).
20. 20)
  - 33. Diwakar, P., Rahul, R., Prashant, S., Bhaskar, K., Jayaraman, V.K.: ‘Random forests’, Comb. Chem. High Throughput Screen., 12, p. 507.
21. 21)
  - 2. Johnson, A., O'Donnell, C.: ‘An open access database of genome-wide association results’, BMC Med. Genet., 2009, 10, (1), 6 (doi: 10.1186/1471-2350-10-6).
22. 22)
  - 11. Hahn, L., Ritchie, M., Moore, J.: ‘Multifactor dimensionality reduction software for detecting gene–gene and gene–environment interactions’, Bioinformatics, 2003, 19, pp. 376–382 (doi: 10.1093/bioinformatics/btf869).
23. 23)
  - 26. 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 Res. Notes, 2010, 3, p. 117 (doi: 10.1186/1756-0500-3-117).
24. 24)
  - 46. Chang, Y., Liu, P., Shih, K., et al: ‘Replication of genome-wide association signals of type 2 diabetes in han Chinese in a prospective cohort’, Clin. Endocrinol., 2012, 76, pp. 365–372 (doi: 10.1111/j.1365-2265.2011.04175.x).
25. 25)
  - 40. Sapin, E., Keedweel, E.: ‘A subset-based ant colony optimisation with tournament path selection for high-dimensional problem’. Transactions on Computional Collective Intelligence (LNCS, 8790), 17, pp 232–247.
26. 26)
  - 14. Culverhouse, R., Klein, T., Shannon, W.: ‘Detecting epistatic interactions contributing to quantitative traits genet’, Epidemiol. Genome Res., 2004, 27, pp. 141–152 (doi: 10.1002/gepi.20006).
27. 27)
  - 4. Oki, N.: ‘On considering epistasis in genome wide association studies’ (North Carolina State University, North Carolina, USA2012).
28. 28)
  - 24. Shang, J., Zhang, J., Lei, X., Zhang, Y., Chen, B.: ‘Incorporating heuristic information into ant colony optimization for epistasis detection’, 2012, 34, (3), pp. 321–327.
29. 29)
  - 13. Nelson, M., Kardia, S., Ferrell, R., Sing, C.F.: ‘A combinatorial partitioning method to identify multilocus genotypic partitions that predict quantitative trait variation’, Genome Res., 2001, 11, pp. 458–470 (doi: 10.1101/gr.172901).
30. 30)
  - 21. Mooney, M., Wilmot, B., Bipolar Genome StudyMcWeeney, T.S., et al: ‘The GA and the GWAS: using genetic algorithms to search for multi-locus associations’. IEEE/ACM Transactions on Computational Biology and Bioinformatics/IEEE, 2011, doi: 10.1109/TCBB.2011.145. PMC. Web. 16 Apr. 2015.
31. 31)
  - 9. Breiman, L.: ‘Random forests’, Mach. Learn, 2001, 45, pp. 5–32 (doi: 10.1023/A:1010933404324).
32. 32)
  - 15. Hosmer, D., Lemeshow, S.: ‘Applied logistic regression’ (John Wiley & Sons, Inc., New York, 2000).
33. 33)
  - 35. Boryczka, U., Kozak, J.: ‘Ant colony decision trees – a new method for constructing decision trees based on ant colony optimization’. Computational Collective Intelligence. Technologies and Applications, 2010 (LNCS, 6421), pp. 373–382.
34. 34)
  - 17. Voight, B.F., Scott, L.J., Steinthorsdottir, V., et al: ‘Twelve type 2 diabetes susceptibility loci identified through large-scale association analysis’, Nat. Genet., 2010, 42, pp. 579–589 (doi: 10.1038/ng.609).
35. 35)
  - 37. Oh, S., Lee, J., Kwon, M., Weir, B., Ha, K., Park, T.: ‘A novel method to identify high order gene–gene interactions in genome-wide association studies: gene-based MDR’, BMC Bioinform., 2012, 13, p. S5 (doi: 10.1186/1471-2105-13-S9-S5).
36. 36)
  - 5. The Wellcome Trust Case Control Consortium: ‘Genome-wide association study of 14,000 cases of seven common diseases and 3000 shared controls’, Nature, 2007, 447, pp. 661–978 (doi: 10.1038/nature05911).
37. 37)
  - 8. Lunetta, K., Hayward, L., Segal, J., Van Eerdewegh, P.: ‘Screening large-scale association study data: exploiting interactions using random forests’, BMC Genet., 2004, 5, 32. (doi: 10.1186/1471-2156-5-32).
38. 38)
  - 10. Winham, S., Colby, C., Freimuth, R., Wang, X., De Andrade, M.: ‘SNP interaction detection with random forests in high-dimensional genetic data’, BMC Bioinformatics, 2012, 13 (doi: 10.1186/1471-2105-13-164).
39. 39)
  - 19. Chuang, L., Lin, M., Yang, C.: ‘Improved branch and bound algorithm for detecting SNP–SNP interactions in breast cancer’, J. Clin. Bioinform., 2013, 3, 4. (doi: 10.1186/2043-9113-3-4).
40. 40)
  - 12. Ritchie, M., Hahn, L., Roodi, N., et al: ‘Multifactor-dimensionality reduction reveals high-order interactions among estrogen-metabolism genes in sporadic breast cancer’, Am. J. Hum. Genet., 2001, 69, pp. 138–147 (doi: 10.1086/321276).
41. 41)
  - 32. Sharma, S., Ghosh, S., Anantharaman, N., Jayaraman, V.: ‘Simultaneous informative gene extraction and cancer classification using aco-antminer and aco-random forests’. Proc. Int. Conf. on Information Systems Design and Intelligent Applications 2012 (INDIA 2012) held in Visakhapatnam, India, January 2012. Advances in Intelligent and Soft Computing Volume, 2012, vol. 132, pp. 755–761.
42. 42)
  - 34. Boryczka, U., Kozak, J.: ‘New insights of cooperation among ants in ant colony decision trees’. 2011 Third World Congress on IEEE Nature and Biologically Inspired Computing (NaBIC), 2011, pp. 255–260.
43. 43)
  - 23. Greene, C., White, B., Moore, J.: ‘Ant colony optimization for genome-wide genetic analysis’. Ant Colony Optimization and Swarm Intelligence, Berlin/Heidelberg, 2008 (LNCS, 5217), pp. 37–47.
44. 44)
  - 7. Goldstein, B., Hubbard, A., Cutler, A., Barcellos, L.: ‘An application of random forests to a genome-wide association dataset: methodological considerations & new findings’, BMC Genet., 2010, 11, 49. (doi: 10.1186/1471-2156-11-49).
45. 45)
  - 9. Touw, W., Bayjanov, J., Overmars, L., et al: ‘Data mining in the life sciences with random forest: a walk in the park or lost in the jungle?’, Brief. Bioinform., 2013, 14, (3), 315–326. (doi: 10.1093/bib/bbs034).
46. 46)
  - 6. Bureau, A., Dupuis, J., Hayward, B., Falls, K., Van Eerdewegh, P.: ‘Mapping complex traits using random forests’, BMC Genet., 2003, 4, (Suppl 1), S64. (doi: 10.1186/1471-2156-4-S1-S64).

Login

Not registered yet?

Share

Tools

Login to add to favourites

Key

Ant colony optimisation of decision tree and contingency table models for the discovery of gene–gene interactions

References

Related content