# Parameterized Algorithms in Bioinformatics: An Overview
## 4 Haplotyping
### Haplotype Inference  
**Problem Description. ** A _genotype_\(g\) is a string over the alphabet \(\{0,1,2\}\) and a _haplotype_ is a string over the alphabet \(\{0,1\}\). Two haplotypes \(h\) and \(h^{\prime}\)_resolve_ a genotype \(g\) if, for each position \(i\), \(g[i]=h[i]\) if \(h[i]=h^{\prime}[i]\) and \(g[i]=2\), otherwise. Then, a list of haplotypes _resolves_ a list of genotypes if, for each genotype on the list, there are two haplotypes on the list that resolve it. **Results. ** The literature considers two major variants of the HI problem. **Pure Parsimony. **: In the Pure Parsimony Haplotyping problem, the cost is the number \(k\) of _different_ haplotypes needed to explain the given genotypes. This problem is NP-hard [122; 123; 124; 125; 126], even for three letters 2 per genotype and three letters 2 per position in the genotypes, but becomes polynomial-time solvable if each genotype has at most two letters 2 [127; 104] or each position has at most one letter 2 [128; 126]. Further special cases were considered by [PERSON] et al. [125] who also  
Figure 8: Six genotypes \(g_{j}\) resolved by five haplotypes \(h_{i}\). presented an \(O(k^{k^{2}+k}m)\)-time algorithm for the general case [125]. A variant where haplotypes can only be picked from a prescribed pool \(H^{\prime}\) was considered by [PERSON] et al. [129] who showed a \(O(k^{O(k^{2})}n^{2}m)\)-time algorithm. [PERSON] et al. [130] later presented an \(O(k^{4k+3}m)\)-time algorithm for the unconstrained version that can also solve the constraint version in \(O(k^{4k+3}m|H^{\prime}|^{2})\) time (indeed, these running times can be decreased to \(O(k^{4k+2}m)\) and \(O(k^{4k+2}m|H^{\prime}|)\) on average using perfect hashing) as well as a size-\(O(2^{k}k^{2})\) kernel. Their algorithm can also output all optimal solutions. **Perfect Phylogeny. **: In the Haplotyping by Perfect Phylogeny problem, haplotypes are required to fit a \"perfect phylogeny\", that is, a tree whose leaves are labeled by the haplotypes resolving the input genotypes such that, for each position \(i\), the subtrees induced by the leaves with 0 and 1 at position \(i\) do not intersect. [PERSON] [131] introduced this problem for \(k=\infty\) and showed an almost-linear-time algorithm, which was later improved to linear time [132; 133]. Otherwise, the problem is NP-hard [126] but admits some polynomial-time solvable special cases based on the number of 2s in the genotypes [126]. **Notes. **: A variant of Pure Parsimony Haplotyping is XOR-Haplotyping, where genotypes do not contain the letter 2 and two haplotypes resolve a genotype if it is the result of the bitwise XOR of the haplotypes. While not known to be NP-hard, this variant can be solved in \(O(m(2^{k}k+n))\) time [120]. Note that the \(O^{*}(k^{4k})\)-time algorithm of [PERSON] et al. [130] can be adapted for this problem. Another problem called Shared Center that aims at identifying SNPs that correlate with certain diseases was considered from the viewpoint of parameterized complexity by [PERSON] et al. [134] who showed hardness and tractability for it. **Open Questions. **: A prominent open question is whether Pure Parsimony Haplotyping can be solved in polynomial time when the number of 2s per position is bounded by two [125; 135; 136]. For parameterized complexity, one of the most important questions is whether Pure Parsimony Haplotyping admits a single-exponential-time algorithm or a polynomial-size kernel when parameterized by \(k\). Further, parameterizations for this problem have mostly focused on the \"natural parameter\" \(k\) but, in practice, other parameters may be more relevant and promising. Some measure of how convoluted the given genotypes are may be a promising avenue for future research. From a biological point of view, a parameter related to the number of 2s may be promising, but the known results suggest that such a parameter can only lead to FPT-results if combined with others.