Distance among trees

[jmerelo]

Hi, I am trying to find an easy way to implement distance among trees, as in Tree::DAG_Node. I have found some info about Robinson-Foulds distance, but only in the shape of code, and I don't know exactly if it is what I'm looking for. Meanwhile, I make do with this:

use Tree::DAG_Node;
use String::Approx qw(adist);
my $lol1=[['a','b'],['c','d'],['e']];
my $lol2=[['a','b','c'],['d'],['e']];
my $tree1 = Tree::DAG_Node->lol_to_tree( $lol1 );
my $tree2 = Tree::DAG_Node->lol_to_tree( $lol2 );
my $str1 = $tree1->tree_to_lol_notation();
my $str2 = $tree2->tree_to_lol_notation();
my $dist = adist( $str1, $str2 );
print "Distance between $str1 and $str2 is $dist\n";

But it's not exactly what I'm looking for, since changing a node from one subtree to another would give distance=7 (or 4 in the case above). Can anybody help me? Pointers to RF distance definition anywhere? Thanks!

[cacharbe]

A quick google search gave me these (this and this which look promising) and also lead me to this, which should also prove useful.

C-.

Update:My final suggestion, as I mentioned below, would be to talk to some of the people at Journal of Graph Algorithms and Applications. Someone like Mihalis Yannakakis, I mean, check out the first publication on his bibliography.

[jmerelo]

Already followed those leads, even emailed the guy. Looks promising, but uses its own version of trees, creates "bipartition" of them, and does not contain a detailed explanation of the algorithm. I could try and glean it by following the code, but I'm not sure it's worth the while.

[cacharbe]

Looks like you're going to have to find a copy of "Lecture notes in mathematics" --Springer-Verlag, Germany(1979) to find out their proposed algorithm (or one of Foulds' other books, and he seems to have a few), but I found a text description of it here, pg. 4, and a subsequent discussion on the "Deltahedron Method" here, which does give an algorithm, but doesn't necessarily describe it as Foulds'.

Hope that helps,

C-.

Update: After reading the Caccetta/Kusumah text, theirs might be a more interesting algorithm to attempt implementing if you are going to start from scratch.