On the complexity of finding common approximate substrings.

DOI10.1016/S0304-3975(03)00320-7MaRDI QIDQ1426464zbMATH OpenOpenAlexWikidataFDO

Authors Patricia A. Evans, Andrew D. Smith, H. Todd Wareham

Publication date 14 March 2004

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(03)00320-7

zbMATH Keywords

Parameterized complexityPattern matchingCommon approximate substring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Recommendations

• On the parameterized intractability of motif search problems
• scientific article; zbMATH DE number 1615273
• Closest Substring Problems with Small Distances
• Complexity of approximating closest substring problems.
• Hard problems in similarity searching

Cites work

• scientific article; zbMATH DE number 1615273 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305456 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2081011 (Why is no real title available?)
• scientific article; zbMATH DE number 2086391 (Why is no real title available?)
• Finding similar regions in many strings
• On covering problems of codes
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Pattern recognition in several sequences: Consensus and alignment
• The Complexity of Some Problems on Subsequences and Supersequences
• The parameterized complexity of sequence alignment and consensus

Cited in

(9)

• Hard problems in similarity searching
• Slightly superexponential parameterized problems
• Complexity of substring search in a set of strings
• Finding consensus strings with small length difference between input and solution strings
• Consensus strings with small maximum distance and small distance sum
• Fundamentals of Computation Theory
• Consensus strings with small maximum distance and small distance sum
• An improved voting algorithm for planted \((l, d)\) motif search
• On the common substring alignment problem

This page was built for publication: On the complexity of finding common approximate substrings.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1426464)