On the parameterized intractability of motif search problems

DOI10.1007/S00493-006-0011-4MaRDI QIDQ858110zbMATH OpenOpenAlexWikidataFDO

Authors Michael R. Fellows, Jens Gramm, Rolf Niedermeier

Publication date 8 January 2007

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0205056

zbMATH Keywords

Closest Substringcomputational biologycomputational complexityconsensus analysisConsensus Patternshardnessparameterized complexityparameterized intractability

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Mathematical biology in general (92B99)

Abstract: We show that Closest Substring, one of the most important problems in the field of biological sequence analysis, is W[1]-hard when parameterized by the number k of input strings (and remains so, even over a binary alphabet). This problem is therefore unlikely to be solvable in time O(f(k)cdot n^{c}) for any function f of k and constant c independent of k. The problem can therefore be expected to be intractable, in any practical sense, for k>=3. Our result supports the intuition that Closest Substring is computationally much harder than the special case of Closest String, although both problems are NP-complete. We also prove W[1]-hardness for other parameterizations in the case of unbounded alphabet size. Our W[1]-hardness result for Closest Substring generalizes to Consensus Patterns, a problem of similar significance in computational biology.

Review text

Searching common motifs is a central problem of consensus analysis based on strings with, in particular, applications in computational biology. The Closest Substring problem and the Consensus Patterns problem play an important role in this context. Let \(d_H(s,s')\) denote the Hamming distance between strings \(s\) and \(s'\). Then these two decision problems are defined as follows: Closest Substring: Input. \(k\) strings \(s_1, s_2, \dots, s_k\) over alphabet \(\Sigma\) and non-negative integers \(d\) and \(L\). Question. Is there a string \(s\) of length \(L\) and, for all \(i = 1, \dots, k\), a length-\(L\) substring \(s'_i\) of \(s_i\) such that \(d_H(s,s'_i) \leq d\)? Consensus Patterns: Input. \(k\) strings \(s_1, s_2, \dots, s_k\) over alphabet \(\Sigma\) and non-negative integers \(d\) and \(L\). Question. Is there a string \(s\) of length \(L\) and, for all \(i = 1, \dots, k\), a length-\(L\) substring \(s'_i\) of \(s_i\) such that \(\sum_{i=1}^k d_H(s,s'_i) \leq d\)? In this paper the parameterized complexity of the above two problems is analysed. The main results are the following: A new W[1]-hardness proof both of the Closest Substring and the Consensus Patterns problem are given for various parameters (in particular, \((L,d,k)\)) in case of an unbounded alphabet. It is shown that the W[1]-hardness carries over to the case of a binary alphabet for the parameter \(k\). At the heart of the paper is a sophisticated parameterized \(m\)-reduction from the W[1]-hard Clique problem to the Closest Substring problem with respect to the aggregate parameter \((L,d,k)\) in case of an unbounded alphabet size. It is then shown how this reduction can be modified so as to apply to the parameter \(k\) in case of a binary alphabet. Moreover, also the required modifications in order to extend these W[1]-hardness results to the Consensus Patterns problem are shown. Despite the technical difficulty, this paper maintains a high level of readability. In particular, two detailed examples for the Closest Substring problem (one in case of an unbounded alphabet and one in case of a binary alphabet) greatly help the reader. An overview of already known complexity results in this context, of the results proven in this paper, and of open problems, provides the reader with a full picture of this area. In summary, the paper is a pleasant read. It is interesting both to the parameterized complexity expert (who will appreciate the clear presentation of a sophisticated parameterized problem reduction) and to the novice in this field (who will get an idea of the aesthetics of parameterized complexity analyses). The only criticism with this paper is the lack of motivation for dealing with these problems. A reader who is new to the field of computational biology will enjoy the problem reductions but he/she will not understand what these problems are good for.

Recommendations

• scientific article; zbMATH DE number 2086391
• Closest Substring Problems with Small Distances
• Hard problems in similarity searching
• Finding consensus strings with small length difference between input and solution strings
• Fixed-parameter algorithms for CLOSEST STRING and related problems

Cited in

(24)

• The parameterized complexity of sequence alignment and consensus
• On the complexity of finding common approximate substrings.
• On the kernelization complexity of string problems
• Hard problems in similarity searching
• Consensus strings with small maximum distance and small distance sum
• Parameterized intractability of distinguishing substring selection
• Randomized fixed-parameter algorithms for the closest string problem
• The parameterized complexity of the shared center problem
• Finding consensus strings with small length difference between input and solution strings
• On the Kernelization Complexity of Colorful Motifs
• Closest Substring Problems with Small Distances
• Consensus patterns (probably) has no EPTAS
• On approximating string selection problems with outliers
• A three-string approach to the closest string problem
• scientific article; zbMATH DE number 2086391 (Why is no real title available?)
• Parameterized complexity analysis for the closest string with wildcards problem
• Multivariate algorithmics for NP-hard string problems
• Finding consensus strings with small length difference between input and solution strings
• Consensus strings with small maximum distance and small distance sum
• Separating sets of strings by finding matching patterns is almost always hard
• Tight hardness results for consensus problems on circular strings and time series
• The parameterized complexity of the shared center problem
• Efficient Algorithms for the Closest String and Distinguishing String Selection Problems
• An improved lower bound on approximation algorithms for the closest substring problem

This page was built for publication: On the parameterized intractability of motif search problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q858110)