## 4 Pattern Filtering  
Here, we describe an application of pattern priority; the objective is to select the most important patterns in \(\mu(\mathcal{M})\) for each location of \(s\), according to our pattern priority rule. If a pattern, \(m\), is selected, we filter out all patterns with less priority that lay on the same locations of \(m\). If these locations are, for example, transcription factor binding sites or coding sequences of a genome, we will select only one pattern that best represents these locations. We say that an occurrence \(l\) of \(m\) is tied to an occurrence \(l^{\prime}\) of \(m^{\prime}\), if the two occurrences overlap, _i.e._, \(([l,l+|m|-1]\cap[l^{\prime},l^{\prime}+|m^{\prime}|-1])\
eq\emptyset\). Otherwise, we say that \(l\) is untied from \(l^{\prime}\). **Definition 9**: _(Underlying pattern) The set of patterns, \(\mathcal{U}\subseteq\mu(\mathcal{M})\), is said to be underlying if and only if:_  
1. _Every pattern,_ \(m\)_, in_ \(\mathcal{U}\)_, called an_ underlying pattern_, has at least_ \(q\) _occurrences that are untied from all the untied occurrences of other patterns in_ \(\mathcal{U}\setminus m\) _and_
2. _There does not exist a pattern,_ \(m\in\mu(\mathcal{M})\setminus\mathcal{U}\)_, such that_ \(m\) _has at least_ \(q\) _untied occurrences from all the untied occurrences of patterns in_ \(\mathcal{U}\)_._  
This subset of \(\mu(\mathcal{M})\) is composed only by those patterns that rank higher in our priority rule for some location of \(s\). The following algorithm filters any set of patterns, \(\mathcal{M}\), into the reduced set of underlying patterns, \(\mathcal{U}\). **Underlying Pattern Filtering (Input: \(\mathcal{M}\), \(q\); Output: \(\mathcal{U}\))**  
1. Compute the minimal set, \(\mu(\mathcal{M})\). 2. Rank all minimal patterns in \(\mu(\mathcal{M})\) using the pattern priority rule. 3. At each step, select the top pattern, \(m\), from \(\mu(\mathcal{M})\): * If all of its occurrences are tied/covered by some other patterns already in \(\mathcal{U}\), discard \(m\); * Otherwise, if \(m\) has at least \(q\) untied occurrences, add \(m\) to \(\mathcal{U}\) and update the locations of vector, \(\Gamma\), in which \(m\) appears. The correctness of the algorithm follows from Theorem 2. Let \(n\) be the size of the string, \(s\). During the first step, in the worst case, a pattern, \(m\), can have a location list, \(|\mathcal{L}_{m}|\), that is \(O(n)\), and the comparison of two ordered lists of occurrences costs \(O(n)\). Thus, this step of the algorithm costs \(O(n^{2}|\mathcal{M}|)\). The second phase orders the set of \(\mu(\mathcal{M})\), where each comparison between two patterns can take \(O(n)\) times; thus, this step costs \(O(n|\mu(\mathcal{M})|\log|\mu(\mathcal{M})|)\). In the third step, for each pattern, \(m\), that has been selected by our algorithm, we store the occurrences of \(m\) in a vector of Booleans \(\Gamma\), that represents the locations of \(s\). This means that, \(\forall\,l\in\mathcal{L}_{m}\), we store the value true in the locations \(\Gamma[l+i]\), for \(0\leq i<|m|\). This vector is then used to check if an occurrence is untied in constant time. Thus, for each pattern in \(\mu(\mathcal{M})\), checking for untied occurrences and updating the vector, \(\Gamma\), takes \(O(n)\) time. In total, step 3 requires \(O(n|\mu(\mathcal{M})|)\) time. In short, the total complexity of the algorithm is \(O(n^{2}|\mathcal{M}|)\). Note that this complexity does not depend on the notion of pattern priority used; thus, also, other binary relations can be applied with the same complexity. If the structure of the pattern priority is considered, it is possible to reduce the complexity using some results developed for patterns without character classes [19]. However, this is out of scope for this paper, since the Underlying Pattern Filtering is very fast in practice. Finally, we observe that the untied occurrences of all patterns, \(m\), in \(\mathcal{U}\) are non-overlapping.