On the parameterized intractability of motif search problems

DOI10.1007/S00493-006-0011-4zbMATH Open1109.68049arXivcs/0205056OpenAlexW2044802269WikidataQ57359988 ScholiaQ57359988MaRDI QIDQ858110FDOQ858110

Authors: Michael R. Fellows, Jens Gramm, Rolf Niedermeier 

Publication date: 8 January 2007

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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

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)

Cited In (23)

• On approximating string selection problems with outliers
• Consensus patterns (probably) has no EPTAS
• On the Kernelization Complexity of Colorful Motifs
• Randomized fixed-parameter algorithms for the closest string problem
• An improved lower bound on approximation algorithms for the closest substring problem
• Efficient Algorithms for the Closest String and Distinguishing String Selection Problems
• A three-string approach to the closest string problem
• 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
• Closest Substring Problems with Small Distances
• Parameterized complexity analysis for the closest string with wildcards problem
• Title not available (Why is that?)
• 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)