# Parameterized Algorithms in Bioinformatics: An Overview
## 5 Phylogenetics
### Combining and Comparing Phylogenies
#### 5.2.3 Consensus by Removing Edges--Agreement Forests and Tree Distances
Herein, an \(rSPR\) (rooted subtree prune and regraft) _move_ consists of removing (\"pruning\") an arc \(uv\) from a tree and \"regrafting\" it onto another arc \(xy\), that is, subdividing \(xy\) with a new node \(z\) and inserting the arc \(zv\). The problem is known to be NP-hard and algorithms parameterized by \(k\) have been extensively studied and improved. An initial \(O(4^{k}n^{4})\)-time algorithm [187; 194] was improved to \(O(3^{k}n)\) time [187], \(O(2.42^{k}n)\) time [195], \(O(2.344^{k}n)\) time [196], and the current best \(O(2^{k}n)\)-time algorithm by [PERSON] [183]. In contrast, a kernel with 28\(k\) taxa [193] has stood since 2005. For \(t>2\) trees, rMAF can be decided in \(O^{*}(6^{k})\) time [197] and \(O(3^{k}nt)\) time [190]. [PERSON] [198] showed that using \"soft\"-display, rMAFs still correspond to computing the rSPR distance between two _multifurcating_ trees. This problem can be solved in \(O^{*}(4^{k})\) time [199] and in \(O(2.42^{k}n)\) time [183; 200] and admits a kernel with 64\(k\) taxa [198; 201]. For \(t>2\) trees, the multifurating rMAF problem is solvable in \(O(2.74^{k}3^{n}5)\) time [202]. Notably, [PERSON] et al. [202] also considered the \"hard\" version of the problem and presented an \(O(2.42^{k}3^{n}4)\)-time algorithm for it. **Acyclic Agreement Forest. **: The size of a MAAF of two rooted binary trees \(T_{1}\) and \(T_{2}\) is exactly one more than the minimum number of reticulations found in any phylogenetic network displaying both \(T_{1}\) and \(T_{2}\)[192] and this relation holds also if \(T_{1}\) and \(T_{2}\) are _non-binary_[203]. Deciding this number is known as the Hybridization Number (HN) problem and it has been shown to be NP-hard by [PERSON] and [PERSON] [204]. The problem can be solved in \(O(3^{n}n)\) time  
Figure 9: Illustration of (acyclic) agreement forests. by crawling a bounded search-tree [205]. In 2009, [PERSON] and [PERSON] claimed an \(O(3^{k}n\log n)\)-time algorithm, which they later retracted and replaced by an \(O(3.18^{k}n)\)-time algorithm [195; 183]. For \(t=3\) binary trees, HN can be decided in \(O^{*}(c^{k})\) time, where \(c\) is an \"astronomical constant\"[206]. Concerning preprocessing, a kernel with at most \(9k\) taxa is known [188; 201] and this kernelization result has been generalized to the case of deciding HN for \(t>2\) binary trees (in which case HN and MAAF no longer coincide) by [PERSON] and [PERSON] [207], showing a kernel with \(20k^{2}\) taxa for this case, which has again been generalized to \(t>2\) non-binary trees by [PERSON] et al. [208], showing a kernel with at most \(20k^{2}(\Delta-1)\) (and at most \(4k(5k)^{t}\)) taxa [208]. For MAAF with \(t=2\) non-binary trees, [PERSON] and [PERSON] [203] showed a linear bikernel (that is, a kernelization into a different problem, see [209]) with \(89k\) taxa, which implies a quadratic-size classical kernel. For this setting, algorithms running in \(O^{*}(6^{k}t)\)[210] and \(O^{*}(4.83^{k})\)[211] time are also known. **Notes. ** Any algorithm for binary uMAF, rMAF, and MAAF with running time \(f(k)n^{O(1)}\) can be turned into an algorithm running in \(f(\ell)n^{O(1)}\), where \(\ell\) is the level of any binary network displaying the two input trees [212]. Furthermore, all three agreement forest variants are fixed-parameter tractable for the treewidth of the display graph of the input trees [213] (see corresponding results for unrooted Tree Consistency[149; 150]). The rSPR distance has been generalized to a distance measure for phylogenetic networks called SNPR and its computation is fixed-parameter tractable [214] parameterized by the distance. Variations of the discussed distance measures include: (1) the uSPR distance, which does not have an agreement-forest formulation, is NP-hard to decide [215], admits a kernel with \(76k^{2}\) taxa [216] (in a preprint, [PERSON] and [PERSON] [217] claimed an improvement to \(28k\) taxa), and can be calculated in \(O^{*}((28k)!