- This event has passed.
LANS Informal Seminar: Andrew Lyons
April 28, 2010 @ 15:00 CDT
Seminar Title: What does efficient Hessian computation have to do with inferring evolutionary history?
Speaker: Andrew Lyons, MCS
Date/Time: 2010-04-28 15:00
Location: Bldg 240 Conference Center 1404-1405
Description:
In biology, the ancestral relations among a set of species with a common ancestor are described by a phylogenetic tree (also known as a phylogeny). Given a set of species that are described in terms of their characteristics (in matrix form), the Perfect Phylogeny problem (PP) asks whether there is a phylogeny that is consistent with respect to these characteristics. In graph terms, this question asks whether a given graph can be made chordal (or ‘triangulated’) by adding edges under certain constraints.
A problem that is perhaps more familiar to LANS is the Acyclic Coloring problem (AC), which models the efficient computation of sparse Hessian matrices using substitution-based methods. Both of these problems are NP-complete in the general case, and remain so even under severe restrictions.
In this talk, I will demonstrate positive algorithmic results for both the PP and AC problems by means of a deep connection involving the tree structure of chordal graphs and the powerful notion of treewidth. These results include constructive, polynomial-time algorithms when the input graph belongs to the relatively large class of weakly chordal graphs, which generalizes a number of known results.
Though I will assume some familiarity with basic graph-theoretic concepts, I will not assume any knowledge of evolutionary biology.