McGill University - School of Computer Science

Algorithms Seminar Fall 2001

Everybody is welcome!

DATE: Wednesday, October 31rst
TIME: 4:30 PM - 5:30 PM
PLACE: McConnell 320
TITLE: From consensus trees to supertrees
SPEAKER: David Bryant, School of Computer Science, McGill University

Phylogenetics is the study, and reconstruction, of evolutionary history. Following Darwin, this history is generally depicted by means of a leaf-labelled tree, the labels representing existant species and the internal nodes representing hypothesized ancestral species. Combinatorial problems associated with these structures, and relationships between them, have kept a community of mathematicians and computer scientists busy for some time.

I will be discussing a particular combinatorial problem: given a collection of trees how can we combine these in some systematic way into one representative tree. Constructing trees (e.g. by likelihood methods) is computationally difficult, so the facility to combine trees with overlapping leaf sets would be highly desirable, especially as part of a divide and conquer type approach. This is the supertree problem.

There is a family of methods for combining trees on the same leaf set (consensus tree methods). I propose ways to extend these to supertree consensus methods, and algorithmic tricks that may be employed to construct them.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at Algorithms Seminar organization.