An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence

DOI10.1007/S10878-006-9029-1MaRDI QIDQ996827zbMATH OpenOpenAlexWikidataFDO

Authors Hiroki Arimura, Takeaki Uno

Publication date 19 July 2007

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-006-9029-1

zbMATH Keywords

Data miningAlgorithmDelayEnumerationPattern discoveryPolynomial timeClosed itemsetClosed patternMaximal motifMotifSequence mining

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05)

Recommendations

• Algorithms and Computation
• Toward optimal motif enumeration.
• Efficient construction of maximal and minimal representations of motifs of a string
• Discovering Almost Any Hidden Motif from Multiple Sequences in Polynomial Time with Low Sample Complexity and High Success Probability
• Space and Time Efficient Algorithms for Planted Motif Search
• An algorithmic framework for motif discovery problems in weighted sequences
• An approximation algorithm for alignment of multiple sequences using motif discovery
• scientific article; zbMATH DE number 1945161
• Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications

Cites work

• scientific article; zbMATH DE number 1696848 (Why is no real title available?)
• scientific article; zbMATH DE number 1786452 (Why is no real title available?)
• scientific article; zbMATH DE number 2086380 (Why is no real title available?)
• scientific article; zbMATH DE number 1414302 (Why is no real title available?)
• scientific article; zbMATH DE number 1445317 (Why is no real title available?)
• Algorithms on Strings, Trees and Sequences
• Discovery Science
• Extracting Approximate Patterns
• Inductive Logic Programming
• Jewels of Stringology
• Mathematical Foundations of Computer Science 2003
• Polynomial space polynomial delay algorithms for listing families of graphs
• The complexity of computing the permanent

Cited in

(11)

• Toward optimal motif enumeration.
• Efficient algorithms for discovering frequent and maximal substructures from large semistructured data
• Suffix tree characterization of maximal motifs in biological sequences
• On the complexity of finding gapped motifs
• Reverse-safe text indexing
• Efficient construction of maximal and minimal representations of motifs of a string
• Motif trie: an efficient text index for pattern discovery with don't cares
• Maximal motif discovery in a sliding window
• Mining top-\(k\) motifs with a SAT-based framework
• Algorithms and Computation
• Pattern masking for dictionary matching: theory and practice

Describes a project that uses

Uses Software

• CloseGraph
• gSpan

This page was built for publication: An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence

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