Question: Test for between trees
0
gravatar for sam
4.7 years ago by
sam130
United States
sam130 wrote:

Hello. Does anyone know of a program or a graph that could compare trees with one another to test whether one tree belongs to the other tree?

 

 

graph algorithms sequence • 948 views
ADD COMMENTlink modified 4.7 years ago by Brice Sarver2.6k • written 4.7 years ago by sam130

What's you representation of the trees? In which file format do you store them?

ADD REPLYlink written 4.7 years ago by Biomonika (Noolean)3.0k
1
gravatar for Brice Sarver
4.7 years ago by
Brice Sarver2.6k
United States
Brice Sarver2.6k wrote:

You need to be a bit more specific. Are you interested in seeing if a given tree is a subtree of another? I'm assuming that this is what you want.

The R library ape will return all subtrees for a given tree (http://svitsrv25.epfl.ch/R-doc/library/ape/html/subtrees.html). I imagine an algorithm structured in the following way:

1. Read in a tree and estimate all subtrees of that tree. Store the subtrees as an object.

2. Calculate a distance metric from your tree to each one of the subtrees. The phangorn library (and others) will calculate the standard bipartition distance (Robinson-Foulds) between pairs of trees; if there is a distance of zero from your tree to one of the subtrees, you know that your tree is identical in branching structure to that subtree.

This can be easily accomplished in R. Hope this helps.

 

ADD COMMENTlink written 4.7 years ago by Brice Sarver2.6k
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 818 users visited in the last hour