[Biopython] Tree Comparison in BioPython

[阮铮]

Thanks Eric,


I will check your suggestions to see if it can get my problem solved.


Best,
Zheng




------------------ Original ------------------
From:  "Eric Talevich"<eric.talevich at gmail.com>;
Date:  Mar 23, 2013
To:  "阮铮"<rz1991 at foxmail.com>; 
Cc:  "biopython"<biopython at lists.open-bio.org>; 
Subject:  Re: [Biopython] Tree Comparison in BioPython



Hi Zheng,

The usual way to do this is the Robinson-Foulds metric. It's not implemented directly in Biopython yet, but two programs that can do it are "treedist" in Phylip (a.k.a. ftreedist in Embassy, in the Debian package "embassy-phylip"), and RAxML with the "-f r" option. The Python library DendroPy also has a Robinson-Foulds distance function.
 
See:
https://groups.google.com/forum/?fromgroups=#!topic/raxml/JgvxgknTeqw
http://emboss.bioinformatics.nl/cgi-bin/emboss/help/ftreedist
 http://pythonhosted.org/DendroPy/library/tree.html#dendropy.dataobject.tree.Tree.robinson_foulds_distance
 
Hope that helps,
Eric
 

On Fri, Mar 22, 2013 at 4:02 PM, 阮铮 <rz1991 at foxmail.com> wrote:
 Hi,
 
 I was wondering if there is any tree comparison support in BioPython? I want to know if two trees are topologically the same.
 
 
 The idea I have now is to convert trees into an adjacency matrix and check their equality. This is not easy because internal node typically don't have a name and the structure of the adjacency matrix may be different. Or I may go through all internal nodes and check if they have the same terminals. This idea is also not straightforward as typically for an internal node in one tree I have to compare it against all the internal nodes in the other tree to potentially find a match.
 
 
 Is there any suggestions? Thanks!!
 
 
 Best,
 Zheng
 
 
_______________________________________________
 Biopython mailing list  -  Biopython at lists.open-bio.org
 http://lists.open-bio.org/mailman/listinfo/biopython