Calculation by constraints of ordered patterns

Itemset and pattern mining has numerous applications ranging from Marketing to Bioinformatics. We introduce a language, dubbed Maximal Matrix Problem (MMP), to model such problems. An instance of MMP is based on a matrix of finite domain variables and a set of matrix constraints. A solution is a maximal consistent submatrix whose assignment of the variables in its scope satisfies the constraints but cannot be extended over additional lines while preserving consistency. We propose a generic CP model for MMP and present various types of matrix contraints. We then tackle the problem of partially or totally ordering patterns that have been prelocalized over sequences in order to exclude predefined sequences. We present two CP models to solve these MMP together with a genetic algorithm. Experiments on datasets of protein sequences demonstrate the efficiency of the approach.