# Parameterized Algorithms in Bioinformatics: An Overview
## 4 Haplotyping
### Haplotype Assembly  
**Problem Description. ** A matrix \(M\) with \(m\) length-\(n\) rows (\"fragments\") over \(\{0,1,-\}\) is called _in conflict_ if there are rows \(r\) and \(r^{\prime}\) and a position \(i<n\) such that \(r[i]\), \(r^{\prime}[i]\) and - are pairwise distinct (that is, \(-\
eq r[i]\
eq r^{\prime}[i]\
eq-\)) and _conflict-free_ (or _1-conflict-free_), otherwise. For all \(p\geq 1\), \(M\) is called \(p\)_-conflict-free_ if its rows can be partitioned into \(p\) conflict-free sets of rows. While we prefer stating the general (\"polyloid\") version of this problem, the special case that \(p=2\) (\"diploid\" genome) is by far the most commonly considered. \(p\)-(Single) Individual Haplotyping (also referred to as Haplotype Assembly) (\(p\)-IH) **Input:** matrix \(M\), integer \(k\)  
**Question:** can \(M\) be turned \(p\)-conflict-free with \(k\) operations? \(p\)-IH can be interpreted as a clustering problem that finds \(p\) consensus strings such as to minimize the sum of the radii needed to capture all input strings (rows), where the distance function depends on the nature of allowed \"operations\". Most of the results are for diploid genomes, that is, for the 2-IH problem. In the following, a row \(r\) is called _active_ in position \(j\) if there are \(i\) and \(\ell\) such that \(i\leq j<\ell\) and \(r[i]\
eq-\
eq r[\ell]\), the set of positions in which \(r\) is active is called \(\alpha(r)\) and a _gap_ in a row \(r\) is any position \(i\in\alpha(r)\) with \(r[i]=-\). We let \(g\) denote the maximum number of gaps in any row of \(M\), we let \(\ell:=\max_{r}|\alpha(r)|\) denote the maximum number of active positions of any row, and we let  
Figure 7: A matrix of reads from two chromosomes, condensed to known SNPs of the species. Flipping the underlined (red) entries allows a bipartition into two conflict-free sets (gray and black). Note that not all SNPs exhibit both possible states. \(c:=\max_{j}\alpha^{-1}(j)\) denote the \"coverage\", that is, the maximum over all positions \(j\) of the number of rows \(r\) that are active in \(j\). Note that gapless rows can still contain chains of -at the beginning and end. **Results. ** The complexity of 2-IH depends on the type of operations allowed on the matrix. Mainly, three operations have been considered in the literature:  
Deleting rows.The problem of turning \(M\) 2-conflict-free by row-deletions is known as Minimum Fragment Removal (MFR). It is equivalent to turning the \"conflict graph\" bipartite by removing vertices (this problem is called Odd Cycle Transversal or Vertex Bipartization in the literature). Herein, the vertices of the conflict graph are the rows of \(M\) and rows \(u\) and \(v\) have an edge if they cannot be assigned to the same chromosome, that is, - \(\
eq u[i]\
eq v[i]\
eq\) - for some position \(i\). MFR is NP-hard even if each row has at most one gap [96], but becomes polynomial-time solvable for gapless \(M\)[96, 97]. It can be solved in \(O(2^{28}m^{2}n+2^{38}m^{3})\) time [97] and in \(O(nc3^{c}+m\log m+m\ell)\) time [98]. Of course, results for Odd Cycle Transversal apply to MFR: it admits \(O^{*}(3^{k})\)-time [99, 100] and \(O(2.32^{k})\)-time [101] algorithms as well as a randomized kernel of size \(O(k^{4.5})\)[102]. **Deleting columns. ** The problem of turning \(M\) 2-conflict-free by column-deletions is known as Minimum SNP Removal (MSR). It has been shown to be NP-hard even if each row has at most two gaps [96], but polynomial-time solvable for gapless \(M\)[96, 103]. [PERSON] et al. [97] showed an \(O(2^{5}mn^{2})\)-time algorithm. **Flipping values. **: By far the most studied approach is turning \(M\) 2-conflict-free by flipping values, that is, turning a 1 into a 0 or vice versa. This problem is known as Minimum Error Correction (MEC) or Minimum Letter Flip in the literature and it is has been shown to be NP-hard, even on gapless inputs [104].