Seminar Details:

**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

SPEAKER: Andrew Lyons, *MCS*

LOCATION: Bldg 240 Conference Center 1404-1405, Argonne National Laboratory

[related website]

**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.

Please send questions or suggestions to Debojyoti Ghosh: ghosh at mcs dot anl dot gov.