What does efficient Hessian computation have to do with inferring evolutionary history?

Event Sponsor: 
LANS Informal Seminar
Start Date: 
Apr 28 2010 - 3:00pm to 4:00pm
Building/Room: 
Bldg 240 Conference Center 1404-1405
Location: 
Argonne National Laboratory
Speaker(s): 
Andrew Lyons
Speaker(s) Title: 
MCS
Host: 

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.

Miscellaneous Information: