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

Publication: Research - peer-reviewJournal article – Annual report year: 2018


View graph of relations

We introduce the motif trie data structure, which has applications in pattern matching and discovery in genomic analysis, plagiarism detection, data mining, intrusion detection, spam fighting and time series analysis, to name a few. Here the extraction of recurring patterns in sequential and textual data is one of the main computational bottlenecks. For this, we address the problem of extracting maximal patterns with at most k don't care symbols and at least q occurrences, according to a maximality notion we define. We apply the motif trie to this problem, also showing how to build it efficiently. As a result, we give the first algorithm that attains a stronger notion of output-sensitivity, where the cost for an input sequence of n symbols is proportional to the actual number of occurrences of each pattern, which is at most n (much smaller in practice). This avoids the best-known cost of O(nc) per pattern, for constant c>1, which is otherwise impractical for massive sequences with large n.
Original languageEnglish
JournalTheoretical Computer Science
Pages (from-to)74-87
StatePublished - 2017
CitationsWeb of Science® Times Cited: 0


  • Theoretical Computer Science, Computer Science (all), Data structures, Maximal intervals, Motifs, Pattern discovery, Tries and suffix trees, Intrusion detection, Pattern matching, Time series analysis, Trees (mathematics), Computational bottlenecks, Genomic analysis, Plagiarism detection, Suffix-trees, Trie data structures, Data mining
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

ID: 134178695