On the complexity of finding gapped motifs

DOI10.1016/J.JDA.2009.12.001MaRDI QIDQ972352zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Morris Michael, François Nicolas, Esko Ukkonen

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)

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

Cites work

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

Cited in

(6)

• Structural Analysis of Gapped Motifs of a String
• Motif matching using gapped patterns
• Maximal and minimal representations of gapped and non-gapped motifs of a string
• Motif matching using gapped patterns
• On multiple longest common subsequence and common motifs with gaps (extended abstract)
• A FIRST APPROACH TO FINDING COMMON MOTIFS WITH GAPS

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)