DIMACS Seminar on Math and CS in Biology

Title:

Some combinatorial problems of evolutionary trees

Speaker:

Dr. Laszlo Szekely

Eotvos University, Budapest, Hungary

Place:

Seminar Room 431, CoRE Building,

Busch Campus, Rutgers University

Time:

3:00 PM

Monday, February 27, 1995

Abstract:

Tree reconstruction based on the parsimony principle led to the following enumeration problem: what is the average length of labelled binary trees with a given leaf colouration? This problem was answered for 2 colours and is still open in general. The solution of the general problem seems to require a better understanding of the length of a tree. One step has been made in this direction: a min-max theorem for the length of the leaf-coloured tree. From the point of view of combinatorial optimization, this is a min-max theorem for a type of multiway cut problem.

Tree reconstruction under the Kimura-3 model is possible from the probability distribution of leaf colourations, if the probability for not changing is big enough on all edges. The technique to be used is the Fourier transform. However, tree reconstrion turns into impossible, if sites evolve by arbitrary distributions.

The results to be mentioned are joint results P.L. Erdos, M. Hendy, D. Penny, and M.A. Steel.

Upcoming talks:

March 6, Dr. Vrijenhoek
March 13, SPRING BRK
March 20, Protein Structure Workshop