Center for Computational Molecular Biology Seminar
"Imperfect Ancestral Recombination Graph Reconstruction Problem: A Hierarchy of Upper Bounds"
Fumei Lam, Brown University
Wednesday, May 21, 2008 at 4:00 P.M.
Room 241 Swig Boardroom (2nd Floor CIT)
Reconstruction of evolutionary histories is a fundamental problem in computational biology. It has been established that accurately representing complete evolutionary histories requires an underlying model that incorporates non-tree operations, corresponding to the mixing of genetic material from ancestral sequences. In this talk, we will address the problem of finding parsimonious evolutionary histories with both hybridization and mutation events (the Imperfect Ancestral Recombination Graph Reconstruction Problem). The power of our framework is the connection between our formulation and the Directed Steiner Arborescence Problem in combinatorial optimization. We implement linear programming techniques as well as heuristics for the Directed Steiner Arborescence Problem and apply these algorithms on simulated and benchmark data sets.
This is joint work with Ryan Tarpine and Sorin Istrail.
Host: Sorin Istrail
| Page Owner: Webmaster | Last Modified: Mon May 12 10:18:47 2008 |