Английская Википедия:Agreement forest
Шаблон:Short description Шаблон:Refimprove
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]
Preliminaries
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 Шаблон:Math whose leaves are bijectively labeled by elements of a set Шаблон:Math is called a (rooted or unrooted) Шаблон:Math-tree. Such a Шаблон:Math-tree usually model a phylogenetic tree, where the elements of Шаблон:Math (the taxon set) could represent species, individual organisms, DNA sequences, or other biological objects.
Two Шаблон:Math-trees Шаблон:Math and Шаблон:Math are said to be isomorphic when there exists a graph isomorphism between them which preserves the leaf labels. In the case of rooted Шаблон:Math-trees, the isomorphism must also preserves the root.
Given a Шаблон:Math-tree Шаблон:Math and a taxon subset Шаблон:Math, the minimal subtree of Шаблон:Math that connects all leaves in Шаблон:Math is denoted by Шаблон:Math. When Шаблон:Math is rooted, then Шаблон:Math is also rooted, with its root being the node closest to the original root of Шаблон:Math. This Шаблон:Math subtree needs not be a Шаблон:Math-tree, because it might not be irreductible. We therefore further define the restricted subtree Шаблон:Math, which is obtained from Шаблон:Math by suppressing all internal nodes of degree 2, yielding a proper Шаблон:Math-tree.
Agreement forests
An agreement forest for two unrooted Шаблон:Math-trees Шаблон:Math and Шаблон:Math is a partition Шаблон:Math} of the taxon set Шаблон:Math satisfying the following conditions:
- Шаблон:Math and Шаблон:Math are isomorphic for every Шаблон:Math and
- the subtrees in Шаблон:Math and Шаблон:Math are vertex-disjoint subtrees of Шаблон:Math and Шаблон:Math, respectively.
The set partition Шаблон:Math} is identified with the forest of restricted subtrees Шаблон:Math}, with either Шаблон:Math or Шаблон:Math (the choice of it begin irrelevant because of condition 1). Therefore, an agreement forest can either be seen as a partition of the taxon set Шаблон:Math or as a forest (in the classical graph-theoretic sense) of restricted subtrees.
The size of an agreement forest is simply its number of components. Intuitively, an agreement forest of size Шаблон:Math for two phylogenetic trees is a forest which can be obtained from both trees by removing Шаблон:Math edges in each tree and subsequently suppressing internal nodes of degree Шаблон:Math.
Rooted case
Acyclic agreement forests
A raffinement on the above definition can be made, resulting in the concept of acyclic agreement forest. An agreement forest Шаблон:Math for two Шаблон:Math-trees Шаблон:Math and Шаблон:Math 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 Шаблон:Math is an ancestor of the root of another component Шаблон:Math in either Шаблон:Math or Шаблон:Math, then the number assigned to Шаблон:Math is lower than the number assigned to Шаблон:Math.
Another characterization of acyclicity in agreement forest is to consider the directed graph Шаблон:Math that has vertex set Шаблон:Math and a directed edge Шаблон:Math if and only if Шаблон:Math and at least one of the two following conditions hold:
- the root of Шаблон:Math is an ancestor of the root of Шаблон:Math in Шаблон:Math
- the root of Шаблон:Math is an ancestor of the root of Шаблон:Math in Шаблон:Math
The directed graph Шаблон:Math is called the inheritance graph associated with the agreement forest Шаблон:Math, and we call Шаблон:Math acyclic if Шаблон:Math has no directed cycle.
Optimization problems
A (rooted, unrooted, acyclic) agreement forest Шаблон:Math for Шаблон:Math and Шаблон:Math is said to be maximum if it contains the smallest possible number of elements (i.e. it has the smallest size). 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 (but related) optimization problems. In both cases, we choose to minimize Шаблон:Math rather than Шаблон:Math, because the former corresponds to the number of cuts to be done in each tree in order to obtain Шаблон:Math.
- 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
Notes
