LANS Informal Seminar
"What does efficient Hessian computation have to do with inferring evolutionary history?"
DATE: April 28, 2010
TIME: 15:00:00 - 16:00:00 Description:
SPEAKER: Andrew Lyons, MCS
LOCATION: Bldg 240 Conference Center 1404-1405, Argonne National Laboratory
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.
TIME: 15:00:00 - 16:00:00
Please send questions or suggestions to Debojyoti Ghosh: ghosh at mcs dot anl dot gov.