DIMACS Seminar on Math and CS in Biology


Some combinatorial problems of evolutionary trees


Dr. Laszlo Szekely
Eotvos University, Budapest, Hungary


Seminar Room 431, CoRE Building,
Busch Campus, Rutgers University


3:00 PM
Monday, February 27, 1995


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

Document last modified on February 21, 1995