Motivé par la découverte automatique de la structure hiérarchique de séquences d'ADN, nous nous intéressons au probléme classique de la recherche de la plus petite grammaire algébrique générant exactement une séquence donnée. Ce probléme NP-dur a été largement étudié pour des applications comme la compression de données, la découverte de structure et la théorie algorithmique de l'information. Nous proposons de décomposer ce probléme en deux problémes d'optimisation complémentaires. Le premier consiste á choisir les chaînes de la séquence qui seront les constituants de la grammaire finale alors que le second, que nous appelons ''analyse grammaticale minimale'', consiste á trouver une grammaire de taille minimale permettant l'analyse syntaxique de ces constituants. Nous donnons une solution polynomiale au probléme d' ''analyse grammaticale minimale'' et montrons que cette décomposition permet de définir un espace de recherche complet pour le probléme de la plus petite grammaire algébrique. Nous nous intéressons aux algorithmes praticables permettant de retourner une approximation du probléme en un temps suffisamment raisonnable pour être appliqués á de grandes séquences telles que les séquences génomiques. Nous analysons l'impact de l'utilisation de classes différentes de maximalité de répétitions pour le choix des constituants et le compromis entre l'efficacité et la taille de la grammaire finale. Nous présentons des avancées algorithmiques pour une meilleure efficacité des algorithmes hors-ligne existants, dont notamment la mise á jour incrémentale de tableaux de suffixes en cours de recodage. Enfin, la nouvelle décomposition du probléme nous permet de proposer de nouveaux algorithmes génériques permettant de trouver des grammaires 10\% plus petites que l'état de l'art. Enfin, nous nous intéressons á l'impact de ces idées sur les applications. En ce qui concerne la découverte de structures, nous étudions le nombre de grammaires minimales et montrons que ce nombre peut être exponentiel dans le pire cas. Nos expérimentations sur des jeux de séquences permettent cependant de montrer une certaine stabilité de structure au sein des grammaires minimales obtenues á partir d'un ensemble de constituants. En ce qui concerne la compression des données, nous contribuons dans chacune des trois étapes de la compression á base de grammaires. Nous définissons alors un nouvel algorithme qui optimise la taille de la chaine de bits finale au lieu de la taille de la grammaire. En l'appliquant sur les séquences d'ADN, nos expérimentations montrent que cet algorithme surpasse tout autre compresseur spécifique d'ADN á base de grammaire. Nous améliorons ce résultat en utilisant des répétitions inexactes et arrivons á améliorer les taux de compression de 25\% par rapport aux meilleurs compresseurs d'ADN á base de grammaire. Outre l'obtention de taux de compression plus performants, cette approche permet également envisager des généralisations intéressantes de ces grammaires.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00595494 |
| Date | 15 February 2011 |
| Creators | Gallé, Matthias |
| Publisher | Université Rennes 1 |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0022 seconds