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.