In Article <Crsx70.5vC at sci.kun.nl>, fvisser at caos.kun.nl (Frank Visser) wrote:
>My officemate is working on a project to 'measure' the difference between
>evolutionary trees of a group of species. For example, assume you have
>four species A, B, C and D. You find an evolutionary tree like this:
>>A B C D A B C D
>| | | | | | | |
> --- --- while another group finds: --- | |
> | | | | |
> -------- ---- |
> | | |
>>The goal is to develop a 'metric' to measure the difference between the
>trees. He uses two different metrics, and is now evaluating them. The
>question he asked is: 'Is it possible to make a program that generates all
>different possible trees for a set of species?'
>A friend of mine is trying now, but also found errors in his algorithm.
>>So, does anyone know an algorithm, or pointers to an algorithm which can
>solve this problem?
PAUP does exactly this, plus evaluating the length of each tree under
user-defined assumptions. It seems to be a bit hard to get right now. You
need to contact the author, David Swofford, at paup at onyx.si.edu
As far as generating a metrtic for comparing the trees, good luck. As far
as I can tell it's a question fraught with problems and there is a lot of
dissension on how one would do it in principle.
Department of Zoology, University of Alberta
wgallin at gpu.srv.ualberta.ca