# Parameterized Algorithms in Bioinformatics: An Overview
## 5 Phylogenetics
### Combining and Comparing Phylogenies
#### 5.2.3 Consensus by Removing Edges--Agreement Forests and Tree Distances  
An important biological phenomenon that governs the discordance of gene trees are non-tree-like processes such as hybridization and horizontal gene transfer (HGT) (see also Section 5.3). If a branch in a gene tree corresponds to a horizontal transfer, then we expect that deleting this branch results in a forest, which is in agreement with the other gene trees. This gives rise to the idea of \"agreement forests\", resulting from the deletion of branches in the input phylogenies. Maximum Agreement Forest (MAF)  
**Input:** rooted or unrooted trees \(T_{1},T_{2},\ldots\) on \(\mathcal{X}\) and some \(k\in\mathbb{N}\)  
**Question:** Is there a forest \(F\) with \(\mathcal{L}(F)=\bigcup_{i}\mathcal{L}(T_{i})\), \(F\) has \(\leq k\) trees and each \(T_{i}\) displays \(F\)? Maximum agreement forests come in three major flavors: _unrooted_ maximum agreement forests (uMAFs), _rooted_ maximum agreement forests (rMAFs), and maximum _acyclic_ agreement forests (MAFs). Herein, \"acyclic\" makes reference to the constraint that the \"inheritance graph is acyclic\" (see Figure 9). Formally, the _inheritance graph_ of an agreement forest \(F\) for two trees \(T_{1}\) and \(T_{2}\) has the trees of \(F\) as nodes and an arc \(uv\) if and only if the root of \(u\) is an ancestor of the root of \(v\) in \(T_{1}\) or in \(T_{2}\). Demanding acyclicity of this graph forbids, for example, that a tree \(u\) of \(F\) is \"above\" another tree \(v\) in \(T_{1}\) but \"below\" \(v\) in \(T_{2}\). This definition generalizes straightforwardly to more than two trees \(T_{i}\). In the following, the _size_ of an agreement forest \(F\) is the number of trees in \(F\) and it is equal to the number of branches to remove in each input tree to form (a subdivision of) \(F\) and \(F\) is called _maximum_ if it minimizes this number. For surveys about tree distances and agreement forests, we refer to [PERSON] et al. [182] and [PERSON] [183]. Results.Evidently, results heavily depend on the type of agreement forest we are looking for. Interestingly, each of the three versions corresponds to a known and well-studied distance measure between trees and we thus also include results stated for the corresponding distance-measure. Unrooted Agreement Forest.The size of a uMAF of two binary trees \(T_{1}\) and \(T_{2}\) is exactly equal to the minimum number of \"TBR moves\" necessary to turn \(T_{1}\) into \(T_{2}\)[184; 185] (and vice versa; indeed, this defines a metric and it is called the \"TBR distance\" between \(T_{1}\) and \(T_{2}\)). Herein, a \(TBR\) (tree bisection and reconnection) _move_ consists of removing an edge \(uv\) from a tree (\"bisecting\" the tree) and inserting a new edge between any two edges of the resulting subtrees (\"reconnecting\" the trees), that is, subdividing an edge in each of the subtrees and adding a new edge between the two new nodes. For two trees, deciding uMAF is NP-hard [184], but fixed-parameter tractable in \(k\). More precisely, the problem can be solved in \(O^{*}(k^{O}(k))\) time [185], \(O(4^{k}k^{5}+n^{O(1)})\) time [186], and \(O(4^{k}k+n^{O(1)})\) time [187]. These results make use of the known kernelizations with 15k [185; 188] and 11k taxa [189]. For \(t>2\) binary trees, [PERSON] et al. [190] presented an \(O(4^{k}nt)\)-time algorithm. [PERSON] et al. [191] considered the uMAF problem on multifurating trees, showing that it still corresponds to the TBR problem and can be solved in \(O(3^{k}n)\) time. **Rooted Agreement Forest. **: The size of an rMAF of two rooted binary trees \(T_{1}\) and \(T_{2}\) is exactly one more than the minimum number of \"rSPR moves\" necessary to turn \(T_{1}\) into \(T_{2}\)[192; 193] (and vice versa; indeed, this defines a metric and it is called the \"rSPR distance\" between \(T_{1}\) and \(T_{2}\)).