Consensus Patterns parameterized by input string length is W[1]-hard
Laurent Bulteau


    ^2
    
======



We consider the Consensus Patterns problem, where, given a set of input strings, one is asked to extract a long-enough pattern which appears (with some errors) in all strings. Formally, the problem is defined as follows:

Consensus Patterns

Input: Strings S_1,… S_n of length at most ℓ, integers m and d.

Output: Length-m string S and integers (j_1,…, j_n) such that ∑_i=1^n Ham(S,  S_i[j_i..j_i+m-1]) ≤ d

Where Ham() denotes the Hamming distance and S[a..b] is the substring of S starting in a and ending in b. This problem is one of many variations of the well-studied Consensus String problem. It is similar to Consensus Substring in that the target string must be close to a substring of each input string (rather than the whole string). However, in the latter problem the distance to each input string is bounded, rather than the sum of the distances in our case. 

We look at this problem from the parameterized complexity viewpoint, more precisely for parameter ℓ. Recall that Consensus Substring is FPT for parameter ℓ <cit.>. See <cit.> for an overview of the variants of Consensus String, and <cit.> for recent advances on parameterized aspects of Consensus Substring and Consensus Patterns. We prove the following result.


Consensus Patterns(ℓ) is W[1]-hard.


By reduction from Multi-Colored Clique. We are given a graph G=(V,E), with a partition (coloring) V=V_1 ∪ V_2 ∪…∪ V_k, such that no edge has both endpoints of the same color. Assume that |V_h|=n for all h∈ [k]. Write V_h={v_h,1, v_h,2, … v_h,n}, i.e. each vertex has an index depending both on its color and its rank within its color. Let m=|E|. Multi-Colored Clique is W[1]-hard for parameter k <cit.>. See Figure <ref> for an example of the reduction.



We build an alphabet Σ containing V (i.e., one symbol per vertex) and two special characters  and .

Define string _i=  v_1,i v_2,i… v_k,i. Let e=(v_h,i,v_h',i') be the jth edge of E, j∈ [m]. 
Define _j as the string starting with , followed by k+1 characters: all , except for two positions: _j[k+h+1]=v_h,i and _j[h'+2]=v_h',i'.

Let N=m(k+2)+1. The instance  of Consensus Patterns contains N occurrences of strings _i, i∈ [n], and one occurrence of strings _j, j∈[m]. The target length is m=k+1.


Note that due to the large value of N, any solution S must have a minimal distance to the set of strings {_i| i∈ [n]}. Otherwise, (if it is, say, at the minimum distance plus one), the distance to the whole instance  increases by at least N, which cannot be compensated by the remaining strings _j (which have size m(k+2)<N). Hence we first enumerate the optimal solutions for the set {_i| i∈ [n]}.


The Consensus Patterns of {_i| i∈ [n]} (i.e., the strings of length k+1 at minimum  total distance from strings _i) are the strings of the form S= v_1, i_1… v_k, i_k with i_1,…, i_k∈ [n]. Such a string has a total distance of (n-1)k.


Since all strings in {_i| i∈ [n]} have length k+1, any consensus pattern S must be aligned with _i from the very first character. Hence S is a consensus string of {_i| i∈ [n]}. The consensus strings of this set are obtained by taking the majority character at each position. Thus, S[1]=#, and, for all h∈[k], there exists i_h such that S[h+1]={v_h,i_h}.


Consider now an optimal solution S for . Let {i_h| h∈[k]} be the set of indices as obtained from the lemma above. We show that the set of vertices K={v_h,i_h| h∈[k]} forms a clique of G iff the distance is below a certain threshold. To this end, we compute the best possible alignment between S and each string _j.


Let j∈ [m]. If both endpoints of edge e_j are in K then there exists an alignment of S at distance k-1 from _j, otherwise the best possible alignment has distance k.




Let h_,h_,i_,i_ be such that e_j=(v_h_,i_, v_h_,i_). 
There are two possible alignments of S with _j: S[1] is aligned either with _j[1] or with  _j[2]. We compute the distance in both cases.

If S[1] is aligned with _j[1], then there is exactly one common character, namely S[1]=_j[1]=. Indeed, for all h∈[k], S[h+1]∈ V_h and _j[h+1]∈ V_h-1∪{x}, hence these two characters are different. The distance in this case is k.

If S[1] is aligned with _j[2], then first note that S[1]=≠ x= _j[2]. 
Consider  index h_.  If i_=i_h_, then S[h_]=v_h_,i_h_=_j[h_+1], otherwise S[h_] ≠ =_j[h_+1]. 
Similarly for h_, S[h_]=_j[h_+1] iff i_=i_h_. For other values of h (i.e. h∈ [k]∖{h_, h_}), S[h]≠ = _j[h+1]. The distance is thus k-1 iff i_=i_h_ and i_=i_h_, it is at least k otherwise.

Overall, if i_=i_h_ and i_=i_h_ the optimal alignment has distance k-1, otherwise the optimal alignment has distance k. 



We can now conclude the proof. Let S be an optimal solution of Consensus Pattern for instance  and K its corresponding set of vertices. The distance from S to the N copies of strings _i is N(n-1)k. The distance between S and _j is k-1 if both endpoints of e_j are in K, and k otherwise. |E(K)| is the number of edges with both endpoints in K: the total distance from S to strings _j is thus mk - |E(K)|, and the total distance from S to  is N(n-1)k+mk-|E(K)|. Overall, the optimal distance is at most N(n-1)k+mk-k(k-1)/2 if, and only if, G contains a size-k set of vertices K with |E(K)|≥k(k-1)/2, i.e. if G contains a clique. 
plain

