September 15, 2014: Seminar - Dan Gusfield: "The Multi-State Perfect Phylogeny Problem: Modeling Infinite Alleles"

Seminar Announcement

The Multi-State Perfect Phylogeny Problem: Modeling Infinite Alleles

Dr. Dan Gusfield
University of California at Davis
Monday, September 15, 2014
11:00 a.m., 1000 SEO Building


A binary perfect phylogeny is the graph-theoretic analog of what is called the basic coalescent model in population genetics, under the infinite-sites model of mutation. A multi-state perfect phylogeny is the graph-theoretic analog of the basic coalescent under the infinite-alleles model of mutation. The infinite alleles modeled population genetic data before the SNP-era when the infinite sites model became dominant. However, the infinite alleles model has again become appropriate with the growth of sequence data (four states), and other types of complex biological data.

The multi-state perfect phylogeny has been studied in the computer science literature, but is almost unknown in the population genetics community. In comparison to the binary perfect phylogeny problem, the multi-state perfect phylogeny problem is algorithmically much more complex, and yet connects to a more elegant, deeper body of mathematics.

In this talk, I will introduce the multi-state perfect phylogeny and discuss how it connects to chordal graph theory, minimal triangulation, 2-SAT, and integer linear programming, and the infinite-alleles model in population genetics. I will discuss generalizations of the classic four-gametes condition, which characterizes a binary perfect phylogeny, to conditions that characterize multi-state perfect phylogenies, and I will identify open questions in this field.


Dan Gusfield's primary interests involve the efficiency of algorithms, particularly for problems in combinatorial optimization and graph theory. These algorithms have been applied to study data security, stable matching, network flow, matroid optimization, string/pattern matching problems, molecular sequence analysis, and optimization problems in population-scale genomics. Currently, Gusfield is focused on string and combinatorial problems that arise in computational biology and bioinformatics. He served as chair of the computer science department at UCD from July 2000 until August 2004, and wasthe founding Editor-in-Chief of The IEEE/ACM Transactions of Computational Biology and Bioinformatics until January 2009. Gusfield's PhD is from UC Berkeley in 1980.

Hosted by: Dr. Bhaskar DasGupta

Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF