Abstract
We show that Closest Substring, one of the most important problems in the field of biological sequence analysis, is W[1]-hard with respect to the number k of input strings (even over a binary alphabet). This problem is therefore unlikely to be solvable in time O(f(k)n c) for any function fand constant c independent of k— effectively, the problem can 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 and both possess polynomial time approximation schemes. We also prove W[1]-hardness for other parameterizations in the case of unbounded alphabet size. Our main W[1]- hardness result generalizes to CONSENSUS PATTERNS, a problem of similar significance in computational biology.
Supported by the Deutsche Forschungsgemeinschaft (DFG), project OPAL (optimal solutions for hard problems in computational biology), NI 369/2-1.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Blanchette. Algorithms for phylogenetic footprinting. In Proc. of 5th ACM RECOMB, pages 49–58, 2001, ACM Press.
H. L. Bodlaender, R. G. Downey, M. R. Fellows, and H. T. Wareham. The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science, 147:31–54, 1995.
H. L. Bodlaender, R. G. Downey, M. R. Fellows, M. T. Hallett, and H. T. Wareham. Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences, 11: 49–57, 1995.
M. Cesati and L. Trevisan. On the efficiency of polynomial time approximation schemes. Information Processing Letters, 64(4):165–171, 1997.
R. G. Downey and M. R. Fellows. ParameterizedComplexity. Springer. 1999.
P. A. Evans and H. T. Wareham. Practical non-polynomial time algorithms for designing universal DNAoligon ucleotides: a systematic approach. Manuscript, April 2001.
M. Frances and A. Litman. On covering problems of codes. Theory of Computing Systems, 30:113–119, 1997.
J. Gramm, R. Niedermeier, and P. Rossmanith. Exact solutions for Closest String and related problems. To appear in Proc. of 12th ISAAC (Christchurch, New Zealand), LNCS, December 2001. Springer.
M. T. Hallett. An IntegratedComplexity Analysis of Problems from Computational Biology. PhD Thesis, University of Victoria, Canada, 1996.
J. K. Lanctot, M. Li, B. Ma, S. Wang, and L. Zhang. Distinguishing string selection problems. In Proc. of 10th ACM-SIAM SODA, pages 633–642, 1999, ACM Press. To appear in Information andComputation.
M. Li, B. Ma, and L. Wang. Finding similar regions in many strings. In Proc. of 31st ACM STOC, pages 473–482, 1999. ACM Press. To appear in Journal of Computer andSystem Sciences.
B. Ma. A polynomial time approximation scheme for the closest substring problem. In Proc. of 11th CPM, number 1848 in LNCS, pages 99–107, 2000. Springer.
P. A. Pevzner. Computational Molecular Biology — An Algorithmic Approach. MITPress. 2000.
P. A. Pevzner and S.-H. Sze. Combinatorial approaches to finding subtle signals in DNA sequences. In Proc. of 8th ISMB, pages 269–278, 2000. AAAI Press.
M.-F. Sagot. Spelling approximate repeated or common motifs using a sufix tree. In Proc. of 3rdLA TIN, number 1380 in LNCS, pages 111–127, 1998. Springer.
D. Sanko. and J. Kruskal (eds.). Time Warps, String Edits, and Macromolecules. Addison-Wesley. 1983. Reprinted in 1999 by CSLI Publications.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fellows, M.R., Gramm, J., Niedermeier, R. (2002). On the Parameterized Intractability of Closest Substring and Related Problems. In: Alt, H., Ferreira, A. (eds) STACS 2002. STACS 2002. Lecture Notes in Computer Science, vol 2285. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45841-7_21
Download citation
DOI: https://doi.org/10.1007/3-540-45841-7_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43283-8
Online ISBN: 978-3-540-45841-8
eBook Packages: Springer Book Archive