Comparing trees

There are (at least) two situations in which we compare trees.

• One can compare a tree to the taxonomy, or to a supertree, to ask how compatible or disruptive it is. This is of interest if you're doing quality control on a new tree, or if you're considering making a new supertree that incorporates the tree.
• One can compare a supertree to one or more of the trees that it has contributed to it, to understand what contributions a tree has made to the supertree, or to identify the trees that provided certain information.

When we compare trees, we first establish a 1-1 correspondence (perhaps partial) between their tips, then make comparisons between a node in one tree and a node in the other tree.

Assume that each tip has a label that is unique within its tree, and that tips correspond if and only if they have the same label.

Let S = the set of shared labels, and for any node N in t (or N’ in t’), let S(N) be the members of S that are labels of tips reachable tipward from N. Define:

• N is congruent with N’ if S(N) and S(N’) are the same set.
• N resolves N’ if S(N) is a proper subset of S(N’).
• N conflicts with N’ if S(N) and S(N’) have a nonempty intersection, and neither contains the other.
• N and N’ are independent if S(N) and S(N’) do not intersect.

Congruence may be further classified as follows:

• N supports N’ if (1) N and N’ are congruent and (2) N is the only node in t congruent with N’ (should be equivalent to the definition here)
• N supports a path containing N’ if (1) N and N’ are congruent and (2) N’ is only one of two or more nodes in t’ that N is congruent to (the reverse relation here is called partial_path_of.)

In the case of N resolves N', we are usually interested in the smallest N’ that N resolves (or the largest N that resolves N’), since other cases of resolution follow from that one in uninteresting ways. (One might even want a name for this relation: N’ is the shallowest (smallest, least deep) node that N resolves.)

S(N) is elsewhere written L(N) ∩ L(t’).

Related: RCC-5 articulations, e.g. see this article

Predecessor documents:

• google doc on conflict analysis
• synthesis annotations proposal