# Parameterized Algorithms in Bioinformatics: An Overview
## 3 Genome Assembly and Sequence Analysis
### Scaffolding  
**Problem Description. **: As mentioned previously, overlapping reads usually does not lead to a fully reconstructed (that is, one sequence per chromosome) genome. Instead, assembly algorithms usually produce fairly long and correct substrings called _contigs_ that cannot be extended by overlapping reads. However, current sequencing techniques (\"Next-Generation Sequencing\" (NGS)) yield additional information about reads. Indeed, NGS-produced reads come in pairs (\"mate pairs\") and a rough estimate about the number of base-pairs between the two reads of a pair is known. Thus, it is possible that a read \(r\) of a pair \((r,r^{\prime})\) aligns well with parts of some contig \(c\) while \(r^{\prime}\) aligns well with parts of contig \(c^{\prime}\). This presents evidence that, in the target genome, contig \(c\) is followed by contig \(c^{\prime}\) and gives us an approximation of the distance between them (see [PERSON] et al. [72] for more details). Torepresent this information, we can construct a _scaffold graph_ by representing contigs as pairs of vertices connected by a perfect matching, and connecting contig extremities \(u\) and \(v\) with an edge weighted by the number of mate-pairs indicating that \(u\) is followed by \(v\) in the chromosome. In this graph, we are looking for a cover of all matching edges using a small number of paths and cycles (corresponding to linear and circular chromosomes in the genome). Scaffolding (SCA)  
**Input**: graph \(G\) with edge-weights \(\omega\), perfect matching \(\mathcal{M}\) in \(G\), some \(\sigma_{p},\sigma_{c},k\in\mathbb{N}\)  
**Question:** Is there a collection \(\mathcal{C}\) of \(\leq\sigma_{p}\) paths and \(\leq\sigma_{c}\) cycles covering \(\mathcal{M}\) in \(G\) of total weight \(\geq k\)? [PERSON] et al. [73] considered \(G\) as multigraph in which each non-contig edge has an approximate length. This makes for more realistic modeling since two hypotheses involving different gap-sizes between contigs should be incompatible. The authors showed NP-completeness for this problem. To better support repetitions, ([PERSON] et al. [74] unpublished) added multiplicities to the contig edges, which can be roughly estimated from coverage numbers. Then, a solution is a set of \(\leq\sigma_{p}\) open and \(\leq\sigma_{c}\) closed walks in \(G\). They presented an ILP solving a slight generalization of this problem, but no parameterized algorithms are known in this case. However, the multiplicity-supporting version of Scaffolding gives rise to another problem: optimal solutions are much less likely to be unique and each individual optimal solution is thus likely to correspond to chimeric sequences (a genomic sequence is called _chimeric_ if it contains material from different chromosomes or from unrelated parts of one chromosome). This gives rise to the problem of removing inter-contig edges such as to extract the sub-walks that are shared by all decompositions of a solution into walks [75]. Scaffold Linearization (LIN)  
**Input**: graph \(G\) with edge-weights \(\omega\) and multiplicities \(m\), perfect matching \(\mathcal{M}\) in \(G\), \(k\in\mathbb{N}\)  
**Question:** Is there a set \(X\subseteq E(G)\setminus\mathcal{M}\) of total cost \(\leq k\) s.t. \(G-E\) can be uniquely decomposed into walks? **Results. ** [PERSON] et al. [76] presented an \(O(|V(G)|^{w}|E(G)|)\)-time algorithm for SCA where \(w\) is the maximum number of contigs spanned by any inter-contig edge in the solution ordering. SCA is known to be W[1]-hard for \(k\)[75] but solvable in \(O^{*}((twt)^{2})\) time [77], where \(tw\) denotes the treewidth of \(G\). A simple reduction from Hamiltonian Path proves SCA NP-hard even on bipartite planar graphs with constant edge weights and \(\sigma_{p}+\sigma_{c}=1\)[75]. For a variation of this problem, they proved a kernel for a parameter involving the feedback edge set number of \(G\).