On the complexity of finding common approximate substrings.

DOI10.1016/S0304-3975(03)00320-7zbMath1060.68048OpenAlexW2062088872WikidataQ106509296 ScholiaQ106509296MaRDI QIDQ1426464

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

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)

Related Items (6)

Hard problems in similarity searching ⋮ Finding Consensus Strings with Small Length Difference Between Input and Solution Strings ⋮ Unnamed Item ⋮ An improved voting algorithm for planted \((l, d)\) motif search ⋮ Slightly Superexponential Parameterized Problems ⋮ Consensus strings with small maximum distance and small distance sum

Cites Work

• On covering problems of codes
• Pattern recognition in several sequences: Consensus and alignment
• The parameterized complexity of sequence alignment and consensus
• Finding similar regions in many strings
• The Complexity of Some Problems on Subsequences and Supersequences
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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