On the parameterized intractability of motif search problems

DOI10.1007/s00493-006-0011-4zbMath1109.68049arXivcs/0205056OpenAlexW2044802269WikidataQ57359988 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 complexitycomputational biologyhardnessparameterized complexityconsensus analysisClosest SubstringConsensus Patternsparameterized intractability

Mathematics Subject Classification ID

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

Related Items (12)

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

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