We introduce a new notion of motifs, called masks, that succinctly represents the repeated patterns for an input sequence T of n symbols drawn from an alphabet Σ. We show how to build the set of all frequent maximal masks of length L in O (2 L n) time and space in the worst case, using the Karp-Miller-Rosenberg approach. We analytically show that our algorithm performs better than the method based on constant-time enumerating and checking all the potential (| Σ | + 1) L candidate patterns in T, after a polynomial-time preprocessing of T. Our algorithm is also cache-friendly, attaining O (2 L s o r t (n)) block transfers, where s o r t (n) is the cache complexity of sorting n items.
|Autori:||G.BATTAGLIA; R.GROSSI; D.CANGELOSI; PISANTI N|
|Titolo:||Masking Patterns in Sequences: A New Class of Motif Discovery with Don't Cares|
|Anno del prodotto:||2009|
|Digital Object Identifier (DOI):||10.1016/j.tcs.2009.07.014|
|Appare nelle tipologie:||1.1 Articolo in rivista|