COMPUTER SCIENCE COLLOQUIUM

The quartet distance between general trees

Christian Nørgaard Storm Pedersen Department of Computer Science University of Aarhus

Monday, September 19, 2005, at 14:15 Seminar Room

ABSTRACT

Trees describing the relationship for a set of species are central in evolutionary biology and bioinformatics, and quantifying differences between such evolutionary trees is an important task when gathering and extracting knowledge from a set of predicted trees. One previously proposed measure for this is the quartet distance. The quartet distance between two unrooted evolutionary trees is the number of quartets -- sub-trees induced by four leaves -- that differs between the trees. Previous algorithms focus on computing the quartet distance between binary trees. In this talk we dicuss the problem of computing the quartet distance between two unrooted evolutionary trees of arbitrary degrees and present algorithms for computing this distance in time O(n² d²) or O(n³), where n is the number of species and d is the maximum degree of the input trees.

Host: Jørgen Bang-Jensen

---

SDU HOME | IMADA HOME | Previous Page

---

Last modified: Thu Aug 25 09:50:52 CEST 2005

Joan Boyar (joan@imada.sdu.dk)