# 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

dimacs-www@dimacs.rutgers.edu
Document last modified on February 21, 1995