Agreement forest


In the mathematical field of graph theory, an agreement forest for two given trees is any 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.

Preliminaries

Recall that a tree is irreductible when it lacks any internal node of degree 2. In the case of a rooted tree, the root are of course allowed to have degree 2, since they are not internal nodes. Any tree can be made irreductible by applying a sequence of edge contractions.
An irreductible tree whose leaves are bijectively labeled by elements of a set is called a -tree.
Such a -tree usually model a phylogenetic tree, where the elements of could represent species, individual organisms, DNA sequences, or other biological objects.
Two -trees and are said to be isomorphic when there exists a graph isomorphism between them which preserves the leaf labels. In the case of rooted -trees, the isomorphism must also preserves the root.
Given a -tree and a taxon subset, the minimal subtree of that connects all leaves in is denoted by. When is rooted, then is also rooted, with its root being the node closest to the original root of. This subtree needs not be a -tree, because it might not be irreductible. We therefore further define the restricted subtree, which is obtained from by suppressing all internal nodes of degree 2, yielding a proper -tree.

Agreement forests

An agreement forest for two unrooted -trees and is a partition of the taxon set satisfying the following conditions:
  1. and are isomorphic for every and
  2. the subtrees in and are vertex-disjoint subtrees of and, respectively.
The set partition is identified with the forest of restricted subtrees, with either or . Therefore, an agreement forest can either be seen as a partition of the taxon set or as a forest of restricted subtrees.
The size of an agreement forest is simply its number of components. Intuitively, an agreement forest of size for two phylogenetic trees is a forest which can be obtained from both trees by removing edges in each tree and subsequently suppressing internal nodes of degree.

Acyclic agreement forests

A raffinement on the above definition can be made, resulting in the concept of acyclic agreement forest.
An agreement forest for two -trees and is said to be acyclic if each of its tree components can be numbered in such a way that if the root of one component is an ancestor of the root of another component in either or, then the number assigned to is lower than the number assigned to.
Another characterization of acyclicity in agreement forest is to consider the directed graph that has vertex set and a directed edge if and only if and at least one of the two following conditions hold:
  1. the root of is an ancestor of the root of in
  2. the root of is an ancestor of the root of in
The directed graph is called the inheritance graph associated with the agreement forest, and we call acyclic if has no directed cycle.

Optimization problems

A agreement forest for and is said to be maximum if it contains the smallest possible number of elements. In this context, it is the agreement between the two trees which is maximized: it explains why computing a maximum agreement forest actually means minimizing its number of components. This leads to two different optimization problems. In both cases, we choose to minimize rather than, because the former corresponds to the number of cuts to be done in each tree in order to obtain.
  • maximal ≠ maximum
  • unrooted MAF corresponds to TBR
  • rooted MAF corresponds to rSPR
  • acyclic MAF corresponds to HYB
  • AFs can be defined on non-binary trees
  • AFs can be defined on more than two trees
  • acyclic agreement forests have a role to play in the computation of HYB on 3 or more trees, but the relationship is much weaker than in the case of 2 trees
  • Complexity
  • FPT algorithms
  • Approximation algorithms
  • Exponential time algorithms