Department of Electrical and Computer Engineering

ECpE Distinguished Lecture Series 2007-08

Lecture title: "ReCombinatorics: Combinatorial Algorithms for Studying
the History of Recombination in Populations"

Speaker: Dan Gusfield, Professor, Department of Computer Science, University of California, Davis

Time: 3:30 to 4:30 p.m.

Location: Howe Hall, Alliant Energy-Lee Liu Auditorium

Abstract: The work discussed in this talk falls into the emerging area of Population Genomics. Gusfield will first intro­duce the area and then talk about specific problems and combinatorial algorithms involved in the infer­ence of recombination from population data.
 
A phylogenetic network (or Ancestral Recombination Graph) is a generalization of a tree, allowing struc­tural properties that are not tree-like.  With the growth of genomic and population data (coming for ex­ample from the HAPMAP project) much of which does not fit ideal tree models, and the increasing ap­preciation of the genomic role of such phenomena as recombination (crossing-over and gene-conversion), recurrent and back mutation, horizontal gene transfer, and mobile genetic elements, there is greater need to understand the algorithmics and combinatorics of phylogenetic networks.
 
In this talk, Gusfield will survey a range of our recent results on phylogenetic networks with recombination and show applications of these results to several issues in Population Genomics: Association Mapping; Finding Recombination Hotspots in genotype sequences; Imputing the values of missing haplotype data; Deter­mining the extent of recombination in the evolution of LPL sequences; Distinguishing the role of cross-over from gene-conversion in Arabidopsis; Characterizing some aspects of the haplotypes produced by the program PHASE; Studying the effect of using genotype data in place of haplotype data, imputing missing data, finding optimal recombination mosaics, etc.

Speaker biography: Gusfield’s primary interests involve the efficiency of algorithms, particularly for problems in combi­natorial optimization and graph theory.  These algorithms have been applied to study data security, sta­ble matching, network flow, matroid optimization, string/pattern matching problems, molecular se­quence analysis, and optimization problems in population-scale genomics.  Currently, he is focused on string and combinatorial problems that arise in computational biology and bioinformatics.  He served as chair of the computer science department at the University of California, Davis from July 2000 until August 2004, and is now the founding Editor-in-Chief of The IEEE/ACM Transactions of Computational Biology and Bioinformatics.

Additional details: The seminar is co-hosted by the Department of Computer Science and Department of Mathematics.