Test for between trees

Question

[sam]

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?

[Biomonika (Noolean)]

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

Answer 1

[Brice Sarver]

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.