A self -adaptive random walk algorithm to identify genetic epistatic effects.

A novel search algorithm is developed for finding gene interaction, or epistasis, involved in determining quantitative traits. The algorithm is able to simultaneously find several epistatic effects involving any number of genetic loci. Several other search methods exist in the literature, but most search for epistasis involving two or less loci. For epistasis, especially epistasis involving more than two loci, traditional statistical tests have very low power. In the search algorithm, a series of random walks in the space of possible groups of epistatic effects is performed. The performance of the algorithm is measured while varying key parameters, including the length of the walk, the number of genetic markers available, and the sample size available. Two versions are described, one which restricts the search space to effects involving markers, and a newer approach that allows any locus to be considered. For the newer general locus version, the Expectation Maximization algorithm (EM algorithm) is used to find likelihoods of proposed models. The algorithm was designed to adapt between walks, allowing those loci associated with better models to be guessed more frequently. If the adaptation was gradual, limited and continuous, then the resulting algorithm was robust and improved performance greatly. In simulated data, the algorithm was successful at finding epistatic effects. When several epistatic effects were present in the simulated data, the method was able to simultaneously find all of them at low noise levels. The algorithm was tested in simulated data against a more exhaustive approach, effect bootstrapping, as well as a mainstream approach, Multiple Interval Mapping, and compared well to both approaches. In experimental data, the algorithm found strong evidence of several epistatic effects for most of the phenotypes that were analyzed. Strong evidence of several epistatic effects involving four loci were found, one with a p-value of less than 0.001 from a permutation test. To the best of our knowledge, this is the first time epistasis involving four loci has been explored for quantitative data.PhDMathematicsPure SciencesUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/125699/2/3208501.pd