# Parameterized Algorithms in Bioinformatics: An Overview
## 3 Genome Assembly and Sequence Analysis
### Identifying Common Patterns  
#### 3.2.1 Closest String (and variants)  
**Problem Description.** In Closest String, the goal is to find, given a set of strings, a center string that is close enough to all others (counting the number of mismatches, i.e. the Hamming distance, denoted by \(\mathsf{Ham}\)). This problem and many variants have been widely studied under the point of view of parameterized algorithms: we only highlight some prominent results, and refer the reader to the work of [PERSON] et al. [46] for a more exhaustive review.  
**Closest String (CS)**  
**Input:** strings \(s_{1},\ldots,s_{k}\), all of length \(\ell\), and some \(d_{r}\in\mathbb{N}\)  
**Question:** Is there a string \(s^{*}\) such that \(\forall_{i}\ \mathsf{Ham}(s^{*},s_{i})\leq d_{r}\)?  
**Results.** Closest String is NP-hard, even for binary alphabets [47]. On the other hand, it is FPT for _any_ of the following parameters: \(d_{r}\), \(k\), and \(\ell\)[48]. However, the algorithm for \(k\) makes use of an integer linear program with at most \(2^{k}\) variables, implying a mostly impractical combinatorial explosion. An easier (actually trivial) variant, denoted Consensus String, aims at minimizing the sum (or average) of the hamming distances to the center, rather than the worst-case distance.  
**Closest Substring.** A common generalization of CS called Closest SubString asks for a common pattern in all input strings, i.e. it allows trimming input strings until they reach a desired given length \(m\). In this case, the _consensus_ variant, optimizing the sum of distances, is no longer trivial and is denoted Consensus Pattern. Although these problems become much harder than Closest String and are W[1]-hard for any single parameter among \(\ell\), \(k\), \(d\), and \(m\), they still admit FPT algorithms for several combinations of these parameters [49; 50; 51; 52].  
**Closest String with Outliers.** Another noteworthy variant allows ignoring a small number \(t\) of _outliers_ from the input set of strings [53]. Interestingly, all parameterized algorithms for Closest String extend to this variant when \(t\) is considered as an additional parameter.  
Figure 5: A multiple sequence alignment for \(k=4\) strings with unit costs (shown below each column).  
**Radius or sum.**: A generalization for Closest String (that also applies to the variants above) considers both a constraint on the maximum hamming distance (the _radius_, \(d_{r}\)) and on the sum of hamming distances (denoted \(d_{s}\)). Indeed, the radius constraint only focuses on worst-case strings, and the sum constraint tends to overfit large sets of clustered strings, so taking both constraints can help reduce those problems. All algorithms mentioned for the radius-only version can be extended, in one way or another, to take both constraints into account without additional parameters [54].  
Another point of view consists in seeing the radius and sum measures as the \(L_{1}\) and \(L_{\infty}\) norms, respectively, of the vector \((d(s^{*},s_{1}),\ldots,d(s^{*},s_{k}))\). Thus, a possible compromise consists in optimizing the \(L_{p}\) norm of this vector for any rational \(p\), \(1<p<\infty\). [PERSON] et al. [55] studied Closest String under these norms on binary alphabets, proved its NP-hardness, and gave an FPT algorithm for parameter \(k\).