McGill University - School of Computer Science

Algorithms Seminar Winter 2001

Everybody is welcome!

DATE: Friday, January 19th
TIME: 10:00 AM - 11:00 AM
PLACE: McConnell 103
TITLE: A Polynomial Time Exact Disc-Covering Method
SPEAKER: Jens Lagergren, Royal Institute of Technology (KTH) and Stockholm Bionformatics Centre

For a given set of species, how to create a phylogenetic tree (evolutionary tree) is a well-studied problem in biology and computer science. Usually the species are represented by sequence data (e.g. DNA). Convergence rates, i.e. the sequence length sufficient for (w.h.p.) finding the true tree, is an important property of a phylogenetic tree construction algorithm.

The Disc-Covering Method (DCM) was presented by Huson et al. The idea is to boost the convergence rate by other algorithms. They gave two variations of it: one that provably boosts the convergence rate but runs in exponential time, and a heuristic that runs in polynomial time. We present an algorithm with both of these desirable properties, i.e. it provably boosts the convergence rate and runs in polynomial time.

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