# Parameterized Algorithms in Bioinformatics: An Overview
## 4 Haplotyping
### Haplotype Assembly
A simple reduction from Edge Bipartization[105] further shows that MEC is still NP-hard if each row contains at most three non-(-) characters and each column contains at most two non-(-) characters, thus excluding parameterized algorithms, even for the combined parameter. A parameterized algorithm with running time \(O^{*}(2^{m})\) is trivial (assign each row to one of the two partitions/chromosomes) and an \(O^{*}(2^{n})\)-time algorithm was presented by [PERSON] et al. [106]. Further research focused on the coverage \(c\), which is very small in practice. \(O^{*}(2^{c})\)-time algorithms with various polynomial factors were presented by [PERSON] et al. [107], [PERSON] et al. [108], [PERSON] et al. [109], [PERSON] et al. [110], and [PERSON] et al. [111]. MEC can be linearly reduced to Odd Cycle Transversal[105], implying that results for Odd Cycle Transversal carry over to MEC as well (\(O^{*}(3^{k})\) time [99, 100], \(O^{*}(2.32^{k})\) time [101], and \(O(k^{4.5})\)-size randomized kernel [102]). On gapless inputs, MEC can be solved in \(O(2^{\ell}mn)\) time [112] (assuming that all positions in the corrected matrix are \"heterozygous\", that is, contain both 0 and 1) or in \(O(3^{\ell}\ell m)\) time [105]. Notes.A variant of MFR in which rows are to be removed such as to make \(M\) 2-conflict-free _and_ to maximize the number of SNPs covered by the solution, called Longest Haplotype Reconstruction, has been shown to be NP-hard but solvable in \(O(n^{2}(n+m))\) time [104] for gapless \(M\). A more practical variant of MEC, incorporating the aspect of sequencing that each position in a read is given as four probabilities (probability for C, G, A, and T (or U)) instead of a single character was considered by [PERSON] et al. [107], who included a \"GenoSpectrum\" in the input and give an algorithm running in \(O(nc2^{c}+m\log m+m\ell)\) time. Another version of MEC, constraining output matrices by a \"guide-genotype\" was considered by [PERSON] et al. [113], showing that this version can be solved in \(O(4^{\ell}m)\) time. A slight modification of the MEC problem, asking for two haplotypes \(h_{1}\) and \(h_{2}\) and a bipartition \((R_{1},R_{2})\) of the rows such that \(h_{i}\) is at most \(k\) flips away from the reads in \(R_{i}\) for \(i\in\{1,2\}\), was considered by [PERSON] and [PERSON] [114]. Their algorithm solves this problem in \(O(2^{k}kmn)\) time. Since diploid species usually inherit one chromosome from each of their parents, it seems plausible that knowledge of the pedigree of a group of species helps infer their haplotypes. In this context, [PERSON] et al. [115] considered a set \(I\) of individuals and a set \(T\) of mother-father-child relations, given in addition to the fragment-matrices of each individual, and ask for a set of flips in each fragment-matrix such as to minimize the cost of the flips plus a cost function penalizing unlikely inheritance scenarios. They solved this modified problem in \(O^{*}(2^{4|T|+|I|+c})\) time. Finally, regarding polyploidy (that is, \(p>2\)), [PERSON] et al. [116] showed that \(p\)-ploid MFR can be solved in \(O(2^{2g}nm^{2}+2^{t}(2m)^{p+1})\) time and in \(O(nm^{2}+m^{p+1})\) time if the input matrix \(M\) is gapless. Further, \(p\)-ploid MEC can be solved in \(O^{*}(2^{p(\ell+1)})\) time and in \(O^{*}(p^{\varepsilon})\) time [105]. **Open Questions. ** Parameterizations for the IH problem focus mainly around the number \(g\) of gaps per row and the coverage \(c\). While the coverage \(c\) was reasonably estimated with 10-30 for past sequencing projects, future technology is expected to increase this number. Even today, whole-exome-sequencing uses coverages of at least 100 [117]. Quoting [PERSON] [118],  
\"developing a parameterized algorithm for this integrative framework and deciding parameters that work well in practice is very important.\"  
Thus, a future challenge will be to find more relevant parameters and exploit them to design parameterized algorithms.