Motif trie: an efficient text index for pattern discovery with don't cares

DOI10.1016/j.tcs.2017.04.012zbMath1386.68039OpenAlexW2612197248MaRDI QIDQ1698709

Nadia Pisanti, Roberto Trani, Giulia Menconi, Søren Vind, Roberto Grossi

Publication date: 16 February 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://orbit.dtu.dk/en/publications/202df529-d5c4-46f0-832c-a72743124808

zbMATH Keywords

data structurespattern discoverymotifsmaximal intervalstries and suffix trees

Mathematics Subject Classification ID

Data structures (68P05)

Uses Software

• Varun
• MADMX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \textsc{Rime}: repeat identification
• Maximal and minimal representations of gapped and non-gapped motifs of a string
• Suffix tree characterization of maximal motifs in biological sequences
• Replacing suffix trees with enhanced suffix arrays
• An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence
• Lossless filter for multiple repetitions with Hamming distance
• Irredundant tandem motifs
• Longest repeats with a block of \(k\) don't cares
• Fast Algorithms for Finding Nearest Common Ancestors
• Shared Information and Program Plagiarism Detection
• A Space-Economical Suffix Tree Construction Algorithm
• Mathematical Foundations of Computer Science 2003
• Bridging Lossy and Lossless Compression by Motif Pattern Discovery
• A FIRST APPROACH TO FINDING COMMON MOTIFS WITH GAPS