## 1 Introduction
### Ranking and Clustering Degenerate Patterns  
In this paper, we are interested in patterns with character classes, also called _degenerate patterns_ (with no wildcards/gaps), which represent highly conserved parts in more complex signatures of protein families sharing remote homologies. The classification of their symbols often does not completely partition the entire alphabet of amino acids, and thus, in practical cases, patterns show classes with non-empty intersections. Let us consider, for example, the nickel-dependent hydrogenase large subunit signature \(RG[LIVMF]E..........[QESMP][RK]C[GR][LIVM]C\). The symbols of degenerate patterns contained in this signature allow for intersections between classes, like that of \([RK]\) with \([GR]\), and also subsets, like \([LIVM]\) with respect to \([LIVMF]\). In case the considered classes of characters form a partition of the original alphabet, \(\Sigma\), we can map the input sequences into the new alphabet of symbols represented by the partition, thus considerably reducing the number of candidate patterns to be analyzed to find the real signature. Unfortunately, if we consider the (already discovered) signature reported in PROSITE, most of the time, this is not true. In most cases, this will result in the combinatorial explosion of candidate patterns to be considered [12, 25], which consequently affects the efficiency of matching and discovering of new patterns. To cope with the combinatorial explosion of degenerate patterns, _de novo_ pattern discovery tools must first shrink the search space. In this regard, a number of different techniques have been proposed over the past two decades [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] on the basis of which other work rests [26, 27, 28, 29, 30, 31]. Despite that, the number of patterns in the output still remains intractable in most cases. Moreover, all pattern discovery tools must ultimately rank the output, according to some measure of importance. However, even if very sophisticated probabilistic scoring mechanisms are in place in a tool for protein analysis, such as Varun [12, 25], there are cases where the direct interpretation of results is far from trivial. Let us consider, for instance, the worst case of Varun presented in Table 1. The relevant signatures, shown in bold, appear at position \(42\), whereas almost all top signatures are somehow very similar. In order to filter this output and enhance its readability, there are two main issues. On the one hand, most signatures are very similar in the contained degenerate patterns, and therefore, they must be clustered together. On the other hand, if we are interested in a specific region of the sequences under examination, we would like to select the most important signature that appears in that region according to some rule. These two issues are, in practice, tightly related and need to be addressed as one. In this article, we focus our attention on degenerate patterns that are the fundamental units of representative signatures, e.g., _short linear motifs_ (SLiMs), in order to identify those representing the same loci, and thus, reducing the number of candidate solutions to be tested. In particular, we will follow and adapt the idea of pattern _minimality_ introduced in [32] for exact patterns to the case of degenerate patterns. This latter notion considers exact patterns representing particular equivalent classes, or sets of locations, with the smallest possible content. In the same way, we will identify the unique degenerate pattern characterizing a set of locations with the minimal degeneracy among the patterns given in the input. Recently, a number of ensemble methods addressing some of these clustering issues have been proposed [33, 34, 35, 36]. The general idea is that one can integrate the outcome of several pattern discovery algorithms based on sophisticated heuristics, in order to improve the ability of finding subtle biological signals in specific contexts.