Subset-based ant colony optimisation for the discovery of gene-gene interactions in genome wide association studies

ABSTRACT

In this paper an ant colony optimisation approach for the discovery of gene-gene interactions in genome-wide association study (GWAS) data is proposed. The subset-based approach includes a novel encoding mechanism and tournament selection to analyse full scale GWAS data consisting of hundreds of thousands of variables to discover associations between combinations of small DNA changes and Type II diabetes. The method is tested on a large established database from the Wellcome Trust Case Control Consortium and is shown to discover combinations that are statistically significant and biologically relevant within reasonable computational time.

References

1. J. Christmas, E. Keedwell, TM. Frayling, and JRB. Perry. Ant colony optimisation to identify genetic variant association with type 2 diabetes,. In Information Sciences., volume 181, pages 1609--1622, 2011.
2. Wellcome Trust Case Control Consortium. Genome-wide association study of 14000 cases of seven common diseases and 3000 shared controls. Nature, 447:661--978, 2007.
3. Marco Dorigo and Gianni Di Caro. The ant colony optimization meta-heuristic. In in New Ideas in Optimization, pages 11--32. McGraw-Hill, 1999.
4. Sapin E and Keedwell EC. T-aco - tournament ant colony optimisation for high dimensional problems. in ECTA 2012 - 4th International Conference on Evolutionary Computation Theory and Applications, Barcelona, Spain, 5th - 7th Oct 2012., 2012.
5. M.N. Weedon et al. Combining information from common type 2 diabetes risk polymorphisms improves disease prediction. PLoS Nedicine 3, 10:1877--1882, 2006.
6. Anna L. Gloyn, Michael N. Weedon, Katharine R. Owen, Martina J. Turner, Bridget A. Knight, and Graham Hitman et al. Large-scale association studies of variants in genes encoding the pancreatic beta-cell katp channel subunits kir6.2 (kcnj11) and sur1 (abcc8) confirm that the kcnj11 e23k variant is associated with type 2 diabetes. Diabetes, 52:568--572, 2003.
7. Casey Greene, Bill White, and Jason Moore. Ant colony optimization for genome-wide genetic analysis. In Marco Dorigo, Mauro Birattari, Christian Blum, Maurice Clerc, Thomas Stutzle, and Alan Winfield, editors, Ant Colony Optimization and Swarm Intelligence, volume 5217 of Lecture Notes in Computer Science, pages 37--47. Springer Berlin / Heidelberg, 2008.
8. Kaprio J, Tuomilehto J, Koskenvuo M, Romanov K, Reunanen A, Eriksson J et al. %and Stengård J, and Kesäniemi YA. Concordance for type 1 (insulin-dependent) and type 2 (non-insulin-dependent) diabetes mellitus in a population-based cohort of twins in finland. Diabetologia, 35(11):1060--7, 1992.
9. G. Leguizamon and Z. Michalewicz. A new version of ant system for subset problems. Proceedings of the 1999 Congress on Evolutionary Computation(CEC 99), 2:1458--1464, 1999.
10. Scott LJ, Mohlke KL, Bonnycastle LL, Willer CJ, Li Y, and Duren WL et al. A genome-wide association study of type 2 diabetes in finns detects multiple susceptibility variants. Science, 316(5829):1341--5, 2007.
11. Dorigo M., V. Maniezzo, and A. Colorni. Positive feedback as a search strategy. Tech. Rep. No. 91-016, Politecnico di Milano, Italy, 1991.
12. Kasuga M. Insulin resistance and pancreatic beta cell failure. J Clin Invest, 116:1756--1760, 2006.
13. J. H. Moore and W. C. White. Exploiting knowledge in genetic programming for genome-wide genetic analysis. in Lecture Notes in Computer Science, T. P. Runarsson, H. G. Beyer, E. Burke, J. J. Merelo-Guervós, L. D. Whitley and X. Yao, Eds. Springer, 4193:969--977, 2006.
14. Grant SF, Thorleifsson G, Reynisdottir I, Benediktsson R, Manolescu A, and Sainz J et al. Variant of transcription factor 7-like 2 (tcf7l2) gene confers risk of type 2 diabetes. Nat Genet, 38(3):320--3, 2006.
15. Dov Shiffman, Devlin J. James, L. Judy Z., and E. Boerwinkle. Detecting two-locus associations allowing for interactions in genome-wide association studies. Celera Corporation, 12, 2009.
16. Rich SS. Mapping genes in diabetes. genetic epidemiological perspective. Diabetes., 39(11):1315--9, 1990.
17. T. Stutzle and M. Dorigo. Aco algorithms for the traveling salesman problem 1999. In Periaux (eds), Evolutionary Algorithms in Engineering and Computer Science: Recent Advances in Genetic Algorithms, Evolution Strategies, Evolutionary Programming, Genetic Programming and Industrial Applications. John Wiley & Sons, 1999.
18. Xiang Wan, Can Yang, Qiang Yang, Hong Xue, Nelson L. S. Tang, and Weichuan Yu. Detecting two-locus associations allowing for interactions in genome-wide association studies. Bioinformatics, 26:2517--2525, 2003.
19. A.C. Zecchin, H.R. Maier, A.R. Simpson, M.Leonard, and J.B. Nixon. Ant colony optimization applied to water distribution system design: Comparative study of five algorithms. In Journal of Water Resources Planning and Management, Vol. 133, No. 1, January 1., 2007.
20. Eleftheria Zeggini, Michael N. Weedon, Cecilia M. Lindgren, Timothy M. Frayling, Katherine S. Elliott, and Hana Lango et al. Replication of genome-wide association signals in uk samples reveals risk loci for type 2 diabetes. Science, 316:1336--1341, 2007.

Index Terms

• Applied computing

  • Life and medical sciences

    • Computational biology

    • Genetics

    • Systems biology