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

computational complexitycomputational biologyhardnessparameterized complexityconsensus analysisClosest SubstringConsensus Patternsparameterized intractability

Mathematics Subject Classification ID

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

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.

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

(23)

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

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)