## 2 Preliminary Definitions  
A _string_ is a sequence of symbols from an alphabet, \(\Sigma\). The set of all strings over \(\Sigma\) is denoted by \(\Sigma^{*}\). The length of a string, \(s\), is denoted by \(|s|\) and the \(i\)-th symbol of \(s\) is \(s_{i}\), where \(1\leq i\leq|s|\). Let, now, \(s=s_{1}s_{2}\ldots s_{n}\) be a string of length \(|s|=n\) on \(\Sigma\). This is the reference sequence and, in practice, will be the concatenation of several sequences. For ease of explanation, here, we consider only one sequence, and in Section 5, we will clarify how to deal with multiple sequences. A symbol from \(\Sigma\), say \(\sigma\), is called a _solid character_. A character class, \(C\), is a subset of \(\Sigma\) of cardinality of at least two. Let us assume that we have several character classes, \(C_{j}\). For the rest of the paper, we assume that we are given a string, \(s\), on \(\Sigma\) of length, \(n\), and a positive integer, \(q\), \(2\leq q\leq|s|\), called _quorum_.  
**Definition 1**: _(Sequence) A sequence with character classes, or simply a sequence, is a string of consecutive symbols defined on \(\{2^{C_{j}}\}\)._  
In the literature, a sequence with character classes is also called a _degenerate pattern_ or an _indeterminate string_[4, 5, 6, 7, 8, 9]. Let \(p\) be a sequence with character classes; then, we write its symbols by means of square brackets. For example, if \(p=p_{1}p_{2}\ldots p_{k}\), where \(|p|=k\), and each symbol, \(p_{j}\), with \(1\leq j\leq k\), is either a solid character or a character class, \(C\), and is written as \(p_{j}=[\sigma_{1},\sigma_{2},\ldots,\sigma_{r_{j}}]\). As of Table 2, \(s=aabeadbace\), \(\Sigma=\{a,b,c,d,e\}\), \(q=3\), and the two classes are \(C_{1}=\{a,c,d\}\) and \(C_{2}=\{a,b,e\}\), then \(p=a[a,c,d][b,e]\) is a sequence with character classes of length \(k=3\).  
The main issue with this example is that the character classes might not be a partition of \(\Sigma\). This is very common for PROSITE functional patterns, e.g., _[LIVMA][LIVMY].G[GSTA][DES]L[FI][TN][GS]_.  
**Definition 2**: _(Sequence occurrence) A sequence, \(p=p_{1}p_{2}\ldots p_{k}\), of length, \(k\), is said to occur at a location, \(l\), of a string, \(s\), with \(1\leq l\leq n\), if \(s_{l+j-1}\in p_{j}\) for each \(1\leq j\leq k\)._  
A pattern, \(m\), is then defined as a pair, \((p,\mathcal{L}_{m})\), where \(p\) is a sequence that occurs at the locations given by \(\mathcal{L}_{m}\) and \(\mathcal{L}_{m}\) is a set of at least \(q\) locations of \(s\). For instance, in Table 2, \(m=(p,\mathcal{L}_{m})\) is a pattern with sequence \(p=a[a,c,d][b,e]\) of length \(k=3\) and location list \(\mathcal{L}_{m}=\{1,5,8\}\). More formally:  
**Definition 3**: _(Pattern, location list) We say that \(m=(p,\mathcal{L}_{m})\) is a pattern with sequence, \(p=p_{1}p_{2}\ldots p_{k}\), and location list, \(\mathcal{L}_{m}=(l_{1},l_{2},\ldots,l_{\
u})\), if and only if all of the following hold: (i) \(p\) has at least two symbols, \(|p|\geq 2\); (ii) The location list has at least \(q\) occurrences, \(|\mathcal{L}_{m}|\geq q\); and (iii) There does not exist a location, \(l^{\prime}\
otin\mathcal{L}_{m}\), such that \(p\) occurs at \(l^{\prime}\) in \(s\) (that is, \(\mathcal{L}_{m}\) is complete)._