Calcul par Contraintes de Motifs Ordonnés
Résumé
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.
La recherche de patrons ou d’itemsets fréquents a de nombreuses applications allant de la bioinfor- matique au marketing. Nous présentons le langage MMP (Maximal Matrix Problem) pour modéliser ces problèmes par une matrice de variables à domaines finis et un ensemble de contraintes matricielles. L’objectif est de déterminer une sous-matrice maximale cohérente, i.e., dont l’affectation des variables ans sa portée satisfait les contraintes et qui ne peut s’étendre en ligne en restant cohérente. Nous donnons une modélisation PPC du problème MMP et présentons différents types de contraintes matricielles. Nous étudions ensuite l’ordonnancement total ou partiel de patrons prélocalisés sur des séquences et permettant d’exclure des séquences prédéfinies. Nous présentons deux programmes par contraintes pour résoudre ces MMP ainsi qu’un algorithme génétique s’appuyant sur ces programmes pour passer l’échelle. Les résultats expérimentaux obtenus sur des jeux de séquences protéiques attestent de l’efficacité de l’approche.
Domaines
Informatique [cs]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...