ARC Colloquium: Dan Gusfield - UC Davis

Event Details

Dani Denton
denton at cc dot gatech dot edu


Summary Sentence: Klaus 1116 West at 4 pm (Note: different day and time.)

Full Summary: Dan Gusfield of UC Davis will give a talk at the ARC Center Colloquium on Sept. 9 at 4 pm in Klaus 1116 West.

Please note: talk is at 4 pm on Wednesday.

 Algorithms & Randomness Center (ARC)

Dan Gusfield - UC Davis

Wednesday, September 9, 2015

Klaus 1116 West - 4:00 pm

(Refreshments will be served in 1116W at 4 pm)



Phylogenetics Through the Lens of Chordal Graph Theory


The evolutionary history of a set of species is generally described by a hylogenetic tree.  The combinatorial structure of phylogenetic trees is very well understood when biological characters can only take on two states. But, when characters can take on more than two states, the combinatorial structure is much less understood. The Multi-State Perfect Phylogeny (MPP) problem addresses the case of  non-binary states. 

The MPP problem was initially defined (using different terminology) in a 1975 paper by Peter Buneman that establishes a deep relationship between the MPP problem and the class of graphs called chordal graphs. It showed a how to view the multi-state perfect phylogeny problem as a problem of triangulating non-chordal graphs. While that result has been used in mathematical results, it was not widely exploited as a computational tool.

In this talk, I discuss our work on exploiting the chordal graph approach to solve and study multi-state perfect phylogeny and related problems.  I will discuss how the problem relates to minimal triangulation, 2-SAT, integer linear programming, and undirected tree compatibility.  I will also 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.

Related Links

Additional Information

In Campus Calendar

College of Computing, School of Computer Science, ARC

Invited Audience
Undergraduate students, Faculty/Staff, Public, Graduate students
Algorithm and Randomness Center, ARC, Computational Complexity, Computational Learning Theory, Georgia Tech, Phylogenetics Through the Lens of Chordal Graph Theory
  • Created By: Dani Denton
  • Workflow Status: Published
  • Created On: Sep 4, 2015 - 4:48am
  • Last Updated: Apr 13, 2017 - 5:18pm