| 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.