Hill-climbing through "random chemistry" for detecting epistasis

Created by W.Langdon from gp-bibliography.bib Revision:1.4524

  author =       "Margaret J. Eppstein and Joshua L. Payne and 
                 Bill C. White and Jason H. Moore",
  title =        "Hill-climbing through {"}random chemistry{"} for
                 detecting epistasis",
  booktitle =    "Late breaking paper at Genetic and Evolutionary
                 Computation Conference {(GECCO'2006)}",
  year =         "2006",
  month =        "8-12 " # jul,
  editor =       "J{\"{o}}rn Grahl",
  address =      "Seattle, WA, USA",
  URL =          "http://www.cs.bham.ac.uk/~wbl/biblio/gecco2006etc/papers/lbp111.pdf",
  notes =        "Distributed on CD-ROM at GECCO-2006",
  keywords =     "genetic algorithms, genetic programming, Population
                 based optimisation, epistasis, SNPs, data mining.",
  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

Genetic Programming entries for Margaret J Eppstein Joshua L Payne Bill C White Jason H Moore