McGill University - School of Computer Science

Algorithms Seminar 2005

Everybody is welcome!

DATE: Wednesday, February 16th 2004.
TIME: 4:30 PM - 5:30 PM
PLACE: McConnell 320
TITLE: Phylogenetic Tree Reconstruction, A Graph Theoretical Approach
SPEAKER: Sean Kennedy, Dept. of Computer Science, University of Alberta

A fundamental problem in computational biology is the reconstruction of a phylogeny tree for a set of related organisms. One of the graph theoretical approaches is to construct a similarity graph on the set of organisms where adjacency indicates evolutionary closeness. From this similarity graph, a phylogeny is then reconstructed by computing a tree such that the organisms label leaves in the tree and for any pair of adjacent organisms in the similarity graph their distance in the output tree must be less than some pre-specified bound. This is known as the problem of recognizing Steiner powers and computing Steiner roots. For strictly chordal graphs, a linear time construction is shown for the 3-root Steiner problem. Two similar problems are presented, the leaf root problem and phylogeny root problem, and discussed as they relate to strictly chordal graphs.

mailing list info: