Algorithms & Randomness Center (ARC)
Wednesday, September 9, 2015
Klaus 1116 West - 4:00 pm
(Refreshments will be served in 1116W at 4 pm)
Title:
Phylogenetics Through the Lens of Chordal Graph Theory
Abstract:
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.
]]>