Agreement forest
From Wikipedia, the free encyclopedia
In the mathematical field of graph theory, an agreement forest for two given (leaf-labeled, irreductible) trees is any (leaf-labeled, irreductible) forest which can, informally speaking, be obtained from both trees by removing a common number of edges.
Agreement forests first arose when studying combinatorial problems related to computational phylogenetics, in particular tree rearrangements.[1]
Recall that a tree (or a forest) is irreductible when it lacks any internal node of degree 2. In the case of a rooted tree (or a rooted forest), the root(s) are of course allowed to have degree 2, since they are not internal nodes. Any tree (or forest) can be made irreductible by applying a sequence of edge contractions.
An irreductible (rooted or unrooted) tree T whose leaves are bijectively labeled by elements of a set X is called a (rooted or unrooted) X-tree. Such a X-tree usually model a phylogenetic tree, where the elements of X (the taxon set) could represent species, individual organisms, DNA sequences, or other biological objects.
Two X-trees T1 and T2 are said to be isomorphic when there exists a graph isomorphism between them which preserves the leaf labels. In the case of rooted X-trees, the isomorphism must also preserves the root.
Given a X-tree T and a taxon subset Y ⊆ X, the minimal subtree of T that connects all leaves in Y is denoted by T(Y). When T is rooted, then T(Y) is also rooted, with its root being the node closest to the original root of T. This T(Y) subtree needs not be a Y-tree, because it might not be irreductible. We therefore further define the restricted subtree T|Y, which is obtained from T(Y) by suppressing all internal nodes of degree 2, yielding a proper Y-tree.