{"444651":{"#nid":"444651","#data":{"type":"event","title":"ARC Colloquium: Dan Gusfield - UC Davis","body":[{"value":"\u003Cp\u003EPlease note: talk is at 4 pm on Wednesday.\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u0026nbsp;\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\u003Ch2 align=\u0022center\u0022\u003EDan Gusfield - UC Davis\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EWednesday, September 9, 2015\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West - 4:00 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Refreshments will be served in 1116W at 4 pm)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EPhylogenetics Through the Lens of Chordal Graph Theory\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThe evolutionary history of a set of species is generally described by a hylogenetic tree.\u0026nbsp; 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 \u0026nbsp;non-binary states.\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EThe 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.\u003C\/p\u003E\u003Cp\u003EIn this talk, I discuss our work on exploiting the chordal graph approach to solve and study multi-state perfect phylogeny and related problems.\u0026nbsp; I will discuss how the problem relates to minimal triangulation, 2-SAT, integer linear programming, and undirected tree compatibility.\u0026nbsp; 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.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EDan Gusfield of UC Davis will give a talk at the ARC Center Colloquium on Sept. 9 at 4 pm in Klaus 1116 West.\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"Klaus 1116 West at 4 pm  (Note: different day and time.)"}],"uid":"27466","created_gmt":"2015-09-04 08:48:16","changed_gmt":"2017-04-13 21:18:23","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-09-09T17:00:00-04:00","event_time_end":"2015-09-09T18:00:00-04:00","event_time_end_last":"2015-09-09T18:00:00-04:00","gmt_time_start":"2015-09-09 21:00:00","gmt_time_end":"2015-09-09 22:00:00","gmt_time_end_last":"2015-09-09 22:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/www.arc.gatech.edu\/","title":"Algorithms \u0026 Randomness Center (ARC)"}],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"},{"id":"140451","name":"Phylogenetics Through the Lens of Chordal Graph Theory"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDani Denton\u003Cbr \/\u003Edenton at cc dot gatech dot edu\u003Cbr \/\u003E\u003Cbr \/\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}