How to generate all possible evol. trees

Frank Visser fvisser at caos.kun.nl
Wed Jun 22 08:52:11 EST 1994


Hello, I have got a kind of complicated question regarding generating
evolutionary trees. I will try to formulate the problem as clear as I can.

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 method of calculating the number of trees is known 
(Fn = number of trees for n species):
 
Odd number of species: 
  Fn = (Fn-1 * F1 + Fn-2 * F2 + .... + Fn/2+1 * Fn/2-1)
Even number of species:
  Fn = ( Fn-1 * F1 + Fn-2 * F2 + ..... + Fn/2 *((F4+1)/2) ) 

At first glance, the problem seemed rather simple, but I (as the
programmer whom the question was asked) found soon enough that there is no
real obvious solution. All methods I used were either to strong (ignoring
some possibilities) or to weak (generating same trees).

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

---
Frank Visser                | Gods wegen zijn duister, en zelden aangenaam
e-mail: fvisser at caos.kun.nl | 
CAOS/CAMM center            |  		         
K. Universiteit Nijmegen    |



More information about the Mol-evol mailing list