Program for tree comparison

Warren Frank Lamboy wfl1 at cornell.edu
Thu Apr 13 15:05:55 EST 1995

In article <3mdtof$8sj at sunserver.lrz-muenchen.de>,
strimmer at wap18.zi.biologie.uni-muenchen.de (Korbinian Strimmer) wrote:

> To all tree reconstructors out there! 
> Using the programs from the PHYLIP package of Joe Felsenstein I have
> produced quite a huge number of trees written down as specified within
> the "New Hampshire" standard for computer readable trees (an example 
> for an unrooted tree may be  (a, b, ((c, d), e)); ) Now I want to compare
> all these trees (that are all in one big treefile) to one specific tree
> that is also given in another file. I want to count how many trees in the
> big treefile are identical to the specified tree. As there are many
> possibilities for writing down a given tree in the "New Hampshire"
> form one can not simply compare the two files with a text editor
> but one must think of another way. I suppose that this program must 
> work in a way Consense (from PHYLIP) works, but Consense alone gives
> no answer to my problem.
> I am very sure that many people must have encountered this problem before,
> and I am sure that there exists already a solution to this. If you know
> how to deal with this problem please give me a hint and contact me!!
> Thank you
> Korbinian Strimmer
> ----------------------------------
> strimmer at zi.biologie.uni-muenchen.de

If I understand your problem correctly, I think that one way to do this
would be to compute Robinson and Fould's partition metric between each tree
in the data set and the given specific tree.  A value of 0 for the
partition metric would indicate that the two trees are identical.  (The
partition metric is a count of the number of branch contractions and node
expansions that it takes to convert one tree into another.  If none are
needed, then the trees are the same.)  Unfortunately, I know of no program
that computes this value for you--so I am afraid that this may not be much
help unless you are a programmer or have access to one.  The reference is:
Robinson, D.F. and L.R. Foulds. 1981.  Comparison of phylogenetic trees. 
Mathematical Biosciences 53:  131-147.  Sorry I can't be of more help.

Warren F. Lamboy                            "It's easy if you know how to
                                             do it, but it's impossible if
                                             you don't know how to do it."

More information about the Mol-evol mailing list

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