Center for Computational Molecular Biology Postdoctoral Fellow Interview Seminar
"Algorithms for Analyzing Intraspecific Sequence Variation"
Srinath Sridhar, Ph.D.
Tuesday, December 2, 2008 at 12:30 P.M.
Room 241 Swig Boardroom (2nd Floor CIT)
Analysis of human genetic variation has gained significant momentum due to the success of many large-scale sequencing projects. Within the last five years, millions of single nucleotide polymorphisms (SNPs) have been genotyped over thousands of individuals belonging to several different ethnic groups. The large-scale efforts have now made it possible to analyze genetic variation within humans, at very fine-scales.
In the talk, we outline two research directions to analyze SNP variation within humans. Firstly, we develop maximum parsimony phylogenetic tree reconstruction algorithms that are specifically catered to work on SNP data. Such a phylogeny should cluster closely related individuals (perhaps an ethnic group) together. Therefore, these techniques are widely used to answer questions of human migration. A second method to understand genetic variation is to infer population substructure, i.e., find clusters of individuals based on the property that individuals within a cluster would share similar genetic sequences.
Mathematically, we work with two variants of the phylogeny reconstruction problem, both of which are NP-complete. The first variant is equivalent to finding a Steiner minimum tree on a hypercube and the second is a generalization of this problem. We solve the two variants in polynomial time when the size of the phylogeny (Steiner minimum tree) is 'small' with respect to the dimensions of the hypercube (near-perfect). For detecting substructure, we reduce the problem to finding the max-cut of a graph, a well-known NP-complete problem. We can show that if the graph is generated with the clusters 'planted', then our algorithm finds the max-cut in polynomial time given enough data. We provide extensive empirical results to show the methods' effectiveness for both problems.
Host: Sorin Istrail
| Page Owner: Webmaster | Last Modified: Mon Dec 1 13:53:08 2008 |