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)

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

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)