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