how to generate all possible evol. trees trees

FrohlichM frohlichm at STARBASE1.CALTECH.EDU
Wed Jun 22 16:15:51 EST 1994


Frank,

Do you actually want to draw ALL trees, each in its entirety, including
clades that are the same in many different trees?  You may run out of
computer memory.

I and others have used algorithms that draw small trees, calculate attributes
of them, and combine these to calculate attribures of larger trees.  

If you really want to draw all trees it isn't difficult.  Here is an
algorithm:

Describe trees by parenthetical notation, with letters or numbers to
represent the terminal taxa.  Put parentheses around each terminal taxon. 
Include no other punctuation in the tree description.

Start with a tree consisting of a single terminal taxon and its parentheses:

(A)

Successively generate a lists of all trees with n + 1 terminal taxa from a
list of all trees with n taxa using this rule:

For each tree in the list of those with n terminal taxa, and for each
occurrence of a left parenthesis in each of these trees, insert the next
taxon to left of left of the parenthesis.  You also have to insert another
left parenthesis to the left of the newly inserted taxon.   Scan to the
right, counting left and right parentheses to find the correct place to
insert a right parenthesis.  Add each of these new trees to the developing
list of trees with n + 1 terminal taxa.

This will give all the trees.

Good luck defining an appropriate metric.

Mike Frohlich



More information about the Mol-evol mailing list