BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Recent Progress on Multi-State Perfect Phylogeny (Compatibility) P
 roblems - Gusfield\, DM (University of California\, Davis)
DTSTART:20110620T090000Z
DTEND:20110620T100000Z
UID:TALK31785@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:The Multi-State Perfect Phylogeny Problem is an extension of t
 he Binary Perfect Phylogeny (or Compatibility) Problem\, allowing evolutio
 nary characters to have more than two states. The problem is of interest d
 ue to prior elegant mathematical and algorithmic results\, and due to inte
 ger data that is increasingly available. \n\nIn 1975\, Buneman showed a ho
 w to view the Multi-State problem as one of triangulating non-chordal grap
 hs\, but the result has not been widely exploited as a computational tool.
  In this talk\, I discuss our recent work on Multi-State Perfect Phylogeny
  problems\, mostly by exploiting Buneman's result. I will talk about three
  sets of results. \n\nThe first set of results concerns problems that exte
 nd the multi-state problem: The Missing Data (MD) Problem\, where some ent
 ries in the input are missing and the question is whether (bounded) values
  can be imputed so that the full data has a multi-state perfect phylogeny\
 ; The Character-Removal (CR) Problem\, minimizing the number of characters
  to remove so that the resulting data has a multi-state perfect phylogeny.
  Using results on triangulation of non-chordal graphs\, we establish new n
 ecessary and sufficient conditions for the existence of a perfect phylogen
 y with (or without) missing data. This leads to solutions of the MD and CR
  problems using integer linear programming. \n\nThe second set of results 
 concerns generalization of the famous ``four-gametes test" that characteri
 zes the compatibility of binary data. Such a generalization was sought sin
 ce the 1970s. Our new generalization establishes that 3-state data has a p
 erfect phylogeny if and only if every subset of three characters has a 3-s
 tate perfect phylogeny. We also characterize the patterns in the data that
  prohibit a 3-state perfect phylogeny. We briefly discuss efforts to gener
 alize this to more states. \n\nThe third set of results concerns reduction
 s of multi-state data to binary data\, to the 2-SAT problem\, and to spars
 er problem instances.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR