Le cadre des bases de données inductives (IDB) permet de décrire et d'exécuter des scénarios d'extraction de connaissances dans des données (ECD) à partir de séquences de requêtes. En particulier, les requêtes inductives spécifient de façon déclarative les contraintes que les motifs à extraire doivent satisfaire. Un premier défi consiste à identifier les contraintes primitives qui sont effectivement utiles pour exprimer l’intérêt subjectif et donc les attentes des analystes. Un second défi concerne le développement d'algorithmes efficaces capables d’exploiter ces contraintes et leurs propriétés, une difficulté majeure quand l’on veut obtenir des extracteurs complets : tous les motifs qui satisfont une combinaison de contraintes donnée par l'utilisateur doivent alors être extraits. Dans le cadre de cette thèse, nous nous intéressons à l'extraction de motifs sous contraintes dans des collections de séquences (chaînes de caractères) et au développement de solveurs complets et génériques c’est-à-dire non spécialisés pour un type de combinaison de contraintes particulier. Nous voulons exploiter des compositions Booléennes arbitraires de primitives (par exemple, extraire les chaînes qui sont suffisamment fréquentes dans un jeu de données mais non fréquentes dans un autre et qui ne contiennent pas une certaine sous-chaîne). Un solveur générique typique de l’état de l’art comme FAVST est capable d'optimiser l’évaluation de conjonctions de contraintes dites monotones et/ou anti-monotones (e.g., la conjonction de contraintes de fréquence maximale et minimale). Il est beaucoup plus difficile, voir souvent impossible, de développer de tels solveurs pour des contraintes non (anti)-monotones. Nous avons travaillé sur ce problème dans le cas de la recherche de motifs tolérants aux fautes ou exceptions, en particulier pour l'extraction de motifs dégénérés et pour aider l'analyse de données intrinsèquement bruitées. Notre contribution méthodologique est double. D'abord, nous avons étudié différentes façons de définir les occurrences approchées pour les chaînes ainsi que des contraintes de fréquence approchée en exploitant des mesures de similarité. Le point crucial ici est que de telles contraintes ne sont généralement pas (anti)-monotones. Notre proposition est de proposer des contraintes de similarité pertinentes (avec les concepts d’occurrences approchées associées) qui se décomposent comme des conjonctions de contraintes monotones et anti-monotones. Nous avons ainsi développé un solveur générique appelé Marguerite capable d'exploiter de telles contraintes. Ensuite, nous avons étudié le problème du réglage des paramètres d'extraction qui est inhérent à toute tâche de fouille de données sous contraintes (e.g., quel seuil choisir pour les contraintes de fréquence). Nous avons proposé une méthode originale pour estimer le nombre de motifs satisfaisants une conjonction de contraintes donnée par échantillonnage de l'espace des motifs. La question soulevée est d'identifier les paramètres les plus stringents qui fournissent toujours des motifs solution et qui ne sont probablement pas des faux positifs en fonction d'une mesure de similarité appelé Twilight Zone Indicator (TZI). Ces différentes contributions ont été appliquées à l'analyse des séquences promotrices des gènes. En étroite collaboration avec une équipe de biologistes dont l'expertise est l'étude des mécanismes d'auto renouvellement cellulaire, nous avons pu identifier, grâce à Marguerite et à la mesure TZI, des sites de fixation putatifs de facteurs de transcription impliqués dans le processus de différenciation cellulaire.