# Parameterized Algorithms in Bioinformatics: An Overview
## 5 Phylogenetics
### Combining and Comparing Phylogenies
#### 5.2.3 Consensus by Removing Edges--Agreement Forests and Tree Distances
Boxes, triangles, circles, and hexagons represent leaves, duplications, speciations, and transfers, respectively, while crosses are losses. The left reconciliation has three duplications and four losses, while the right has two duplications, two losses, and one transfer. We specify the allowed type of embedding by prepending \"DL\", \"DTL\", etc. to the problem name. The study of the formal reconciliation problem was initiated by [PERSON] et al. [225] and [PERSON] et al. [226] and is surveyed in [227; 228; 229; 230]. **Results. ** Optimal binary DL-reconciliations can be computed--independently of the costs--by the _LCA-mapping_, which maps each node of \(G\) to the LCA of the nodes that its children are mapped to [231]. Thus, this problem can be solved in linear time [232; 233] using \(O(1)\)-time LCA queries [234; 235]. The non-binary variant, while not quite as straightforward, can still be solved in polynomial time [236; 237]. The complexity of computing DTL-reconciliations depends heavily on their time-consistency. If we allow producing time-inconsistent reconciliations or the given species tree already comes with a dating function, then optimal DTL-reconciliations can be computed in polynomial time [238; 239; 240]. In general, however, the problem is NP-hard [238; 241], but can be solved in \(O(3^{k}|G|+|S|)\) time [238]. [PERSON] and [PERSON] [242] showed that DTL-reconciliations with at most \(\alpha\) speciations mapped to any one node in the species tree is FPT in \(\alpha+\tau\). Duplication, transfer, and loss are not the only evolutionary events shaping a gene tree. [PERSON] and [PERSON] [243; 244] recently introduced \"replacing transfers\" (T\({}_{\text{R}}\)) and \"gene conversion\" (C) which model important evolutionary events and showed that DLC-reconciliations can be decided in polynomial time [243] while deciding T\({}_{\text{R}}\)-reconciliations is NP-hard and FPT for \(k\)[244]. Finally, the concept of \"incomplete lineage sorting\" (ILS) is an important factor influencing discrepancies between gene and species phylogenies, especially when speciation occurs in rapid succession [245]. Roughly, ILS refers to the possibility that an earlier duplication or transfer does not pervade a population at the time a speciation occurs. Thus, one branch of a speciation may carry a gene lineage while the other does not (see Figure 11 for an illustration). In DL-reconciliation, this scenario requires a loss, but this would not reflect the true evolutionary history. Unfortunately, no particular mathematical model of ILS is widely accepted, so the following results might be incomparable. In 2017, [PERSON] et al. [246] showed that incorporating ILS into DL-reconciliation makes the problem NP-hard, even for dated species trees. Furthermore, DTL-reconciliation for dated, non-binary species trees allows ILS to be computed in \(O^{*}(4^{\Delta})\) time [247; 248]. [PERSON] and [PERSON] [249] started looking into the problem of reconciling rooted gene trees with a rooted species network, showing that, for the DL model, this problem is NP-hard, but solvable in \(O^{*}(2^{k})\) time. **Open Questions. ** There are three major challenges for bioinformatics concerning reconciliation. The first and more obvious task is to include all known genomic players in the reconciliation game, meaning to establish a standard model incorporating duplication, transfer, loss, replacing transfers, conversion,  
Figure 11: Illustration of incomplete lineage sorting (ILS). Each row of dots represents a generation and each dot stands for a number of individuals. The ancestral lineages of genes \(a\), \(b\) and \(c\), sampled in individuals of the respective extant species \(A\), \(B\), and \(\mathbb{C}\) are drawn in black. When the speciation splits \(A\) from \(\mathbb{C}\), all three alleles \(a\), \(b\), and \(c\) exist in the population, but are not “fixated”. This is necessary to observe ILS and gets more likely the shorter the branch to the ancestor species. The resulting gene phylogeny differs from the species phylogeny.