Middlebury College
Department of Computer Science Seminar
Friday, April 7th at 12:20 PM:
A "Random Chemistry" Algorithm for Detecting Epistatic Genetic Interactions
Dr. Margaret J. Eppstein
Department of Computer Science
University of Vermont
There are estimated to be on the order of 106 single nucleotide polymorphisms (SNPs) existing as standing variations in the human genome. Certain combinations of these SNPs can predispose individuals for a variety of common diseases, even though individual SNPs may have no ill effects. Detecting which handfuls of SNPs exhibit these nonlinear epistatic interactions is a computationally daunting combinatorial optimization task.Solving this important problem is further exacerbated by low disease heritability, small sample sizes, little or no marginal effects for individual SNPs, and unknown a priori information regarding how many, if any, SNPs interact epistatically. Brute force approaches are feasible only for small sets, and standard evolutionary computation approaches are no better than random search.
Here, we explore the potential for an alternative methodology, one inspired by Kauffman's "random chemistry" approach to detecting small autocatalytic sets of molecules from within large sets. In this approach, we generate a small population of large sets of SNPs (each half the size of the original set), which are then evaluated using an approximate and noisy fitness function that estimates whether they are likely to contain smaller subsets of epistatically interacting SNPs. The sets with the highest fitness are then merged, and the process is repeated until the sets in the population become small enough to support a brute force fitness evaluation. Preliminary results from synthetic data sets with a range of heritabilities are presented.
Friday, April 7, 2006
12:20 p.m. to 1:15 p.m.
McCardell Bicentennial Hall 538
Lunch will be provided at 12:05 p.m.
All are welcome to attend!
This event is supported by the Computer Science Enrichment Fund