IUBio Biosequences .. Software .. Molbio soft .. Network News .. FTP

How to generate all possible evol. trees

Warren Gallin wgallin at gpu.srv.ualberta.ca
Wed Jun 22 10:27:53 EST 1994

In Article <Crsx70.5vC at sci.kun.nl>, fvisser at caos.kun.nl (Frank Visser) wrote:

[stuff deleted]

>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?' 

[stuff deleted]

>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?
>Thanks, Frank

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.

Warren Gallin,
Department of Zoology, University of Alberta
wgallin at gpu.srv.ualberta.ca

More information about the Mol-evol mailing list

Send comments to us at biosci-help [At] net.bio.net