Combinatorics Seminar 2015

Speaker: Stefan Grünewald, CAS-MPG Partner Institute on Computational Biology

Date: Tue, Mar 17, 2015

Time: 16:10 - 17:10

Venue: Room 1106

Title: Quartet-based tree comparison


Phylogenetic (i.e. leaf-labeled) trees are used in biology to display the evolutionary relationship between species and other taxonomic units. There are various applications that require measuring the dissimilarity between two trees with identical leaf set. One such measure is the quartet distance that counts the number of sets of $4$ leaves where the two trees differ.

It can easily be seen that, for binary trees (trees where all interior vertices have degree $3$) with at least $6$ leaves, two trees cannot be different for every $4$ leaves. It was conjectured by Bandelt and Dress in 1986 that the maximum quartet distance between binary trees on $n$ leaves, divided by the number of all $4$-sets, will converge towards $2/3$.

In my talk, I will give a proof of the 2/3-conjecture for the special case that one of the trees is a caterpillar (a path with leaves attached to it). Then I will show that the quartet distance can be used to measure dependence between random variables and compare it with well-known methods like the Maximum Information Coefficient and Distance Correlation. Finally, I will sketch our recently discovered complete proof of the 2/3-conjecture.

Slides: View slides