Masking patterns in sequences: A new class of motif discovery with don't cares
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 Sigma. 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 (vertical bar Sigma vertical bar + 1)(L) candidate patterns in T, after a polynomial-time preprocessing of T. Our algorithm is also cache-friendly, attaining O(2(L) sort(n)) block transfers, where sort(n) is the cache complexity of sorting n items. (C) 2009 Elsevier B.V. All rights reserved.
motif inference pattern with don't care partial order set doubling algorithm