On the parameterized intractability of motif search problems

DOI10.1007/s00493-006-0011-4zbMath1109.68049arXivcs/0205056WikidataQ57359988 ScholiaQ57359988MaRDI QIDQ858110

Rolf Niedermeier, Michael R. Fellows, Jens Gramm

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 complexity; computational biology; hardness; parameterized complexity; consensus analysis; Closest Substring; Consensus Patterns; parameterized intractability

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D15: Complexity of computation (including implicit computational complexity)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

92B99: Mathematical biology in general

Related Items

Unnamed Item, Tight Hardness Results for Consensus Problems on Circular Strings and Time Series, Efficient Algorithms for the Closest String and Distinguishing String Selection Problems, Randomized fixed-parameter algorithms for the closest string problem, On approximating string selection problems with outliers, A three-string approach to the closest string problem, Parameterized complexity analysis for the closest string with wildcards problem, An improved lower bound on approximation algorithms for the closest substring problem, On the kernelization complexity of string problems, Consensus strings with small maximum distance and small distance sum, Finding Consensus Strings with Small Length Difference Between Input and Solution Strings, Consensus Patterns (Probably) Has no EPTAS