On the complexity of finding gapped motifs

DOI10.1016/J.JDA.2009.12.001zbMATH Open1201.68162DBLPjournals/jda/MichaelNU10OpenAlexW1999180344WikidataQ58054150 ScholiaQ58054150MaRDI QIDQ972352FDOQ972352

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

Recommendations

• Structural Analysis of Gapped Motifs of a String
• Maximal and minimal representations of gapped and non-gapped motifs of a string
• Motif matching using gapped patterns
• A FIRST APPROACH TO FINDING COMMON MOTIFS WITH GAPS
• Motif matching using gapped patterns

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)

Cites Work

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

Cited In (3)

• Maximal and minimal representations of gapped and non-gapped motifs of a string
• A FIRST APPROACH TO FINDING COMMON MOTIFS WITH GAPS
• Structural Analysis of Gapped Motifs of a String

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

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