Ant Colony Optimisation for the Discovery of Gene-Gene Interactions in Genome-Wide Association Studies

Lead Research Organisation: University of Exeter
Department Name: Engineering Computer Science and Maths


Genome-wide association studies investigate the small changes in DNA among individuals in a population that lead to variations in traits such as height and the propensity to suffer from diseases. Recent advances in genetic technology allow researchers to measure these small differences in DNA in a population (known as single-nucleotide polymorphisms or SNPs) and have already discovered SNPs that are associated with diseases including the widely publicised 'FTO' gene which has been shown to be highly associated with type 2 diabetes. However, single SNPs do not account for all of the variation that is suspected to be inherited and researchers are now beginning to investigate the potential for interactions between multiple SNPs to explain this variation. The number of possible pairs and triplets in the genome though is vast and so a full enumeration search is not possible, meaning that intelligent techniques are required to process the large space of potential interactions. A method that has shown considerable promise in this area is ant colony optimisation (ACO), a nature-inspired search technique based on the way that insects find the shortest path from a nest to a food source in the wild. This search algorithm has two unique properties that make it ideal for this task. The first is that local heuristics can be used to influence the search to find specific gene-gene interactions such as epistasis and the second is that the algorithm creates a pheromone matrix that provides a detailed map of the importance of variables (SNPs) found during the search. This project will investigate the use of ACO to search the space of SNP interactions and their association with a number of diseases including type 2 diabetes and Crohn's disease and also the potential for them to explain human traits such as height. The discovery of these interactions will advance our knowledge of how disease is inherited and could pave the way for highly personalised and pre-emptive treatment based on an individual's genetic makeup.

Planned Impact

The chief, longer term (3-10 years) societal impact from this research will be achieved through the identification of gene-gene interactions in genome-wide association studies of human populations and the resulting potential to better stratify individuals suffering from a disease. The ability to accurately determine the disease-risk posed to an individual increases the potential for early and personalised treatment plans. Early or pre-emptive treatment has the potential to delay the onset of symptoms of a disease, reduce symptom severity and complications, and to reduce costs associated with treating the disease across a population of individuals Taking the example of type 2 diabetes, there are an estimated 2.5 million people suffering from this disease currently in the UK and this is expected to rise to 4 million by 2026 (Diabetes UK, 2010). If even a small proportion of these individuals can benefit from diagnosis of disease risk and subsequent early treatment then this would in turn lead to improved health and quality of life for thousands of people and a significant reduction in the burden on the NHS.

The chief, longer term (3-10 years) economic impact will be in the potential to reduce costs of treatments of diseases and their complications through early treatment, an approach that has begun to be used in the USA for type 2 diabetes (Herman et al. 2005). In the UK, the current costs for treating type 2 diabetes are around 10% of the entire budget for the NHS (around £9bn) and this figure is expected to rise significantly (Bagust et al. 2002), so clearly any significant reduction in treatment costs for this disease would have profound economic benefits for the country.

The chief impact on people will be the training of a post-doctoral researcher in this new area of research. The researcher is expected to come to the project with a significant existing skillset, but the precise nature of the algorithms and technologies used in this work means that they will need to become familiar with the particular skills required, rapidly furthering their expertise in this growing field. The proposal will also foster the collaboration between Dr Keedwell and Prof. Frayling, with the attendant increase in knowledge of each field that comes from working together on a project of this novel and interdisciplinary nature.

- Bagust, P. K. Hopkinson, L. Maslove and C. J. Currie (2002) "The projected health care burden of Type 2 diabetes in the UK from 2000 to 2060" Diabetic Medicine 19; Supp/4, pp1-5
- Herman et al. (2005) "The Cost-Effectiveness of Lifestyle Modification or Metformin in Preventing Type 2 Diabetes in Adults with Impaired Glucose Tolerance" Ann. Intern. Med. 2005 March 1; 142(5) pp 323-332.


10 25 50
Description The grant developed algorithms to discover combinations of small changes to DNA (known as SNPs) that are associated with a number of diseases including Type-2 diabetes and rheumatoid arthritis. We developed algorithms based on an ant colony optimisation approach, and in particular made the approaches more applicable to large datasets through the use of two approaches, tournament selection and tabu search. The methods were shown to discover SNPs that are known to be highly associated with these diseases.
Exploitation Route The algorithms can be used to find combinations of SNPs associated with disease and therefore might be used as targets for future drug development to improve treatments for patients. The findings also further our understanding of individuals who may be at risk from these diseases and so providing the opportunity for preventative measures to be taken.
Sectors Digital/Communication/Information Technologies (including Software),Healthcare,Pharmaceuticals and Medical Biotechnology

Description Open Day and Undergraduate Research Talks 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Undergraduate students
Results and Impact The work from this project has been presented as an example of research in the department to groups of prospective students at Open Days and to new undergraduates. The (prospective) students then engaged in a Q&A session after the talk.
Year(s) Of Engagement Activity 2014,2015,2016,2017
Description Website dedicated to the work undertaken in this grant 
Form Of Engagement Activity A magazine, newsletter or online publication
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact Website provides details of the work undertaken during the grant, notable results and publications. The site has been written to disseminate results to other researchers, and should also give a lay audience an understanding of the work that has been carried out.

No direct identifiable impact such as this.
Year(s) Of Engagement Activity 2013,2014