Colloquia, Seminars and Conference News
Title : Graph Theoretic Approaches to RECOMBINOMICS
Date : October 12, 2009. (3:00 pm) Tea starts half an hour before each seminar
Location: ITEB 336
Speaker : Laxmi Parida
Abstract:
The work is motivated by the need for understanding, and processing, the manifestations of recombination events in chromosome sequences. It turns out that one of the tools of choice is graph-theory, which provides a convenient handle on the problems arising in recombinational population genomics. In this talk, we focus on two related problems. First, we explore the general problem of reconstructability of pedigree history. How plausible is it to unravel the history of a complete unit (chromosome) of inheritance? We use a random graphs framework to study pedigree history in an ideal (Wright Fisher) population. This framework correlates the underlying mathematical objects in pedigree graph, mtDNA or NRY Chromosome tree, ARG (Ancestral Recombinations Graph) etc. used in population genomics literature, into a single unified random graph framework. Apart from providing natural and topology-based definitions for many population genomic entities (such as GMRCA and ARG), the framework also suggests sampling algorithms (with proven randomness) to construct random populations for simulations studies. Finally, using a suitable measure, the framework provides a concrete answer to the general reconstructability question.
The second problem deals with estimating the recombinational history of a sample of individuals. Apparently there is more genetic diversity in human genomes, in terms of SNPs, inversions, copy number variations and so on, than was believed earlier. As large databases become available, is it possible to detect the recombination events in the data. And, what stories, if any, these recombinational landscapes tell us? I will discuss our experience with designing discovery algorithms-- a graph based system called IRiS that we have developed for the estimation purposes.
I will conclude with a discussion on our ongoing work in the Genographic Project on the study of human population diversity based on evidence of past recombinations (termed recotypes) as genetic markers. The inferred recombinations indicate strong agreement with past in vitro and in silico recombination rate estimates. The correlation between traditional allele frequency based distances and recombinational distances bring further credence to the study of population structure using recotypes. Also, we make the surprising observation that recotypes are more representative of the underlying population structure than the haplotypes they are derived from.
Bio:Laxmi Parida is a research staff member in the Computational Biology Center, at the IBM T.J. Watson Research Center, Yorktown Heights and a visiting professor at New York University. She obtained her PhD in Computer Science, at the Courant Institute of Mathematical Sciences, 1998, in the area of computational genomics. She has authored over seventy-five research papers, and holds several patents related to her algorithmic work. She has been on the program committees of several leading conferences in the area of computational biology, as well as string algorithms. Her research monograph on "Pattern discovery in Bioinformatics: Theory and Algorithms" was published by Chapman Hall and appeared in August, 2007.
[Back]
