# Parameterized Algorithms in Bioinformatics: An Overview
## 5 Phylogenetics
### Combining and Comparing Phylogenies
#### 5.2.3 Consensus by Removing Edges--Agreement Forests and Tree Distances
!6^{k})\) time [218] (using the mentioned preprint-kernel); (2) its close sibling, the replay distance, which admits a formulation as \"maximum endpoint agreement forest\", is conjectured to be NP-hard to decide but admits an \(O^{*}(16^{k})\)-time algorithm [218]; (3) the \"temporal hybridization number\", denoting the smallest amount of reticulation required to explain trees with a temporal network, which was shown to be NP-hard for two trees [219] but admits an \(O^{*}((9k)^{9k})\)-time algorithm [220]; and (4) the parsimony distance, which is NP-hard [221; 222] but can be solved in \(O^{*}(1.618^{38k\textsl{{}_{\text{TRB}}}})\) time [223], where \(d_{\text{\text{\text{\text{\text{\text{\text{\text{\text{\text  
differing arbitrarily from the corresponding species tree. To better understand how a family of genes developed in the genome of a concurrently developing set of species, we can compute an \"embedding\" of the gene tree nodes to the edges of the species phylogeny called a _reconciliation_ (see Figure 10). Reconciliations also allow drawing conclusions when comparing phylogenies of co-evolving species such as hosts/parasites or flowers/pollinators. More formally, a _DL-reconciliation_ of a (gene-)phylogeny \(G\) with a (species-)phylogeny \(S\) is a pair \((G^{\prime},r)\) where \(G^{\prime}\) is a subdivision of \(G\) and \(r:V(G)\to V(S)\) is a mapping such that:  
1. for all arcs \(uv\) of \(G\), either \(r(u)=r(v)\) (in which case \(u\) is called \"duplication\") or \(r(v)\) is a child of \(r(u)\) (in which case \(u\) is called \"speciation\");
2. for arcs \(uv\) and \(uw\) in \(G\), we have \(r(u)=r(v)\iff r(u)=r(w)\) (that is, no node of \(G\) can be a speciation and a duplication at the same time); and
3. if \(u\) is a leaf in \(G\), then \(r(u)\) is a leaf labeled with the contemporary species that \(r(u)\) was sampled in. We can then define the number of losses in \((G^{\prime},r)\) as the sum over all speciations \(u\) of the outdegree of \(r(u)\) in \(S\) minus the outdegree of \(u\) in \(G^{\prime}\). If horizontal transfers are allowed, Condition (a) is replaced by (a') for all arcs \(uv\) of \(G\), either \(r(u)=r(v)\) (in which case \(u\) is called \"duplication\") or \(r(v)\) is a child of \(r(u)\) (in which case \(u\) is called \"speciation\"), **or \(r(v)\) is incomparable to \(r(u)\) (in which case \(u\) is called a \"transfer\" and \(uv\) is called a \"transfer arc\")**, and Condition (b) is restricted to non-transfer arcs, and each transfer with out-degree one causes an additional loss. In this case, we call \(r\) a _DTL-reconciliation_. Since, in reality, transfers occur only between species existing at the same time, Condition (a') introduces further restrictions. In particular, a reconciliation \(r\) is called _time-consistent_ if \(G\) can be \"dated\", that is, there is a mapping \(t:V(G)\to\mathbb{N}\) such that, for all arcs \(uv\) of \(G\), we have 1. \(t(u)\leq t(v)\); and 2. \(t(u)=t(v)\) if and only if \(uv\) is a transfer arc of \(G\) under \(r\). A DTL-reconciliation may be time-inconsistent if, for example, there are transfer arcs \(uv\) and \(xy\) such that \(u\) and \(x\) are ancestors of \(y\) and \(v\), respectively, in \(G\). Now, the parsimonious principle is used to define an optimization criterion. To this end, each evolutionary event is given a cost such as to reflect how unlikely it is to see a certain event. By the biological setup, it is usually assumed that speciations have cost zero. Reconciliation (REC)  
**Input:** species tree \(S\), gene tree \(G\), mapping \(\sigma:\mathcal{L}(G)\to\mathcal{L}(S)\), costs \(\lambda,\delta,\tau\in\mathbb{N}\), some \(k\in\mathbb{N}\)  
**Question:** Is there an embedding of \(G\) in \(S\) with cost at most \(k\)? Figure 10: Two different reconciliations of the same gene tree with the same species tree. A small node \(u\) drawn in an edge \(xy\) of the species tree (large outer tree) indicates that the reconciliation maps \(u\) to \(y\).