1. bookVolume 6 (2016): Issue 3 (July 2016)
Journal Details
License
Format
Journal
First Published
30 Dec 2014
Publication timeframe
4 times per year
Languages
English
access type Open Access

Genetic Algorithm Combined with a Local Search Method for Identifying Susceptibility Genes

Published Online: 10 Jun 2016
Page range: 203 - 212
Journal Details
License
Format
Journal
First Published
30 Dec 2014
Publication timeframe
4 times per year
Languages
English

Detecting genetic association models between single nucleotide polymorphisms (SNPs) in various disease-related genes can help to understand susceptibility to disease. Statistical tools have been widely used to detect significant genetic association models, according to their related statistical values, including odds ratio (OR), chi-square test (χ2), p-value, etc. However, the high number of computations entailed in such operations may limit the capacity of such statistical tools to detect high-order genetic associations. In this study, we propose lsGA algorithm, a genetic algorithm based on local search method, to detect significant genetic association models amongst large numbers of SNP combinations. We used two disease models to simulate the large data sets considering the minor allele frequency (MAF), number of SNPs, and number of samples. The three-order epistasis models were evaluated by chi-square test (χ2) to evaluate the significance (P-value < 0.05). Analysis results showed that lsGA provided higher chi-square test values than that of GA. Simple linear regression indicated that lsGA provides a significant advantage over GA, providing the highest β values and significant p-value.

Keywords

[1] A. D Roses, A. M. Saunders, Y. Huang, J. Strum, K. H. Weisgraber, and R. W. Mahley, Complex disease-associated pharmacogenetics: drug efficacy, drug safety, and confirmation of a pathogenetic hypothesis (Alzheimer’s disease), Pharmacogenomics Journal, vol. 7, pp. 10-28, Feb 2007.Search in Google Scholar

[2] R. Sanjuan and M. R. Nebot, A Network Model for the Correlation between Epistasis and Genomic Complexity, PLos One, vol. 3, pp. e2663, Jul 2008.Search in Google Scholar

[3] C. H. Yang, L. Y. Chuang, Y. H. Cheng, Y. D. Lin, C. L. Wang, C. H. Wen, et al., Single nucleotide polymorphism barcoding to evaluate oral cancer risk using odds ratio-based genetic algorithms, Kaohsiung Journal of Medical Sciences, vol. 28, pp. 362-368, Jul 2012.Search in Google Scholar

[4] J. B. Chen, Y. H. Yang, W. C. Lee, C. W. Liou, T. K. Lin, Y. H. Chung, et al., Sequence-based polymorphisms in the mitochondrial D-Loop and potential SNP predictors for chronic dialysis, PLoS One, vol. 7, pp. e41125, Jul 2012.Search in Google Scholar

[5] C. Y. Yen, S. Y. Liu, C. H. Chen, H. F. Tseng, L. Y. Chuang, C. H. Yang, et al., Combinational polymorphisms of four DNA repair genes XRCC1, XRCC2, XRCC3, and XRCC4 and their association with oral cancer in Taiwan, Journal of Oral Pathology & Medicine, vol. 37, pp. 271-277, May 2008.Search in Google Scholar

[6] J. H. Moore, A global view of epistasis, Nature Genetics, vol. 37, pp. 13-14, Jan 2005.Search in Google Scholar

[7] J. H. Moore, F.W. Asselbergs, and S. M.Williams, Bioinformatics challenges for genome-wide association studies, Bioinformatics, vol. 26, pp. 445-455, Feb 15 2010.Search in Google Scholar

[8] S. Purcell, B. Neale, K. Todd-Brown, L. Thomas, M. A. R. Ferreira, D. Bender, et al., PLINK: A tool set for whole-genome association and populationbased linkage analyses, American Journal of Human Genetics, vol. 81, pp. 559-575, Sep 2007.Search in Google Scholar

[9] X. A. Wan, C. Yang, Q. A. Yang, H. Xue, X. D. Fan, N. L. S. Tang, et al., BOOST: A fast approach to detecting gene-gene interactions in genome-wide case-control studies, American Journal of Human Genetics, vol. 87, pp. 325-340, Sep 2010.Search in Google Scholar

[10] C. S. Greene, B. C. White, and J. H. Moore, Ant colony optimization for genome-wide genetic analysis, in Ant Colony Optimization and Swarm Intelligence, ed: Springer, pp. 37-47, 2008.Search in Google Scholar

