Ph.D Ieva Mitasiunaité

 

Mining string data under similarity and soft-frequency constraints: Application to promoter sequence analysis

 

Download Draft here

 

Date de soutenance : 04/05/2009

Lieu (établissement) : INSA de Lyon

 

Jury              

Pr. Michael R. Berthold (Examinateur, University of Konstanz, D)

Pr. Jean-François Boulicaut (Directeur de thèse, INSA Lyon)

Dr. Olivier Gandrillon (Examinateur, Université Lyon 1-CNRS, CGMC)

Pr. Ross D. King (Examinateur, University of Wales, UK)

Pr. Dominique Mouchiroud (Présidente, Université Lyon 1, LBBE)

Pr. Arno Siebes (Rapporteur, Universiteit Utrecht, Pays-Bas)

Dr. Maguelonne Teisseire  (Rapporteur, Cemagref, Montpellier)

 

Résumé. Nous étudions l'extraction de motifs sous contraintes dans des collections de chaînes de caractères et le développement de solveurs complets et génériques pour l'extraction de tous les motifs satisfaisant une combinaison de contraintes primitives. Un solveur comme FAVST permet d'optimiser des conjonctions de contraintes dites monotones et/ou anti-monotones (e.g., des contraintes de fréquence maximale et minimale). Nous avons voulu compléter ce type d’outil en taitant des contraintes pour la découverte de motifs tolérants aux exceptions. Nous proposons différentes définitions des occurrences approchées et l’exploitation de contraintes de fréquence approximative. Ceci nous conduit à spécifier des contraintes difficiles (e.g., pour l’expression de la similarité) comme des conjonctions de primitives monotones et anti-monotones optimisées par notre solveur MARGUERITE. Soucieux de sa mise en œuvre dans des processus de découverte de connaissances à partir de données, nous avons analysé le réglage des paramètres d'extraction (e.g., quel seuil choisir pour les fréquences). Nous proposons une méthode originale pour estimer le nombre de motifs qui satisfont une contrainte au moyen d’un échantillonnage de l'espace des motifs. Nous avons également étudié l'identification des paramètres les plus stringents pour fournir des motifs qui ne sont probablement pas de faux positifs. Ces contributions ont été appliquées à l'analyse des séquences promotrices des gènes. En étroite collaboration avec une équipe de biologistes du CGMC, nous avons pu identifier des sites de fixation putatifs de facteurs transcription impliqués dans le processus de différenciation cellulaire.

 

Abstract. We study constraint-based pattern mining from collections of strings and the design of complete and generic solvers (i.e., algorithms that compute every pattern which satisfies a combination of primitive constraints). A solver like FAVST enables to optimize the use of conjunctions of  primitive constraints which are either monotonic or anti-monotonic (e.g., minimal and maximal frequency constraints). We have extended this kind of tool by addressing fault-tolerant mechanisms. We propose different approaches for soft occurrences and the use of soft-frequency constraints. It leads to the design of, for instance, similarity constraints as conjunctions of monotonic and anti-monotonic primitives. Such constraints can be processed efficiently by our generic solver MARGUERITE. To support its use in knowledge discovery processes, we hae studied parameter tuning, e.g., for frequency thresholds. We propose an original method for guessing the size of the solution thanks to pattern space sampling. Moreover,  we also studied the parameter space to avoid the interpretation of some false positive patterns. This has been applied to gene promoter sequence analysis in collaboration with biologists from CGMC. We managed to identify putative transcription binding sites involved in the cellular differentiation process..

 

Publications liées à la thèse

 

I. Mitasiunaité, J-F. Boulicaut. Looking for monotonicity properties of a similarity constraint on sequences. Proceedings of 2006 ACM Symposium of Applied Computing SAC'2006, Special Track on Data Mining, April 23 - 27, 2006, Dijon, France. ACM Press, pp. 546-552.

I. Mitasiunaité, J-F. Boulicaut. About softness for inductive querying on sequence databases. Proceedings 7th International Baltic Conference on Databases and Information Systems DB&IS 2006,Vilnius (LT), July 3-6, 2006. pp. 77-82. IEEE Computer Press.

I. Mitasiunaité, J-F. Boulicaut. Introducing softness into inductive queries on string databases. Databases and Information Systems IV. Vol. 155 Frontiers in Artificial Intelligence and Applications. pp. 117-132. IOS, 2007.

J. Besson,  C. Rigotti, I. Mitasiunaite, J-F. Boulicaut. Parameter tuning for differential mining of string patterns. Proceedings 2nd International Workshop on Domain Driven Data Mining DDDM'08 co-located with IEEE ICDM'08, Pisa, Italy, December 15, 2008. pp. 77-86. IEEE Computer Society.

I. Mitasiunaite, C. Rigotti, S. Schicklin, L. Meyniel, J-F. Boulicaut, O. Gandrillon. Extracting Signature Motifs from Promoter Sets of Differentially Expressed Genes. In Silico Biology 8(0043), 2008.