%0 Conference Paper %1 Eppstein:gecco06lbp %A Eppstein, Margaret J. %A Payne, Joshua L. %A White, Bill C. %A Moore, Jason H. %B Late breaking paper at Genetic and Evolutionary Computation Conference (GECCO'2006) %C Seattle, WA, USA %D 2006 %E Grahl, Jörn %K Population SNPs, algorithms, based data epistasis, genetic mining. optimisation, programming, %T Hill-climbing through "random chemistry" for detecting epistasis %U http://www.cs.bham.ac.uk/~wbl/biblio/gecco2006etc/papers/lbp111.pdf %X There are estimated to be on the order of 1000000 single nucleotide polymorphisms (SNPs) existing as standing variation in the human genome. Certain combinations of these SNPs can interact in complex ways to predispose individuals for a variety of common diseases, even though individual SNPs may have no ill effects. Detecting these epistatic combinations is a computationally daunting task. Trying to use individual or growing subsets of SNPs as building blocks for detection of larger combinations of purely epistatic SNPs (e.g., via genetic algorithms or genetic programming) is no better than random search, since there is no predictive power in subsets of the correct set of epistatically interacting SNPs. Here, we explore the potential for hill-climbing from the other direction; that is, from large sets of candidate SNPs to smaller ones. This approach was inspired by Kauffman's "random chemistry" approach to detecting small autocatalytic sets of molecules from within large sets. Preliminary results from synthetic data sets show that the resulting algorithm can detect epistatic pairs from up to 1000 candidate SNPs in O(log N) fitness evaluations, although success rate degrades as heritability declines. The results presented herein are offered as proof of concept for the random chemistry approach.

@inproceedings{Eppstein:gecco06lbp, abstract = {There are estimated to be on the order of 1000000 single nucleotide polymorphisms (SNPs) existing as standing variation in the human genome. Certain combinations of these SNPs can interact in complex ways to predispose individuals for a variety of common diseases, even though individual SNPs may have no ill effects. Detecting these epistatic combinations is a computationally daunting task. Trying to use individual or growing subsets of SNPs as building blocks for detection of larger combinations of purely epistatic SNPs (e.g., via genetic algorithms or genetic programming) is no better than random search, since there is no predictive power in subsets of the correct set of epistatically interacting SNPs. Here, we explore the potential for hill-climbing from the other direction; that is, from large sets of candidate SNPs to smaller ones. This approach was inspired by Kauffman's {"}random chemistry{"} approach to detecting small autocatalytic sets of molecules from within large sets. Preliminary results from synthetic data sets show that the resulting algorithm can detect epistatic pairs from up to 1000 candidate SNPs in O(log N) fitness evaluations, although success rate degrades as heritability declines. The results presented herein are offered as proof of concept for the random chemistry approach.}, added-at = {2008-06-19T17:35:00.000+0200}, address = {Seattle, WA, USA}, author = {Eppstein, Margaret J. and Payne, Joshua L. and White, Bill C. and Moore, Jason H.}, biburl = {https://www.bibsonomy.org/bibtex/2e28d505fff03a81315f718f2d944a58a/brazovayeye}, booktitle = {Late breaking paper at Genetic and Evolutionary Computation Conference {(GECCO'2006)}}, editor = {Grahl, J{\"{o}}rn}, interhash = {1276f43b79df5b5186a745a1587e7ca1}, intrahash = {e28d505fff03a81315f718f2d944a58a}, keywords = {Population SNPs, algorithms, based data epistasis, genetic mining. optimisation, programming,}, month = {8-12 July}, notes = {Distributed on CD-ROM at GECCO-2006}, timestamp = {2008-06-19T17:39:15.000+0200}, title = {Hill-climbing through {"}random chemistry{"} for detecting epistasis}, url = {http://www.cs.bham.ac.uk/~wbl/biblio/gecco2006etc/papers/lbp111.pdf}, year = 2006 }