[11] L. Y. Chuang, H. Y. Lane, Y. D. Lin, M. T. Lin, C. H. Yang, and H. W. Chang, Identification of SNP barcode biomarkers for genes associated with facial emotion perception using particle swarm optimization algorithm, Annals of General Psychiatry, vol. 13, pp. 15, May 2014.Search in Google Scholar

[12] S. J. Wu, L. Y. Chuang, Y. D. Lin, W. H. Ho, F. T. Chiang, C. H. Yang, et al., Particle swarm optimization algorithm for analyzing SNP-SNP interaction of renin-angiotensin system genes against hypertension, Molecular Biology Reports, vol. 40, pp. 4227-4233, Jul 2013.Search in Google Scholar

[13] J. B. Chen, L. Y. Chuang, Y. D. Lin, C. W. Liou, T. K. Lin, W. C. Lee, et al., Genetic algorithmgenerated SNP barcodes of the mitochondrial Dloop for chronic dialysis susceptibility, Mitochondrial DNA, vol. 25, pp. 231-237, Jun 2014.Search in Google Scholar

[14] W. C. Chang, Y. Y. Fang, H. W. Chang, L. Y. Chuang, Y. D. Lin, M. F. Hou, et al., “Identifying association model for single-nucleotide polymorphisms of ORAI1 gene for breast cancer,” Cancer Cell International, vol. 14, pp. 29, Mar 2014.Search in Google Scholar

[15] J. H. Holland, Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence: U Michigan Press, 1975.Search in Google Scholar

[16] L. P. Li, C. R. Weinberg, T. A. Darden, and L. G. Pedersen, Gene selection for sample classification based on gene expression data: study of sensitivity to choice of parameters of the GA/KNN method, Bioinformatics, vol. 17, pp. 1131-1142, Dec 2001.Search in Google Scholar

[17] C. H. Yang, Y. H. Cheng, L. Y. Chuang, and H. W. Chang, Confronting two-pair primer design for enzyme-free SNP genotyping based on a genetic algorithm, BMC Bioinformatics, vol. 11, pp. 509, Oct 2010.Search in Google Scholar

[18] E. H. Aarts and J. K. Lenstra, Local search in combinatorial optimization: Princeton University Press, 2003.Search in Google Scholar

[19] G. Moslehi and M. Mahnam, A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search, International Journal of Production Economics, vol. 129, pp. 14-22, Jan 2011.Search in Google Scholar

[20] B. Y. Qu, J. J. Liang, and P. N. Suganthan, Niching particle swarm optimization with local search for multi-modal optimization, Information Sciences, vol. 197, pp. 131-143, Aug 2012.Search in Google Scholar

[21] Wan W, Birch JB: An Improved Hybrid Genetic Algorithm with a New Local Search Procedure. Journal of Applied Mathematics 2013, vol. 2013, Article ID 103591, Aug 2013.Search in Google Scholar

[22] J. H. Moore, L. W. Hahn, M. D. Ritchie, T. A. Thornton, and B. C. White, Application of genetic algorithms to the discovery of complex models for simulation studies in human genetics, in Proceedings of the Genetic and Evolutionary Computation Conference/GECCO. Genetic and Evolutionary Computation Conference, 2002, pp. 1150.Search in Google Scholar

[23] W. N. Frankel and N. J. Schork, Who’s afraid of epistasis?, Nature genetics, vol. 14, pp. 371-373, 1996.Search in Google Scholar

[24] J. H. Moore, L. W. Hahn, M. D. Ritchie, T. A. Thornton, and B. C. White, Routine discovery of complex genetic models using genetic algorithms, Applied Soft Computing, vol. 4, pp. 79-86, Feb 2004.Search in Google Scholar

[25] R. J. Urbanowicz, J. Kiralis, N. A. Sinnott- Armstrong, T. Heberling, J. M. Fisher, and J. H. Moore, GAMETES: a fast, direct algorithm for generating pure, strict, epistatic models with random architectures, Biodata Mining, vol. 5, pp. 16, Oct 2012.Search in Google Scholar

[26] A. Mousa, M. El-Shorbagy, and W. Abd-El- Wahed, Local search based hybrid particle swarm optimization algorithm for multiobjective optimization, Swarm and Evolutionary Computation, vol. 3, pp. 1-14, Apr 2012.Search in Google Scholar

[27] H. Derbel, B. Jarboui, S. Hanafi, and H. Chabchoub, Genetic algorithm with iterated local search for solving a location-routing problem, Expert Systems with Applications, vol. 39, pp. 2865-2871, Feb 2012.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo