On the complexity of finding gapped motifs

DOI10.1016/j.jda.2009.12.001zbMath1201.68162OpenAlexW1999180344WikidataQ58054150 ScholiaQ58054150MaRDI QIDQ972352

Esko Ukkonen, François Nicolas, Morris Michael

Publication date: 25 May 2010

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2009.12.001

zbMATH Keywords

NP-completemotif discoverygapped patternstring matching with don't care symbolstandem motifs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Related Items (1)

Maximal and minimal representations of gapped and non-gapped motifs of a string

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hardness of optimal spaced seed design
• An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence
• Finding approximate repetitions under Hamming distance.
• Distinguishing string selection problems.
• Finding similar regions in many sequences
• Longest repeats with a block of \(k\) don't cares
• Extracting approximate patterns
• Algorithms on Strings, Trees and Sequences

This page was built for publication: On the complexity of finding gapped motifs